Lex&Yacc
1 知识储备：
1.1 工具
1.1.1 Bison
bison是一个通用解析器生成器，将LALR(1)上下文无关文法转变成一个解析该语法的C程序，可被用于开发各种语言的解析器，向上兼容Yacc，用C开发语法解析器时要安装Bison
1.1.2 Flex
flex是一个高速的词法分析器生成器，可用于对文字(text)进行模式匹配(pattern-matching), 它是lex的众多版本之一，选择flex是因为可以方便的在Windows系统安装
1.1.3 GCC(GNU Compiler Collection)
bison和flex需要的编译包都是GnuWin32，在win环境下，使用MinGW工具安装gcc编译环境
1.2 编译器原理概述
1.2.1 编程语言的编译器通常可被分为五个阶段：
- 词法分析：分析源码，扫描字符串，分离出所有语法单位(tokens), 这个任务可由Lex自动化完成
- 语法分析：分析词法分析传来的tokens, 找出符合规定的语法，确定整个输入串能否构成语法正确的句子和程序，这个任务可由Yacc自动化完成
- 中间代码生成：在语法分析正确的基础上，按照语义规则产生介于源语言和目标代码之间的代码，中间代码不依赖于机器，同时便于产生依赖于机器的代码
- 优化：依据等价变换原则，对中间代码进行加工变换，以便在后期生成高效的代码
- 目标代码生成：将优化后的中间代码转换成具体机器的指令序列
- Note：在微、小型机这类对编译质量要求不高的场合，可跳过中间代码生成阶段，语法分析后直接生成目标代码。语义分析在目标代码生成阶段完成。
1.2.2 词法分析
定义
词法分析器以词法定义为基础，词法定义用正则表达式(正规文法)表示
正则表达式 ->NFA(不确定有限自动机)->DFA(确定有限自动机)->DFA最小化
功能
读取源代码，根据定义的词法分析识别单词，构造词法单元(token)，检查此法错误，最后输出token序列(用二元组表示)
token
-
语言中最小的语法单位
-
分为两部分
-
种类(类号)
-
内容(内码)
-
例如：
<id, 1>
-
-
token种类
-
标识符
变量名、常量名、函数名、数组名… -
数字 数值
整型浮点型布尔型…
-
特殊种类
-
保留字(基本字)
被被语言系统自身定义的有特殊意义的单词，例如
int float void null -
操作符
+ - * / -
分隔符(界限符)
; : ( )
-
-
1.2.3 语法分析
定义
以语法定义(上下文无关文法)为基础，语法定义用产生式表示
功能
读取词法分析器传来的词法单元序列，根据语法定义生成语法结构(组词成句)
语法结构
描述程序结构，例如：
Program -> Type main() Block
Type -> int | bool
Block -> { Stmts return Num ; }
Decl -> Type Array ;
Array -> Identifier [ Num ] | Identifier [ Identifier ] | Identifier
Stmts -> Stmts M Stmt | Stmt
上下文无关文法(context-free grammar)
- 文法中所有的产生式左边只有一个非终结符
- 只要找到符合产生式右边的串，就可以把它归约为对应的非终结符
-
S->ab是一个上下文无关文法 -
aSb->aaSbb是一个上下文有关文法，因为它的第一个产生式左边有不止一个符号，所以你在匹配这个产生式中的S的时候必需确保这个S有正确的“上下文”，也就是左边的a和右边的b
2 Lex
生成词法分析器源码，lex.yy.c
2.1 Lex用于消除歧义的规则：
- 优先原则，只匹配字符或字符串一次，如果出现单词与两个规则都匹配，匹配靠前的规则
- 最长字串匹配原则，执行能匹配到的最长的匹配对应的action
2.2 lex语法分为三段
每段之间用**%%**隔开
2.2.1 定义部分:
-
例：
%{ /* *这是一个Lex的定义部分 */ #undef input #undef unput unsigned verbose; char *progName; %}-
用**%{ %}**包住这块
-
包裹住的部分会被直接复制粘贴进**.l文件生成的.c**文件
-
把想要想要粘贴进最终程序的C代码写这
- 要include的头文件
- 其他C代码
-
2.2.2 规则部分:
-
例：
int { printf("%s: is a verb\n", yytext); } -
规则由模式(pattern)和与应的操作(action)构成
-
pattern:
- 字符串
- 正则表达式
-
action:
- C代码
- return的数据将传递给Yacc作为保留字(token)
-
-
lex生成的词法分析器(lexer)识别出定义的pattern时，将执行对应的action
2.2.3 子程序部分
-
写C代码
- 例子：
main() { yylex(); }
2.3 Lex对比C写出来的词法分析器
- Lex程序长度比C短很多
- C需要花接近三倍于Lex的时间来编写和Debug
- 一些词法用C编写会失败，例如：
/** comment **/，C编写的词法分析器可能会识别不出这个注释的结尾
2.4 lex.yy.c中的全局变量和函数
2.4.1 变量
-
yyout：FILE*类型，指向lexer的输出 -
yyin：FILE*类型，指向lexer的输入 -
yytext：匹配到的文本存在这个变量里
2.4.2 函数
-
yylex()由lex自动生成，从进入这个函数开始分析 -
yywrap()批量处理文件，可以配合yyin在子程序部分使用，返回1表示文件读完，返回0继续读文件 -
ECHO输出匹配到的字符串
2.5 flex词法分析产生器实现过程
词法分析器自动生成器的核心是lex编译器，lex编译器的功能是对某语言单词集描述的lex源程序，将其变换为一个能识别该语言单词的词法分析器。而该词法分析器像有限自动机一样取识别处理单词。
基于lex源程序，lex编译器的实现步骤大致是：
- 对lex源程序识别规则中的每个pi构造一个相应的NFA Ni
- 引入唯一初态S，从初态S通过ε弧将所有NFA Ni（i=1，…，n）连接成新的NFA N’
- 对NFA N’确定化，产生DFA N
- DFA N 最小化
- 给出控制程序。控制程序的作用是激活有限自动机，即控制输入字符串在有限自动机上运行，一旦达到终态，即识别出lex源程序模式描述的某个单词，转去调用相应的动作部分就可以了
3 Yacc
生成语法分析器源码y.tab.c 存放LALR分析表
和包含了token的枚举定义的头文件y.tab.h
3.1 Yacc parser分为三部分
每段之间用**%%**隔开
3.1.1定义部分
- 和Lex的一样
- 例：
%{
/*
* 这是一个Yacc的定义部分
*/
#include <stdio.h>
%}
-
tokens
- 定义所有词法分析器可能传来的token
-
例：
%token INT CHAR ADD
3.1.2 语法规则部分
-
用一系列产生式描述语法规则
-
形如：
sentence: simple_sentence { printf("Parsed a simple sentence.\n"); } | compound_sentence { printf("Parsed a compound sentence.\n"); } ;- : 左侧为非终结符
- 右侧为产生式
- 产生式可有终结符和非终结符构成
- 可递归
- **{ }**放识别到特定语法时要执行的操作
- | 表示可有多条产生式
- ; 结束本条语法定义
-
yacc识别到定义的语法时会调用
yyparse()来重置状态并继续扫描 -
如果识别到未定义的文法，将调用
yyerror()来报错
3.1.3 子程序部分
-
此处的C代码将被放入
.y文件生成的文件名.tab.c里 -
可在此处重定义Yacc自带的函数，如
yyerror() -
例：
main() { do { yyparse(); } while(!feof(yyin)); } yyerror(s) char *s; { fprintf(stderr, "%s\n", s); }
3.2 Yacc中的函数
-
yyerror()错误处理函数，可以重写覆盖 -
yyparse()调用这个函数开始读入和解析，它会调用lex的yylex()函数
3.3 生成语法树
3.4 Yacc使用的自下而上的LALR(1)算法(Look Ahead LR)
3.4.1 自上而下和自下而上
- 自上而下语法分析:反复使用不同产生式推导以谋求与输入符号串相匹配
- 自下而上语法分析：对输入符号串对输入符号串寻找不同产生式进行归约，直到得到开始符号
3.4.2 LR分析器
- 规范归约的关键问题是找句柄
- LR分析法根据三方信息找句柄
- 历史:移进、归约的历史情况记录在下推栈内，可查阅
- 展望：预测句柄之后可能出现的信息
- 现实：读头下的符号
- LR分析器实际上是带有下推栈的确定有限自动机
- 状态：把一个"历史"和这个"历史"下的"展望"综合成一个抽象的状态
- 下推栈用于存放这些状态
- 栈顶信息可用于决定当前动作
- LR分析器的每一步动作可由栈顶状态和读头下符号唯一确定
- LR分析器的核心是分析表，包含动作(ACTION)表和转向(GOTO)表两部分
- LR分析器的总控程序根据表里的内容具体实施
- 分类：
| “历史” | “现实” | “展望” | 备注 | |
|---|---|---|---|---|
| LR(0) | √ | × | × | |
| SLR | √ | √ | × | 考虑了一点点现实 |
| LR(1) | √ | √ | √ | 向前展望一个符号，表格尺寸较大 |
| LALR(1) | √ | √ | √ | 简化了的LR(1)，表格尺寸缩小了 |
3.4.3 LALR(1)
对比LR(1)：
-
简化的LR(1)
-
表格尺寸大幅缩小，与SLR尺寸相同
-
能力：LR(1)>LALR(1)>SLR
基本思想：
- 同心项目集：LR(1)中的两个项目集去掉搜索项(展望)后是一样的
- 将LR(1)化简为LALR(1)就是将同心项目集合并
- 合并同心项目集时，以某种规则合并LR(1)的ACTION表和GOTO表的对应项，在此基础上构造一个尺寸与LR(0)分析表相同的分析表
- LALR(1)分析表不含多重定义项
构造LALR分析表时
- 如果归约与归约合并时不按同一文法归约，将造成冲突，因此LALR(1)能力弱于LR(1)
- 归约与出错合并时，人为规定为归约
- 其他情况没有冲突或不会出现
3.4.4 Note
由于Yacc使用的是LALR(1)算法，它不能识别过于模糊的语法，例如
- 需要向前看两个输入带上的单词才能确定的语法
- 同一个输入可以匹配多颗语法树的语法
3.5 Yacc自动生成LALR(1)分析表
3.5.1 构造LALR(1)分析表的主要步骤
- 构造文法的项目集族
- 把所有同心集合并到一起，生成新的集族
- 用新的集族构造 ACTION表
- 构造GOTO表
这些步骤手动完成很麻烦，自动化生成这样的表就变得很有必要
3.5.2 用--v选项生成.output文件来查看生成的表
以本次实验中的一个状态为例：
state 131
61 iteration_statement: FOR OPAIR expression_statement expression_statement . CPAIR statement
62 | FOR OPAIR expression_statement expression_statement . expression CPAIR statement
OPAIR shift, and go to state 21 //对应ACTION表的部分，读到终结符(时，(入栈，跳到状态21
CPAIR shift, and go to state 136
SELMIN shift, and go to state 22
SELADD shift, and go to state 23
NOT shift, and go to state 24
NUM shift, and go to state 25
IDENTIFIER shift, and go to state 26
constant_expression go to state 27 //对应GOTO表的部分，读到非终结符常量表达式时，转到状态27
expression go to state 137
unary_expression go to state 29
postfix_expression go to state 30
primary_term go to state 31
primary_expression go to state 32
4 编译运行Lex和Yacc
4.1 编译
bison -d -v --debug tinyC.y
flex tinyC.l
gcc -o tinyC tinyC.tab.c lex.yy.c -lfl -ly -LC:\GnuWin32\lib
-
-d
这个开关会生成一个
xxx.tab.h文件，存放tokens表，这个.h文件将被lex生成的lex.yy.c文件include -
-v
-
–debug
-
-lfl -ly
-
libfl是Flex的共享库 ,-lfl意思是编译时链接libfl库 -
liby是Yacc的共享库，-ly链接至liby库
-
-
-L 路径
例：
-LC:\GnuWin32\lib编译时如果报错找不到以上两个包，用这个可强制链接至所需的库
-
-o
生成可执行文件
4.2 运行结果
====begin parsing test.txt====
/* 111
this is comment
222 */
#include<stdio.h>
< INT, int > < ID, a > < ASSIGN, = > < NUM, 1 > < SC, ; >
< INT, int > < ID, f > < OPAIR, ( > < INT, int > < ID, a > < CPAIR, ) > < SC, ; >
< INT, int > < ID, main > < OPAIR, ( > < CPAIR, ) >
< OSP, { >
< INT, int > < ID, a > < ASSIGN, = > < NUM, 9 > < SC, ; >
< FLOAT, float > < ID, b > < ASSIGN, = > < NUM, 9.1 > < SC, ; >
< WHILE, while > < OPAIR, ( > < ID, a > < LT, < > < NUM, 10 > < CPAIR, ) > < OSP, { >
< ID, a > < SELADD, ++ > < SC, ; > hahahaha
< CSP, } >
< FOR, for > < OPAIR, ( > < SC, ; > < ID, b > < COMPARE, == > < NUM, 9.1 > < SC, ; > hahahaha< CPAIR, ) > < OSP, { >
< CSP, } >
< IF, if > < OPAIR, ( > < NUM, 1 > < CPAIR, ) > < OSP, { >
< CSP, } >
< RETURN, return > < NUM, 0 > < SC, ; >
< CSP, } >
< VOID, void > < ID, f > < OPAIR, ( > < INT, int > < ID, a > < CPAIR, ) >
< OSP, { >
< FLOAT, float > < ID, b > < ASSIGN, = > < NUM, 0.0 > < SC, ; >
< SWITCH, switch > < OPAIR, ( > < ID, a > < CPAIR, ) >
< OSP, { >
< CASE, case > < NUM, 0 > < COLON, : > < BREAK, break > < SC, ; >
< CASE, case > < NUM, 2 > < COLON, : > < BREAK, break > < SC, ; >
< DEFAULT, default > < COLON, : > < BREAK, break > < SC, ; >
< CSP, } >
< CSP, } >
****the file is end****
====end parsing====
Parse Tree:
start
|-->start
| |-->start
| | |-->start
| | | |-->start_part
| | | |-->extern_declaration
| | | |-->declaration
| | | |-->type_specifier
| | | | |-->INT
| | | |-->declarator
| | | | |-->direct_declarator
| | | | |-->IDENTIFIER
| | | | |-->ASSIGN
| | | | |-->expression
| | | | |-->primary_expression
| | | | |-->primary_term
| | | | |-->constant_expression
| | | | |-->NUM
| | | |-->SC
| | |-->start_part
| | |-->extern_declaration
| | |-->function_declaration
| | |-->type_specifier
| | | |-->INT
| | |-->IDENTIFIER
| | |-->OPAIR
| | |-->parameter_type_list
| | | |-->parameter_type_declaration
| | | |-->type_specifier
| | | | |-->INT
| | | |-->IDENTIFIER
| | |-->CPAIR
| | |-->SC
| |-->start_part
| |-->function_definition
| |-->type_specifier
| | |-->INT
| |-->IDENTIFIER
| |-->OPAIR
| |-->CPAIR
| |-->compound_statement
| |-->OSP
| |-->declaration_list
| | |-->declaration_list
| | | |-->declaration
| | | |-->type_specifier
| | | | |-->INT
| | | |-->declarator
| | | | |-->direct_declarator
| | | | |-->IDENTIFIER
| | | | |-->ASSIGN
| | | | |-->expression
| | | | |-->primary_expression
| | | | |-->primary_term
| | | | |-->constant_expression
| | | | |-->NUM
| | | |-->SC
| | |-->declaration
| | |-->type_specifier
| | | |-->FLOAT
| | |-->declarator
| | | |-->direct_declarator
| | | |-->IDENTIFIER
| | | |-->ASSIGN
| | | |-->expression
| | | |-->primary_expression
| | | |-->primary_term
| | | |-->constant_expression
| | | |-->NUM
| | |-->SC
| |-->statement_list
| | |-->statement_list
| | | |-->statement_list
| | | | |-->statement_list
| | | | | |-->statement
| | | | | |-->iteration_statement
| | | | | |-->WHILE
| | | | | |-->OPAIR
| | | | | |-->expression
| | | | | | |-->primary_expression
| | | | | | |-->primary_expression
| | | | | | | |-->primary_term
| | | | | | | |-->postfix_expression
| | | | | | | |-->unary_expression
| | | | | | | |-->IDENTIFIER
| | | | | | |-->binary_operation
| | | | | | | |-->LT
| | | | | | |-->primary_term
| | | | | | |-->constant_expression
| | | | | | |-->NUM
| | | | | |-->CPAIR
| | | | | |-->statement
| | | | | |-->compound_statement
| | | | | |-->OSP
| | | | | |-->statement_list
| | | | | | |-->statement
| | | | | | |-->expression_statement
| | | | | | |-->expression_list
| | | | | | | |-->expression
| | | | | | | |-->primary_expression
| | | | | | | |-->primary_term
| | | | | | | |-->postfix_expression
| | | | | | | |-->postfix_expression
| | | | | | | | |-->unary_expression
| | | | | | | | |-->IDENTIFIER
| | | | | | | |-->SELADD
| | | | | | |-->SC
| | | | | |-->CSP
| | | | |-->statement
| | | | |-->iteration_statement
| | | | |-->FOR
| | | | |-->OPAIR
| | | | |-->expression_statement
| | | | | |-->SC
| | | | |-->expression_statement
| | | | | |-->expression_list
| | | | | | |-->expression
| | | | | | |-->primary_expression
| | | | | | |-->primary_expression
| | | | | | | |-->primary_term
| | | | | | | |-->postfix_expression
| | | | | | | |-->unary_expression
| | | | | | | |-->IDENTIFIER
| | | | | | |-->binary_operation
| | | | | | | |-->COMPARE
| | | | | | |-->primary_term
| | | | | | |-->constant_expression
| | | | | | |-->NUM
| | | | | |-->SC
| | | | |-->CPAIR
| | | | |-->statement
| | | | |-->compound_statement
| | | | |-->OSP
| | | | |-->CSP
| | | |-->statement
| | | |-->selection_statement
| | | |-->IF
| | | |-->OPAIR
| | | |-->expression
| | | | |-->primary_expression
| | | | |-->primary_term
| | | | |-->constant_expression
| | | | |-->NUM
| | | |-->CPAIR
| | | |-->statement
| | | |-->compound_statement
| | | |-->OSP
| | | |-->CSP
| | |-->statement
| | |-->jump_statement
| | |-->RETURN
| | |-->expression
| | | |-->primary_expression
| | | |-->primary_term
| | | |-->constant_expression
| | | |-->NUM
| | |-->SC
| |-->CSP
|-->start_part
|-->function_definition
|-->type_specifier
| |-->VOID
|-->IDENTIFIER
|-->OPAIR
|-->parameter_type_list
| |-->parameter_type_declaration
| |-->type_specifier
| | |-->INT
| |-->IDENTIFIER
|-->CPAIR
|-->compound_statement
|-->OSP
|-->declaration_list
| |-->declaration
| |-->type_specifier
| | |-->FLOAT
| |-->declarator
| | |-->direct_declarator
| | |-->IDENTIFIER
| | |-->ASSIGN
| | |-->expression
| | |-->primary_expression
| | |-->primary_term
| | |-->constant_expression
| | |-->NUM
| |-->SC
|-->statement_list
| |-->statement
| |-->selection_statement
| |-->SWITCH
| |-->OPAIR
| |-->expression
| | |-->primary_expression
| | |-->primary_term
| | |-->postfix_expression
| | |-->unary_expression
| | |-->IDENTIFIER
| |-->CPAIR
| |-->statement
| |-->compound_statement
| |-->OSP
| |-->statement_list
| | |-->statement_list
| | | |-->statement_list
| | | | |-->statement
| | | | |-->labeled_statement
| | | | |-->CASE
| | | | |-->constant_expression
| | | | | |-->NUM
| | | | |-->COLON
| | | | |-->statement
| | | | |-->jump_statement
| | | | |-->BREAK
| | | | |-->SC
| | | |-->statement
| | | |-->labeled_statement
| | | |-->CASE
| | | |-->constant_expression
| | | | |-->NUM
| | | |-->COLON
| | | |-->statement
| | | |-->jump_statement
| | | |-->BREAK
| | | |-->SC
| | |-->statement
| | |-->labeled_statement
| | |-->DEFAULT
| | |-->COLON
| | |-->statement
| | |-->jump_statement
| | |-->BREAK
| | |-->SC
| |-->CSP
|-->CSP
请按任意键继续. . .