Lex和Yacc
Lex 代表 Lexical Analyzar, Yacc 代表 Yet Another Compiler Compiler。
Lex
Lex 是一种生成扫描器的工具。 Lex是Unix环境下非常著名的工具,主要功能是生成一个扫描器(Scanner)的C源码。
扫描器是一种识别文本中的词汇模式的程序。 这些词汇模式（或者常规表达式）在一种特殊的句子结构中定义。一种匹配的常规表达式可能会包含相关的动作。这一动作可能还包括返回一个标记。 当 Lex 接收到文件或文本形式的输入时，它试图将文本与常规表达式进行匹配。 它一次读入一个输入字符，直到找到一个匹配的模式。 如果能够找到一个匹配的模式，Lex 就执行相关的动作（可能包括返回一个标记）。 另一方面，如果没有可以匹配的常规表达式，将会停止进一步的处理，Lex 将显示一个错误消息。
Lex 和 C 是强耦合的。一个 .lex 文件（Lex 文件具有 .lex 的扩展名）通过 lex 公用程序来传递，并生成 C 的输出文件。这些文件被编译为词法分析器的可执行版本。
Lex程序
一个典型的Lex程序的大致结构:
declarations
%%
translation rules
%%
auxiliary procedures
分别是声明，转换规则和其它函数。%用作在单个部分之间做分隔。
字符及其含义列表：
A-Z, 0-9, a-z 构成了部分模式的字符和数字。
. 匹配任意字符，除了 \n。
- 用来指定范围。例如：A-Z 指从 A 到 Z 之间的所有字符。
[ ] 一个字符集合。匹配括号内的 任意 字符。如果第一个字符是 ^ 那么它表示否定模式。
例如: [abC] 匹配 a, b, 和 C中的任何一个。
* 匹配 0个或者多个上述的模式。
+ 匹配 1个或者多个上述模式。
? 匹配 0个或1个上述模式。
$ 作为模式的最后一个字符匹配一行的结尾。
{ } 指出一个模式可能出现的次数。 例如: A{1,3} 表示 A 可能出现1次或3次。
\ 用来转义元字符。同样用来覆盖字符在此表中定义的特殊意义，只取字符的本意。
^ 否定。
| 表达式间的逻辑或。
"<一些符号>" 字符的字面含义。元字符具有。
/ 向前匹配。如果在匹配的模版中的“/”后跟有后续表达式，只匹配模版中“/”前 面的部分。
如：如果输入 A01，那么在模版 A0/1 中的 A0 是匹配的。
( ) 将一系列常规表达式分组。
标记声明：
数字(number) ([0-9])+ 1个或多个数字
字符(chars) [A-Za-z] 任意字符
空格(blank) " " 一个空格
字(word) (chars)+ 1个或多个 chars
变量(variable) (字符)+(数字)*(字符)*(数字)*
值得注意的是，lex 依次尝试每一个规则，尽可能地匹配最长的输入流。如果有一些内容根本不匹配任何规则，那么 lex 将只是把它拷贝到标准输出。
Lex 编程可以分为三步：
- 以 Lex 可以理解的格式指定模式相关的动作。
- 在这一文件上运行 Lex，生成扫描器的 C 代码。
- 编译和链接 C 代码，生成可执行的扫描器。
例如，对于一下的Lex代码：
%{
#include <stdio.h>
int k = 0;
%}
%%
[0-9]+ {
k = atoi(yytext);
if(k % 6 == 0 && k % 8 == 0) {
printf("%d\n", k);
}
}
执行：
lex prog.lex
gcc lex.yy.c -o prog -ll
然后将会得到一个可执行文件，这个可执行文件的功能是：如果输入的字符串不是数字，原样输出，如果是数字，判断是否为6和8的公倍数，若是，则输出。
其中，-ll表示链接lex的相关库文件，要想编译时不带-ll选项，就必须实现main函数和yywrap函数(return 1即可)。
Lex中，一般声明为如下形式：
%{
int wordCount = 0;
%}
chars [A-Za-z\_\'\.\"]
numbers ([0-9])+
delim [" "\n\t]
whitespace {delim}+
words {chars}+
模式匹配规则如下例：
{words} { wordCount++; /* increase the word count by one*/ }
{whitespace} { /* do nothing*/ }
{numbers} { /* one may want to add some processing here*/ }
含义为针对不同的模式采取不同的策略（状态机）。
Lex程序的最后一段一般为C代码，为如下形式：
void main()
{
yylex(); /* start the analysis*/
// ... do some work.
}
int yywrap()
{
return 1;
}
最后一段覆盖了 C 的函数声明（有时是主函数）。注意这一段必须包括 yywrap() 函数。
在上文中的判断公倍数的例子中，省略了程序的第三段，Lex生成了默认的C风格的main()函数。
在使用Lex做文法解析时，某些特殊结构的表达式会使由表格转化的确定的自动机成指数增长，并因此造成指数级的空间和时间复杂度消耗。
Lex变量和函数
一些常用的Lex变量如下所示：
yyin FILE* 类型。 它指向 lexer 正在解析的当前文件。
yyout FILE* 类型。 它指向记录 lexer 输出的位置。 缺省情况下，yyin 和 yyout 都指向标准输入和输出。
yytext 匹配模式的文本存储在这一变量中（char*）。
yyleng 给出匹配模式的长度。
yylineno 提供当前的行数信息。 （lexer不一定支持。）
Lex函数:
yylex() 这一函数开始分析。 它由 Lex 自动生成。
yywrap() 这一函数在文件（或输入）的末尾调用。 如果函数的返回值是1，就停止解析。
因此它可以用来解析多个文件。 代码可以写在第三段，这就能够解析多个文件。
方法是使用 yyin 文件指针（见上表）指向不同的文件，直到所有的文件都被解析。
最后，yywrap() 可以返回 1 来表示解析的结束。
yyless(int n) 这一函数可以用来送回除了前 n 个字符外的所有读出标记。
yymore() 这一函数告诉 Lexer 将下一个标记附加到当前标记后。
Lex内部预定义宏:
ECHO #define ECHO fwrite(yytext, yyleng, 1, yyout) 也是未匹配字符的默认动作。
一个简单的Lex的例子：
%{
#include <stdio.h>
%}
%%
[\n] { printf("new line\n"); }
[0-9]+ { printf("int: %d\n", atoi(yytext)); }
[0-9]*\.[0-9]+ { printf("float: %f\n", atof(yytext)); }
[a-zA-Z][a-zA-Z0-9]* { printf("var: %s\n", yytext); }
[\+\-\*\/\%] { printf("op: %s\n", yytext); }
. { printf("unknown: %c\n", yytext[0]); }
%%
Yacc
Yacc 代表 Yet Another Compiler Compiler。 Yacc 的 GNU 版叫做 Bison。它是一种工具，将任何一种编程语言的所有语法翻译成针对此种语言的 Yacc 语 法解析器。它用巴科斯范式(BNF, Backus Naur Form)来书写。按照惯例，Yacc 文件有 .y 后缀。
用 Yacc 来创建一个编译器包括四个步骤：
- 通过在语法文件上运行 Yacc 生成一个解析器。
-
说明语法：
- 编写一个 .y 的语法文件（同时说明 C 在这里要进行的动作）。
- 编写一个词法分析器来处理输入并将标记传递给解析器。 这可以使用 Lex 来完成。
- 编写一个函数，通过调用 yyparse() 来开始解析。
- 编写错误处理例程（如 yyerror()）。
- 编译 Yacc 生成的代码以及其他相关的源文件。
- 将目标文件链接到适当的可执行解析器库。
Yacc程序
如同 Lex 一样, 一个 Yacc 程序也用双百分号分为三段。 它们是：声明、语法规则和 C 代码。 每两段内容之间用%%。
一个Yacc程序示例：
%{
typedef char* string;
#define YYSTYPE string
%}
%token NAME EQ AGE
%%
file: record file
| record
;
record: NAME EQ AGE {
printf("name: %s, eq: %d, age: %d\n, $1, $2, $3);
}
;
%%
int main()
{
yyparse();
return 0;
}
int yyerror(char *msg)
{
printf("ERORR MESSAGE: %s\n", msg);
}
Lex和YACC内部工作原理
在YACC文件中，main函数调用了yyparse()，此函数由YACC替你生成的，在y.tab.c文件中。函数yyparse从yylex中读取符号/值组成的流。你可以自己编码实现这点，或者让Lex帮你完成。在我们的示例中，我们选择将此任务交给Lex。
Lex中的yylex函数从一个称作yyin的文件指针所指的文件中读取字符。如果你没有设置yyin，默认是标准输入(stdin)。输出为yyout，默认为标准输出(stdout)。
你可以在yywrap函数中修改yyin，此函数在每一个输入文件被解析完毕时被调用，它允许你打开其它的文件继续解析，如果是这样，yywarp的返回值为0。如果想结束解析文件，返回1。
每次调用yylex函数用一个整数作为返回值，表示一种符号类型，告诉YACC当前读取到的符号类型，此符号是否有值是可选的，yylval即存放了其值。
默认yylval的类型是整型（int）,但是可以通过重定义YYSTYPE以对其进行重写。分词器需要取得yylval,为此必须将其定义为一个外部变量。原始YACC不会帮你做这些，因此你得将下面的内容添加到你的分词器中，就在#include<y.tab.h>下即可：
extern YYSTYPE yylval;
Bison会自动做这些工作（使用-d选项生成y.tab.h文件）。
Lex与Yacc配合
使用Lex和Yacc实现一个简单的四则运算计算器：
Lex代码的内容：
/* calc.lex */
%{
#include <stdio.h>
#include "y.tab.h"
void yyerror(char *);
%}
%%
[0-9]+ { yylval = atoi(yytext); return INTEGER; }
[\+\-\*\/\(\)\n] { return *yytext; }
[\t] {}
. { yyerror("invalid char."); }
%%
int yywarp() { return 1; }
Yacc代码的内容：
/* calc.y */
%{
#include <stdio.h>
#include <stdlib.h>
int yylex();
void yyerror();
%}
%token INTEGER
%left '+' '-'
%left '*' '/'
/* %left 表示左结合，%right 表示右结合。 */
/* 最后列出的定义拥有最高的优先权。 运用这个简单的技术，我们可以消除文法的歧义。*/
%%
program:
program expr '\n' { printf("result: %d\n", $2); }
|
;
expr:
INTEGER { $$ = $1; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr { $$ = $1 / $3; }
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
| '(' expr ')' { $$ = $2; }
| { yyerror("invalid input.\n"); }
;
/* "$$"表示缩小后的堆栈顶部。$1，$2都是yacc预定义可以直接使用的标记(用相对地址访问内容栈中的值)。 */
/* “$1”代表右式中的第一个成员，“$2”代表第二个，后面的以此类推。*/
%%
void yyerror(char *s)
{
printf("YACC erro: %s\n", s);
}
int main()
{
yyparse();
return 0;
}
运行：
yacc calc.y -d
lex calc.lex
gcc lex.yy.c y.tab.c -o calc
将会得到一个可执行文件calc，运行，输入四则运算表达式，将会得到结果。运行yacc时，-d 表示生成头文件，如果你想将 yylex 定义放到独立的源文件中，你需要 y.tab.h, 因为 yylex必须能够引用标记类型代码和 yylval 变量。
Lex和Yacc使用变量
我们在以前的基础上，深入一步，设计一个简单的计算器，包含+,-,*,/四项操作，且支持()运算符，其中对值可以进行变量保存，并打印出内部的分析信息。
Lex代码：
/* calc.lex */
%{
#include <stdio.h>
#include "y.tab.h"
void yyerror(char *);
%}
%%
[a-zA-Z] { yylval = yytext[0]; return VAR; }
[0-9]+ { yylval = atoi(yytext); return INTEGER; }
[\+\-\*\/\(\)=\n] { yylval = yytext[0]; return yytext[0]; }
[\t ] { } /* skip all space. */
. { yyerror("invalid char seq."); }
%%
int yywarp() {
return 1;
}
Yacc文件：
/* calc.y */
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int yylex();
void yyerror();
int mem[256] = {0};
%}
%token VAR
%token INTEGER
%token END
%left '+' '-'
%left '*' '/'
%%
program:
statement /* single line. */
| program '\n' statement /* multiple lines. */
;
statement:
expr { fprintf(yyout, "%d\n", $1); } /* output result */
| VAR '=' expr { mem[$1] = $3; }
| /* empty lines */
;
expr:
INTEGER { $$ = $1; }
| VAR { $$ = mem[$1]; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr { $$ = $1 / $3; }
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
| '(' expr ')' { $$ = $2; }
;
%%
void yyerror(char *s)
{
printf("YACC erro: %s\n", s);
}
int main()
{
yyparse();
return 0;
}
编译程序：
yacc calc.y -d
lex calc.lex
gcc lex.yy.c y.tab.c -o calc -ll
测试文件内容：
a=(1+(1+(1+1)))+1
b = (2*3) + a
a
b
执行./calc < calctest,会得到一下的结果输出：
5
11
这个程序的关键之处在于使用了一个mem数组来记录所有的变量的值，使得计算结果和变量状态得以保持。
高级yylval: union
YACC的yylval类型是取决于YYSTYPE。如果yylval是个联合体，它即可以处理字符串，也可以是整数，但不是同时处理这两种。我们可以通过定义YYSTYPE为联合体。不过YACC有一个更简单的方法：使用%union语句。
%union {
int number;
char *string;
}
%token <number> STATE
%token <number> NUMBER
%token <string> WORD
定义了我们的联合体，它仅包含数字和字体串，然后使用一个扩展的%token语法，告诉YACC应该取联合体的哪一个部分。
我们不再直接获取yylval的值，而是添加一个后缀指示想取得哪个部分的值。
%{
#include <stdio.h>
#include <string.h>
#include "y.tab.h"
%}
%%
[0−9]+ yylval.number=atoi(yytext); return NUMBER;
[a-z][a−z0−9]+ yylval.string=yytext; return WORD;
%%
不过在YACC语法中，我们无须这样做，因为YACC为我们做了神奇的这些, 由于上面的%token定义，YACC自动从联合体中挑选string成员。
heater_select:
TOKHEATER WORD {
printf("Selected heater '%s'\n", $2);
heater = $2;
}
;
需要注意的是，一般来时，yyvsp[0]相当于$1, yyvsp[1]相当于$2,但是，在当yylval为union的时候，$1相当于yysvp[0]的某个类型的值，这个类型是Yacc推断出来的类型。例如，上例中的$2相当于yyvsp[1].string。因此，使用%union的时候的尤其注意这个问题。我们知道，在C语言中，Union在bit级别上是低位对齐(所有成员都从低地址开始存放的)的，因此，有些时候这可能会导致某些错误。
Inter X86 CPU是小端(Little-endian)模式, 例如，0x12345678在内存中的排列情况为：
内存地址 存放内容
0x4000 0x78
0x4001 0x56
0x4002 0x34
0x4003 0x12
因此，在使用Yacc时，对于由于类型判断错误而导致的union的值错误的情形要非常谨慎。
有歧义的文法
通常文法是有歧义的，比如：四则运算”34+5“，应该如何分组操作符？这个表达式的意思是(34)+5，还是3*(4+5)？当yacc遇到歧义的文法时，会报错”shift/reduce”冲突或者”reduce/reduce”冲突。
遇到”shift/reduce”冲突是因为yacc在遇到一个词法单元时，不知道应该执行规约动作还是执行词法单元移动。
出现”shift/reduce”冲突时，yacc可以根据规则的优先级和结合性进行处理，具体规则：
- 如果当前的词法单元的优先级高于解析栈中规则，那么执行shift动作。
- 如果当前的词法单元的优先级低于解析栈中规则，那么将栈中的规则进行规约。
- 在当前的词法单元和解析栈中规则的优先级相同的情况下，如果规则是左结合性，那么执行规约动作，否则执行shift。
- 如果没有提供优先级和结合性，那么默认执行shift动作。
StackOverflow上有一个问题是一个很好的处理”shift/reduce conflicts”的例子：Shift/reduce conflicts in bison
“reduce/reduce”冲突就是解析栈中可以应用多个规则进行规约，这种冲突的解决就是选择第一个出现的规则进行规约。一般出现这种冲突主要是因为不同的规则集合可以产生相同的词法单元序列。
通过%nonassoc指定操作符不具备结合性。nonassoc, 意味着没有依赖关系。它经常在连接词中和 %prec一起使用，用于指定一个规则的优先级。
以If-Else的冲突为例，当有两个IF一个ELSE时，该ELSE和哪个IF匹配是一个问题。有两中匹配方法：与第一个匹配和与第二匹配。现代程序语言都让ELSE与最近的IF匹配，这也是yacc的缺省行为。虽然yacc行为正确，但为避免警告，可以给IF-ELSE语句比IF语句更高的优先级：
%nonassoc IFX
%nonassoc ELSE
stmt:
IF expr stmt %prec IFX
| IF expr stmt ELSE stmt
一个关于’%prec’的解释：
It declares that that construct has the same precedence as the ‘.’ operator, which will have been specified earlier.
Yacc源程序的风格
- 终端符名全部用大写字母，非终端符全部用小写字母；
- 把语法规则和语义动作放在不同的行；
-
把左部相同的规则写在一起，左部只写一次，而后面所有规则都写在竖线“ ”之后； - 把分号“；”放在规则最后，独占一行；
- 用制表符来对齐规则和动作。
YACC中的递归分为两类：左递归和右递归。大部分时候你应该使用左递归，就像这样：
commands: /*empty*/
|
commands command
它的意思是，一个命令集要么是空，要么它包含更多的命令集以及后面跟着一个命令。YACC的工作方式意味着它可以轻松的砍掉单独的命令块（从前面）并逐步归约它们。
一个采用右递归的例子：
commands: /*empty*/
|
command commands
但这样代价太高了。如果使用%start规则，需要YACC将所有的命令放在栈上，消耗很多的内存。因此尽可能使用左递归解析长语句，比如解析整个文件。有时则无可避免的使用右递归，如果语句不是太长，不需要想尽一切方法使用左递归。