《编译与反编译技术》—第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源程序如下：

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是右部的第三个文法符号，“+”是第二个文法符号。第一个产生式的语义动作是把右部expr的值和term的值相加，把结果赋给左部非终结符expr作为它的值。第二个产生式的语义动作描述省略，因为当右部只有一个文法符号时，语义动作缺省就是表示值的复写，即它的语义动作是{$$ = $1； }。

yacc源程序辅助过程部分由一些c语言函数组成，其中必须包含名为yylex的词法分析器，其他过程则视需要而定。每次调用函数yylex()时，得到一个二元式的记号：<记号，属性值>。返回的记号必须事先在yacc说明文件的第一部分中用%token说明，属性值必须通过yacc定义的变量yylval传给分析器。