[原理] Lex Yacc规则格式

2018-04-02 本文已影响0人 CrazyTiger

在1975年之前，写出一个编译器是很麻烦的事情。在1975年的时候，有两篇文章的发表，简化了编译器的编写。
Lex - A Lexical Analyzer Generator.
Yacc: Yet Another Compiler Compiler.
Lex和YACC的具体实现细节可以在2006年的这本书中找到：
Compilers, Principles, Techniques and Tools (2nd edition). Addison-Wesley, Reading, Massachusetts.
WinFlex和WinBison是Flex和Bison的Windows版本。

image.png

Lex匹配规则

Yacc匹配规则

Lex文件格式

Lex预定义变量

ECHO

LineNo

变量名

字符统计

Yacc的语法是BNF范式的变种。BNF文法可以用来表示上下文无关文法，大多数的编程语言都可以用BNF来表示。

文法

文法可以扩展的表达式

自底向上分析。默认放一个“.”在栈里面。shift操作：一个新的标识符入栈。reduce操作：使用文法进行规约。

例子中的第6步，E+E可以进行Reduce，但是也可以进行Shift。使用符号结合方向和优先级解决。

id有两种Reduce结果：E或者T。

语法格式

lex文件
词法分析器输出的Token类型：VARIABLE，INTEGER，-，+，（，），=，/，\n，a-z
yacc文件
词法标识：INTEGER，VARIABLE
符号优先级与结合方式
文法标识：program，statement，expr
int sys[26]：a-z 26个变量的数值
yytext
词法分析器匹配到的字符串
yylval
yytext相关的数值，比如：在词法分析器匹配到数字的时候，设置yylval=atoi(yytext) ，在语法分析器，就可以通过$1，$2，来读取对应的yylval。
实际上，yacc内部有两个栈，一个是分析栈，一个是内容栈，分别用yytext和yylval来读取。
Lex Yacc (一) 入门这里说的更加详细一些。
Lex文件
Yacc文件