我是靠谱客的博主 愤怒纸鹤,这篇文章主要介绍LEX&&YACC--编译界的神,现在分享给大家,希望可以做个参考。

最近研究lex&&yacc,记录并总结一些重要的概念和解释。
lex&&yacc是gnu开源的全文解析工具,lex用于词法解析,yacc用于语法解析。lex一般也称为token scanner/lexer,yacc称为parser generator(语法解析器生成器)。
lex&&yacc这两个工具已经很老了,现代版本的工具为flex&&bison。两个工具可以结合使用,也可以只使用bison。

基本原理

lex词法解析,使用正则表达式进行匹配,你可以写入正则表达式到lex文本中。
yacc语法解析,学过编译原理的人可能比较熟悉上下文无关文法,巴科斯范式,LR(1),LALR(1)等概念。yacc内部其实就是实现了一个状态机。其执行过程,就是借助状态机和栈来不断地将规则文本进行归约的过程。

归约和移进是lex&&yacc中比较重要的概念,官方文档中使用的是shift/reduce这两个单词,shift表示移进,reduce表示归约。在编写完语法规则后,使用yacc/bison编译,可能会出现一些shift/reduce conflict,即移进归约冲突。这时候,你需要仔细确认自己写的语法规则,其中就存在一些语义上的错误,需要进行修改。

命令介绍

这里讨论flex&&bison,旧版类似。
编写的词法文件后缀一般是.l,语法文件后缀是.y。这里假设你写了一个sql的语法解析工具:
词法文件为sql.l,语法文件为sql.y。(当然,你也可以仅使用语法解析。)

复制代码
1
2
3
4
5
6
flex sql.l             # 生成C语言版本的词法解析源代码 flex -+ sql.l          # 生成C++版本的词法解析源代码 bison sql.y            # 仅生成一个C语言版本的语法解析源代码,不会导出头文件给其它源码引用 bison -d sql.y         # 功能同上,但是会导出头文件给其他源码引用 bison -L c++ -d sql.y  # 生成C++版本的语法解析源码 gcc *.c -o parser      # 编译

上述命令如果不使用-o选项给输出文件取名,那么执行成功后会生成以下文件:
C语言版本
词法文件为lex.yy.c
语法文件为sql.tab.c,sql.tab.h
C++版本
词法文件为lex.yy.cc
语法文件为sql.tab.cc,sql.tab.h

官方实例与文档

官方文档地址为: http://dinosaur.compilertools.net/
有lex,yacc,flex,bison和相关工具的实例与文档。如果有需要,可以查阅文档。

重要概念

token: 词法解析出的结果,一般是yylex函数return给语法解析的返回值,一般在.y文件中使用%token定义的符号,本质上会被编译成一个int值,给程序识别。yylex函数返回的就是这个int值。
shift/reduce: 移进/归约,移进就是规则解析未结束,继续向栈中推入一个符号。
terminal: 终结符,语法规则一般就是终结符和非终结符构成的,非终结符最终还是由终结符构成。
nonterminal: 非终结符
rule: 语法规则
precedence: 优先级,出现shift/reduce conflict时,需要定义该规则归约的优先级
action: 动作。词法和语法文件中,跟在词法或语法规则后面的一段C/C++代码,会在解析到该词法或语法规则后立马执行这些代码。多行代码使用{}括起来。

词法语法文件格式

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
%{ // 在这里写C/C++程序代码,一般是程序模块的引入,和类型或函数的声明与定义 // #include <stdio.h> // C语言版本 // #include <iostream> // C++版本 // extern int yylex(); // 语法文件中,需要声明一个名为yylex的词法解析函数(这个函数的任务是帮语法模块进行词法解析) %} // 这部分写词法或语法解析自身的一些声明及定义 // 如语法解析的token定义 %token LPAREN // 定义左括号的token %token RPAREN // 定义右括号的token %token KEYWORD_SELECT // 定义关键字select的token // 声明优先级,后声明的优先级高,除了%left左结合,还有%right, %nonassoc可以来定义优先级 %left "+" "-" %left "*" "/" // 这里你可以使用上面定义的token,也可以使用未定义的token,来代表声明一个虚拟符号,来代表这个层次的优先级。 // 声明一个虚拟优先级符号后,使用%prec将虚拟符号插入到语法规则的末端,那么该语法规则的优先级就是该虚拟符号的优先级了。 // 这里说明一下,一个语法规则的优先级,一般就是规则中最后一个终结符的优先级,而终结符一般就是token定义的符号。 %union { char* ycText; // 这里可以使用union命令定义需要从词法传入到语法解析模块的具体内容,ycText在词法模块中赋值 } // union命令本质上会在源码中生成一个叫YYTYPE的联合体类型,在语法模块中会有YYTYPE yylval这个变量定义,extern到词法文件中,对其ycText成员进行赋值。那么在语法文件中就可以访问到这个具体的字符串了。当然上面的token声明需要修改一下 %token <ycText> KEYWORD_SELECT // 除了字符串类型,还可以是int等其他类型,但需要使用代码在词法的action中进行转化 %start root // 生命一下语法规则的起始规则,具体的root规则在下面定义。不使用start命令,yacc也会从第一条规则进行解析。 %% // 词法和语法文件的主体部分,词法就写解析的词法及其附带的action(动作) root: KEYWORD_SELECT tail {/* 动作代码,这里假装输出select这个词,使用$1引用,yacc编译器后期会把$1替换成具体的栈上变量 */printf("%sn",$1);} ; // 别忘记使用分号注明root规则结束 // 如果规则有多种情况,使用‘|‘符号分多种规则情况 // 这里,root其实就是一个nonterminal,而KEYWORD_SELECT是一个terminal。tail也是nonterminal,因为下面还是要对它进行定义。 // 规则定义时,尽量使用左递归的写法,右递归会出现很多未知情况,除非你知道他们的意义,否则还是使用左递归 // 另外,介绍一下$$,这个可以给非终结符进行赋值,具体使用可以参考官方文档 %% // 这里一般写C/C++代码,一般是一些函数的具体实现 // 词法模块一般需要定义一个yywrap函数 int yywrap() {return 1;} // yywrap函数的作用请查阅文档,不定义该函数,gcc编译源码时会报错

工具使用说明

在编写词法语法文件时需要明确几点:
一般过程是,将文本通过标准输入(stdin)传入程序,先经过词法分析模块,后将词法分析结果传入语法解析模块,然后循环该过程。

语法解析需要定义并实现如下函数:

复制代码
1
2
int yylex(); // 词法解析函数,如果是c语言版本的,那么词法文件编译成源码后,里面就自带一个yylex的c语言函数。这时候,你仅需要在语法文件的头部声明一下外部的函数即可。 void yyerror(char* msg) {printf("error : %sn", msg);}; // 错误处理函数

语法模块生成的头文件,需要在词法文件的头部引入:

复制代码
1
2
3
%{ #include "sql.tab.h" // 因为里面包含了yylex要返回的token值,这个值要传给语法解析模块 }%

词法解析模块,内部需要定义yywrap函数。

最后,你需要自己写一个main函数,条用语法解析的yyparse函数进行全文解析。

最终词法和语法文件大概的样子:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// sql.l文件内容 %{ #include <stdio.h> #include <sql.tab.h> extern YYTYPE yylval; }% %% "select" {yylval.ycText = yytext;return KEYWORD_SELECT;} %% int yywrap() {return 1;} // sql.y文件内容 %{ #include <stdio.h> extern int yylex(); void yyerror(char* msg) {printf("error : %sn", msg);} }% %union { char* ycText; } %token <ycText> KEYWORD_SELECT %start root %% root: KEYWORD_SELECT {printf("%sn", $1);} ; %% int main(int , char** ) {yyparse();return 0;}

总结

关于lex&&yacc的使用,还有很多需要注意的,尽量还是查看官方文档。

最后

以上就是愤怒纸鹤最近收集整理的关于LEX&&YACC--编译界的神的全部内容,更多相关LEX&&YACC--编译界内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(99)

评论列表共有 0 条评论

立即
投稿
返回
顶部