《编译与反编译技术》—第3章3.5节语法分析器的生成器
本节书摘来自华章出版社《编译与反编译技术》一书中的第3章,第3.5节语法分析器的生成器,作者庞建民,陶红伟,刘晓楠,岳峰,更多章节内容可以访问云栖社区“华章计算机”公众号查看。
3.5 语法分析器的生成器
本节介绍一个语法分析器的自动产生工具YACC(Yet Another Compiler-Complier),YACC通过输入用户提供的语言的语法描述规格说明,基于LALR(1)语法分析的原理,自动构造一个该语言的语法分析器。YACC源程序又称YACC规格说明,同LEX源程序类似,也由说明部分、翻译规则和辅助过程三部分组成,形式如下:
[说明部分]
%%
翻译规则
[%%
辅助过程]
其中,用方括号括起来的部分可以省略,但是翻译规则部分不能省略。下面通过一个例子来说明YACC源程序。
例3.42 构造一个简单的台式计算器,该计算器读入一个算术表达式,然后计算并打印它的值。该算术表达式文法的产生式为:
E→E+T | T
T→T*F | F
F→(E) | digit
其中,digit表示0~9的单个数字。根据这一文法写出的YACC源程序如下:
%{ # include ctype .h # include stdio.h % token DIGIT lines : expr \ n {printf ( "%d \ n",$1 ) ;} expr : expr + term {$$ = $1 + $3; } | term term : term *factor {$$ = $1 * $3; } | factor factor : ( expr ) {$$ = $2; } | DIGIT yylex ( ) { int c; c = getchar ( ); if ( isdigit (c) ) yylval =c-0 return DIGIT; return c; }
YACC源程序说明部分有任选的两部分:第一部分是处于“%{”和“%}”之间的部分,这里是一些普通的C语言的声明,在翻译规则或者辅助过程中用到的数据结构都需要在此进行声明。第二部分是文法记号的声明,一般以“%start S”的形式说明文法的开始符号,默认为第一条语法规则的左部符号。用 %token IF、DO、…、ID、… 的形式说明记号,记号被YACC赋予了不会与任何字符值冲突的数字值。
YACC源程序翻译规则部分中的每条规则由一个产生式和有关的语义动作组成。形如产生式A→α1 |α2 |…| αn,在YACC说明文件中写成
A : α1 { 语义动作1 }
| α2 { 语义动作2 }
…
| αn { 语义动作n }
;
在YACC产生式里用单引号括起来的单个字符,如c,是由终结符号c组成的记号,没有用引号括起来,也没有被说明成token类型的字母数字串是非终结符号。产生式左部非终结符之后是一个冒号,右部候选式之间用竖线分隔。在规则的末尾用“;”表示规则的结束。YACC语义动作是用C语言描述的语句序列,用“$$”表示与产生式左部非终结符号相关的属性值,用“$i”表示与产生式右部第i个文法符号相关的属性值。由于语义动作都是放在产生式右部的尾部,所以,每当用某一个产生式进行归约时,执行与之相关的语义动作。这样,可以在每个$i值都计算出来之后再求$$的值。比如,在本例的YACC源程序中,产生式E→E+T | T及其相关的语义动作表示为
expr : expr + term {$$ = $1 + $3; }
| term ;
在第一个产生式中,非终结符term是右部的第三个文法符号,“+”是第二个文法符号。第一个产生式的语义动作是把右部expr的值和term的值相加,把结果赋给左部非终结符expr作为它的值。第二个产生式的语义动作描述省略,因为当右部只有一个文法符号时,语义动作缺省就是表示值的复写,即它的语义动作是{$$ = $1; }。
YACC源程序辅助过程部分由一些C语言函数组成,其中必须包含名为yylex的词法分析器,其他过程则视需要而定。每次调用函数yylex()时,得到一个二元式的记号: 记号,属性值 。返回的记号必须事先在YACC说明文件的第一部分中用%token说明,属性值必须通过YACC定义的变量yylval传给分析器。
《编译与反编译技术实战 》一1.3 语法分析生成器YACC 。YACC(Yet Another Compiler Compiler)是一个经典的语法分析生成器。YACC最初是由AT&T公司的Steven C. Johnson为UNIX操作系统开发的,后来一些兼容的程序如Berkeley YACC、GNU Bison、MKS YACC和Abraxas YACC陆续出现,它们都是在此基础上做了少许改进或者增强,但是基本概念是相同的。
《编译与反编译技术实战 》一 1.2 词法分析生成器LEX LEX是LEXical compiler的缩写,是UNIX环境下非常著名的工具,主要功能是生成一个词法分析器的C源码,描述规则采用正则表达式。描述词法分析器的文件*.l经过LEX编译后生成一个lex.yy.c的文件,然后由C编译器编译生成一个词法分析器。
相关文章
- 光谱分析技术是如何改变了 天文学、化学以及物理学的?
- 【分布式空时编码+LDPC】协作MIMO中分布式空时编码和LDPC编译码技术的仿真
- 基于ANFIS的有色噪声抵消技术
- 【德勤重磅】2016年度科技趋势之区块链技术(134pdf下载)
- 《编译与反编译技术》—第1章1.6节编译的前端和后端
- 《编译与反编译技术》—第1章1.7节C语言程序的编译流程
- 《编译与反编译技术》—第2章2.1节词法分析器的需求分析
- 《编译与反编译技术》—第2章2.6本章小结
- 《编译与反编译技术》—第3章3.3节自上而下的语法分析
- 《编译与反编译技术实战 》一1.9 动态分析工具TEMU
- 《编译与反编译技术实战 》一2.2 编译器的结构
- 《编译与反编译技术实战 》一3.4 本章小结
- CSDN日报20170425 ——《私活,是对技术达人最好的点赞》
- Python爬虫技术--基础篇--面向对象高级编程(上)
- react 前端项目技术选型、开发工具、周边生态
- 《圣殿祭司的ASP.NET4.0专家技术手册》---- 1-13 ClientBuilderManager类别的编译功能
- 《编译与反编译技术实战》——1.3 语法分析生成器YACC
- 利用自定义分页技术提高数据库性能
- 北京大学建立大数据分析与应用技术国家工程实验室
- 大数据技术正全面重塑芯片方案
- 专家:大数据等新技术助力信息融合