[原理] Lex Yacc规则格式

历史

• 在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的输入：词法规则（.l文件）
• Lex的输出：词法分析器
• Yacc的输入：语法规则（.y文件）
• Yacc的输出：语法分析器
• 宿主程序使用词法分析器和语法分析器，产生分析结果。
  image.png

规则格式

Lex匹配规则
Yacc匹配规则
Lex文件格式
Lex预定义变量

Lex代码示例

ECHO
LineNo
变量名
字符统计

Yacc文法

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

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

Shift -Reduce冲突

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

Reduce-Reduce冲突

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

Yacc语法格式

语法格式

Yacc代码示例

• 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文件

示例使用

几次输入输出
第1次输入

下载地址

https://github.com/lexxmark/winflexbison

参考文章

• 官网教程
  http://epaperpress.com/lexandyacc/bib.html
• 其他
  Lex Yacc (一) 入门
  Yacc 与 Lex 快速入门
  算法优先级