Lex vs Yacc

lex-yacc


 在开源世界里，lex与yacc的对应实现是：flex与bison。在fedora下，可以通过如下命令进行安装：
　　sudo yum -y install flex bison

Lex的本质，是利用正则表达式和额外实现的语法规则（如start condition），来描述token的切分方法，即词法规则。lex把用户定制的token切分方法，实现为一个yylex函数(此函数通常为int yylex()，但也有其他形式)。 yylex函数的作用，是从输入的文件流（从stdin读取）中，每次切分出一个token，然后返回。每个token都含有两个属性： token-type和token-value。token-type就是yylex的返回值，是整型；而token-value的数据类型，由宏 YYSTYPE决定，值需赋值给yylval(其类型即为YYSTYPE)。YYSTYPE，可以由用户显式定义，也可以利用yacc生成(可以通过在 yacc的语法规则文件里，定义%union的结构，yacc就会把这个结构作为宏YYSTYPE的定义)。lex孤立来看没有意义的，因为它只生成一个 yylex函数。这个函数，只有被yacc所用，才真正发挥实效。

Yacc的本质，是利用BNF(Backus Naur Form, 巴科期范式)，来描述语法规则， 然后根据这些规则生成语法解析的C代码。关于词法规则与语法规则的区别，个人理解为，词法规则描述token的切分方法(如何划分token，token 的类别是什么，其值是又是什么)，语法规则描述token之间的组合方式(哪种token组合是合法的，当遇到某种组合时，执行什么动作)。显然yacc 的处理，必须建立在token已经被划分出来的基础之上。而yacc划分token的方法，依赖于由用户定义的一个yylex函数。而lex就是为了方便 实现这个函数而设计的。当然，这个函数，也可由我们自已手动编写，lex不是必须的，只是它提供了一个更快且通用的实现方法而已。

Yacc 为什么要求yylex切分出来的token具有两个属性(token-type, token-value)？yacc的语法规则，包含三个元素： Nonterminal token, Terminal token。 Terminal token，是不可再分的，例如关键字、数值、标识符等。Nonterminal token是可以再分解的，即它是由Terminal tokne组合而成的，这个组合的方式，就是通过语法规则来描述的。本质上，把语法规则全部扩展之后，每个元素都是Terminal token。而为了描述这些Terminal token的组合方式，只能用这些token的类别(token-type)而不是值(token-value)来抽象它们。所以，当然yacc对一个文 本流进行解析时，是通过把这些文本流的token的type取出来，然后用语法规则去匹配，如果匹配成功，则表明语法合格，否则会报一个错(通过 yyerror(char *s)函数，这个函数也由用户实现)。