词法分析器（Scanner）和语法解析器

Lex（Lexical Analyzar）

词法分析器，简单来说，其任务就是将输入的各种符号，转化成相应的标识符(token)，转化后的标识符很容易被后续阶段处理

Lex工具是一种词法分析程序生成器，它可以根据词法规则说明书的要求来生成单词识
别程序，由该程序识别出输入文本中的各个单词。一般可以分为定义部分、规则部
分、用户子程序部分。其中规则部分是必须的，定义和用户子程序部分是任选的

Lex编程可以分为三步：

以Lex可以理解的格式指定模式相关的动作
在这一文件上运行Lex，生成扫描器的C代码
编译和链接C代码，生成可执行的扫描器

下面的程序识别一组动词

%{
#include <stdio.h>
int k;
%}
%%
[\t ]+
is |
am |
are |
were |
was |
be |
being |
been |
do |
does |
did |
will |
would |
should |
can |
could |
has |
have |
had |
go              { printf("%s: is a verb\n",yytext); }
[a-zA-Z]+               {printf("%s: is not a verb\n",yytext);}

.|\n            {ECHO;}
%%

int main()
{
        yyin = fopen("example.txt","r");
                yylex();
        fclose(yyin);
}
int yywrap()
{
        return 1;
}

通过flex flex_test.l命令生成相应的C语言程序，然后编译执行，得到下图

定义部分

起始于%{，终止于%}符号

规则部分

起始于%%符号，终止于%%符号，期间就是词法规则，词法规则由模式和动作组成。模式部分可以由任意的正则表达式组成，动作部分是由C语言语句组
成，这些语句用来对所匹配的模式进行相应处理

需要注意的是，lex将识别出来的单
词存放在yytext[]字符数据中，因此该数组的内容就代表了所识别出来的单词的内容。
类似yytext这些预定义的变量函数会随着后面内容展开一一介绍。动作部分如果有多
行执行语句，也可以用{}括起来

正则表达式是规则部分最麻烦的一部分

规则部分也能使用变量，例如

%{
#include "stdio.h"
int linenum;
%}
int                   [0-9]+
float                 [0-9]*/.[0-9]+
%%
{int}                 printf("Int     : %s/n",yytext);
{float}               printf("Float   : %s/n",yytext);
.                     printf("Unknown : %c/n",yytext[0]);
%%

在%}和%%之间，加入了一些类似变量的东西，注意是没有;的，这表示int，float分
别代指特定的含义，在两个%%之间，可以通过{int} {float}进行直接引用，简化模式定义

用户子程序部分

最后一个%%后面的内容是用户子程序部分，可以包含用C语言编写的子程序，而这些子
程序可以用在前面的动作中，这样就可以达到简化编程的目的。这里需要注意的是，
当编译时不带-ll选项时，是必须加入main函数和yywrap，如：

%%
showtitle()
{
printf("----- Lex Example -----/n");
}

int main()
{
  linenum=0;
  yylex(); /* 进行Lex分析 */
  printf("/nLine Count: %d/n",linenum);
  return 0;
}
int yywrap()
{
return 1;
}

Lex内置变量和函数

内置变量：

yytext： char *，当前匹配的字符串
yyleng： int，当前匹配的字符串长度
yyin： FILE *，lex当前的解析文件，默认为标准输出
yyout： FILE *，lex解析后的输出文件，默认为标准输入
yylineno： int，当前的行数信息

内置宏：

ECHO：#define ECHO fwrite(yytext, yyleng, 1, yyout)，也是未匹配字符的默认动作

内置函数：

int yylex(void)：调用Lex进行词法分析
int yywrap(void)：在文件(或输入)的末尾调用。如果函数的返回值是1，就停止解析。因此它可以用来解析多个文件。代码可以写在第三段，这样可以解析多个文件。方法是使用yyin文件指针指向不同的文件，直到所有的文件都被解析。最后，yywrap() 可以返回1来表示解析的结束

Lex其实就是词法分析器，通过配置文件*.l，依据正则表达式逐字符去顺序解析文件，
并动态更新内存的数据解析状态。不过Lex只有状态和状态转换能力。因为它没有堆栈，
它不适合用于剖析外壳结构。而yacc增加了一个堆栈，并且能够轻易处理像括号这样的
结构。Lex善长于模式匹配，如果有更多的运算要求就需要yacc了

Yacc

Yacc文法采用BNF(Backus-Naur Form)的变量规则描述。BNF文法最初由John Backus和Peter Naur发明，并且用于描述Algol60语言。BNF能够用于表达上下文无关的语言。现代程序语言大多数结构能够用BNF来描述

出现在每个产生式左边(left-hand side：lhs)的符号是非终端符号，出现在产生式右边(right-hand side：rhs)的符号有非终端符号和终端符号，但终端符号只出现在右端

1、yacc语法规则部分和BNF类同，先来看BNF巴克斯范式

（1）<> 内包含的内容为必选项；

（2）[] 内的包含的内容为可选项；

（3）{ } 内包含的为可重复0至无数次的项；

（4） | 表示在其左右两边任选一项，相当于”OR”的意思；
（5）::= 是“被定义为”的意思；
（6）双引号“”内的内容代表这些字符本身；而double _quote用来表示双引号

2.Yacc文件格式
Yacc文件分为三部分：

... definitions ...
%%
... rules ...
%%
... subroutines ...

3.定义部分
第一部分包括标志(token)定义和C代码(用“%{”和“%}”括起来)。

如在定义部分定义标志：

%token INTEGER
当运行yacc后，会产生头文件，里面包含该标志的预定义，如：

#ifndef  YYSTYPE
#define  YYSTYPE int
#endif
#define  INTEGER  258
extern  YYSTYPE  yylval;

lex使用该头文件中的标志定义。Yacc调用lex的yylex()来获得标志(token)，与标志对应的值由lex放在变量yylval中。yylval的类型由YYSTYPE决定，YYSTYPE缺省类型是int。如：

[0-9]+ {
yylval = atoi(yytext);
return INTEGER;
}
标志0-255被保留作为字符值，一般产生的token标志从258开始。如：

1	[-+] return yytext; / return operator */

返回加号或减号。注意要把减号放在前面，避免被认作是范围符号。

对于操作符，可以定义%left和%right：%left表示左相关(left-associative)，%right表示右相关(right-associative)。可以定义多组%left或%right，在后面定义的组有更高的优先级。如：

1 2	%left ‘+’ ‘-‘ %left ‘*’ ‘/’

上面定义的乘法和除法比加法和减法有更高的优先级。

Yacc内部维持着两个栈：符号栈(parse stack)和值栈(value stack)，这两个栈始终是同步的。

改变YYSTYPE的类型。如这样定义TTSTYPE：

%union {
    int     iValue;    /* integer value */
    char    sIndex;    /* symbol table index */
    nodeType *nPtr;    /* node pointer */
};

则生成的头文件中的内容是：

typedef union {
    int     iValue;   /* integer value */
    char    sIndex;   /* symbol table index */
    nodeType *nPtr;   /* node pointer */
} YYSTYPE;
extern  YYSTYPE  yylval;

可以把标志(token)绑定到YYSTYPE的某个域。如：

1 2	%token <iValue> INTEGER %type <nPtr> expr

把expr绑定到nPtr，把INTEGER绑定到iValue。yacc处理时会做转换。如：

expr: INTEGER { $ = con($1); }
转换结果为：

yylval.nPtr = con(yyvsp[0].iValue);
其中yyvsp[0]是值栈(value stack)当前的头部。

定义一元减号符有更高的优先级的方法：

%left GE LE EQ NE '>' '<'
%left '+' '-'
%left '*'
%nonassoc UMINUS

%nonassoc的含义是没有结合性。它一般与%prec结合使用表示该操作有同样的优先级。如：

expr: ‘-‘ expr %prec UMINUS { $ = node(UMINUS, 1, $2); }
表示该操作的优先级与UMINUS相同，在上面的定义中，UMINUS的优先级高于其他操作符，所以该操作的优先级也高于其他操作符计算。

4.规则部分
规则部分很象BNF语法。

规则中目标或非终端符放在左边，后跟一个冒号(:)，然后是产生式的右边，之后是对应的动作(用{}包含)。如：

%token INTEGER
%%
program: program expr '/n' { printf("%d/n", $2); }
|
;
expr:  INTEGER   { $ = $1; }
| expr '+' expr { $ = $1 + $3; }
| expr '-' expr { $ = $1 - $3; }
;
%%
int yyerror(char *s)
{
    fprintf(stderr, "%s/n", s);
    return 0;
}
int main(void)
{
    yyparse();
    return 0;
}

其中，$1表示右边的第一个标记的值，$2表示右边的第二个标记的值，依次类推。$$表示规约后的值。

5.第三部分
该部分是函数部分。当yacc解析出错时，会调用函数yyerror()，用户可自定义函数的实现。main函数是调用yacc解析入口函数yyparse()。

6.递归的处理
递归处理有左递归和右递归。

左递归形式：

list:
item
| list ‘,’ item ;
右递归形式：

list: item
| item ‘,’ list
使用右递归时，所有的项都压入堆栈里，才开始规约；而使用左递归的话，同一时刻不会有超过三个项在堆栈里。

所以，使用左递归有很大的优势。

7.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

8.出错处理
当yacc解析出错时，缺省的行为是调用函数yyerror()，然后从yylex返回一个值。一个更友好的方法是忽略一段错误输入流，继续开始扫描。实现方法如下：

stmt:
';'
| expr ';'
| PRINT expr ';'
| VARIABLE '=' expr ';

| WHILE '(' expr ')' stmt
| IF '(' expr ')' stmt %prec IFX
| IF '(' expr ')' stmt ELSE stmt
| '{' stmt_list '}'
| error ';'
| error '}'
;

这里的error标志表示，当yacc发现错误时，它调用yyerror()，之后是输入流往前到‘；’或‘}’，然后继续扫描

9.Yacc源程序的风格
建议按照如下风格来写：
终端符名全部用大写字母，非终端符全部用小写字母；
把语法规则和语义动作放在不同的行；
把左部相同的规则写在一起，左部只写一次，而后面所有规则都写在竖线“|”之后；
把分号“；”放在规则最后，独占一行；
用制表符来对齐规则和动作