编 译 原 理
实
验
指
导
书
前 言
编译原理是计算机科学与技术、软件工程等专业的主干课和必修课，由于这门课程相对抽象且内容较复杂，一直是比较难学的一门课程。在编译原理的学习过程中，实验非常重要，只有通过上机实验，才能使学生对比较抽象的课程内容产生一个具体的感性认识。
本书实验环境主要为C环境及一个词法分析器自动生成工具FLEX和一个语法分析器自动生成工具BISON。书中给出的参考源程序也是C源程序，但由于实验者熟悉精通的语言工具不尽相同，因而强求采用统一的编程语言编程是不现实的。实验者在掌握了编译程序各个阶段的功能和原理之后，不难借助使用其他自己熟悉的语言实现相关功能。
实验者在实验过程中应该侧重写出自己在算法分析、设计思路、实现功能或程序代码等方面的特色，写出设计和实现过程中遭遇到的难点和解决办法，可以不拘泥于实验指导给出的参考性设计思路，尽可能在深度和广度上加以拓展。只有这种各具特色的实验报告，才将更有利于体现实验者在创新思维和动手能力上的差异。
通过这些实验，能使学生对这些部份的工作机理有一个详细的了解，达到“知其然，且知其所以然”的目的。并可在C环境下对自动生成工具生成的词法、语法分析器进行编译调试。
由于手工生成词法和语法分析器的工作量太大，在实际中常用自动生成工具来完成之。这些工具中最著名的当属贝尔实验室的词法分析器生成工具LEX和语法分析器生成工具YACC。它们现已成为UNIX的标准应用程序同UNIX一起发行。与此同时GNU推出与LEX完全兼容的FLEX，与YACC完全兼容的BISON。这两个程序都在Internet上以源代码的形式免费发行，所以很容易在其它操作系统下重新编译安装。我们实验采用的就是for dos的FLEX和BISON。本书有关的编译工具及其源程序例子，可到BISON的网站上下载。关于FLEX和BISON的用法简介，参见附录，如需更详细的介绍，请参阅编译工具中帮助文件。
目 录
实验一 词法分析器**的设计**
【实验目的】
1． 掌握生成词法分析器的方法，加深对词法分析原理的理解。
2． 掌握设计、编制并调试词法分析程序的思想和方法。
3． 本实验是高级语言程序设计、数据结构和编译原理中词法分析原理等知识的综合。
【实验性质】
综合性实验（学时数：2H）
【实验内容及要求】
1． 设计并实现一个四则运算的计算器,通过命令行方式启动,可以通过键盘输入整个算式,然后直接显示结果。将换行作为分隔符，把输入分隔为一个个算式。
2． 使用C语言设计、编写、调试一个词法分析子程序。
3． 实验前请仔细阅读实验预习提示，已经附有完整的源代码,请在实验报告中画出该分析器所实现的状态转换图。
4． 提交的实验报告中要有实验名称、实验目的、实验内容、实验程序清单、调试过程和运行结果，程序的主要部分做出功能说明，并有实验收获体会或改进意见等内容。
5． 进阶实验:扩展原有计算器,使其可以支持括号和负数运算。
6． 本实验建议学时数为2学时
【实验预习提示】
1.词法分析器的功能和输出格式
词法分析器的功能是输入以字符串表示的源程序，输出单词符号或单词符号序列。词法分析器的单词符号常常表示成以下的二元组(单词的种别码，单词符号的属性值)。本实验是用于计算器的词法分析器，只需处理运算符和数值。
2.“超前搜索”方法
词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“a>+”,当前字符为’>’，此时，分析器倒底是将其分析为大于关系运算符还是大于等于关系运算符呢？显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符’+’，这时可知应将’>’解释为大于运算符。但此时，超前读了一个字符’+’，所以要回退一个字符，词法分析器才能正常运行。
3.词法分析程序主程序的算法思想
算法的基本思想是根据扫描到单词符号的第一个字符的种类，拼写出相应的单词符号，其实现的基本任务是从字符串表示的源程序中识别出相应的具有独立意义的单词符号。主程序示意图如图1.1所示。
 |
图1.1 词法分析主程序示意图
4.补充知识:
(1)避免重复包含。在头文件token.h中，有这样的代码段：
#ifndef TOKEN_H_INCLUDED
#define TOKEN_H_INCLUDED
…
#endif
这是为了防止多次用#include包含引起多重定义错误而采用的技巧。头文件用#include包含自己所依赖的其他所有头文件，可以让代码中只需书写一次include,且当依赖关系发生改变时较容易修改。但如果多个头文件这样书写，会报类型或宏的重复定义错误，一次可以采用这个技巧，根据开头的#ifndef语句，避免产生多重定义的错误。
(2)在执行语句sscanf(token->str,”%lf”,&token->value);时，会出现null pointer assignment错误，这是因为没有给指针初始化。
5.参考源程序
实验二 用递归下降法实现语法分析
【实验目的】
1.掌握用递归下降分析法进行语法分析的方法。加深对自顶向下语法分析原理的理解。
2.掌握设计、编制并调试自顶向下语法分析程序的思想和方法。
3.本实验是高级语言程序设计、数据结构和编译原理中词法分析、自顶向下语法分析原理等知
识的综合。由于语法分析是在词法分析的基础上进行的，且词法分析器输出的结果即单词符号
或单词符号序列是语法分析的输入。
【实验性质】
综合性实验（学时数：2H）
【实验要求】
\1. 调用实验一的get_token函数进行词法分析，使用递归下降法作语法分析器，实现计算器的功能。
\2. 实验前请仔细阅读实验预习提示，参考所附完整的源代码,请在实验报告中写出该分析器所使用的语法规则。
\3. 本实验建议学时2学时。
【实验预习提示】
1、 语法分析程序的算法思想
（1） 主程序示意图如图4.1所示。
 |
图4.1 递归下降法语法分析主程序示意图
（2） 递归下降分析程序示意图如图4.2所示。
 |
图4.2 递归下降分析程序示意图
2.参考源程序parser.c：
实验三 熟悉FLEX使用方法
【实验目的】
1． 掌握FLEX基本使用方法
2． 掌握如何将通过FLEX生成的C语言模块加入到自已的程序中
【实验要求】
1．编制FLEX源程序,分别统计文本文件a.txt中出现的标识符和整数个数,并显示之。标识符定义为字母开头，后跟若干个字母，数字或下划线。整数可以带+或-号，也可不带，且不以0开头。非单词和非整数则忽略不记，将之滤掉不显示。
2．编制一FLEX源程序,分别求出文件hh.c中字母,数字,回车符的个数。
3． 思考：若main函数不在FLEX中实现，应该如何实现？
4． 本次实验建议学时2学时。
【实验预习提示】
参见附录一。在看懂的基础上将之调试通过。
实验四 用FLEX和BISON自动**实现计算器**
【实验目的】
熟练掌握FLEX和BISON，并通过其生成词法和语法分析器，实现实验一和实验二的加算器功能
【实验要求】
1． 通过FLEX生成一词法分析器函数，其功能同实验一中词法分析器函数类似。
2． 通过BISON生成一语法分析器。参造附录，读懂所附源程序。
3． 生成一工程文件，调用1和2中生成的函数，实现计算器的功能
4． 本实验建议学时2学时。
【实验预习提示】
1． 由于FLEX生成的C程序模块lex.yy.c过于复杂，基本不可读，所以不要直接修改它，可将它看成一个“黑箱”，即不需要清楚知道其内部结构，只需要知道其接口即可。可通过修改FLEX源程序间接修改之。关于lex.yy.c中常用变量和函数，在附录中有详细说明。
2． 编制语法分析器mycalc.y，通过BISON生成y.tab.c和y.tab.h。命令为：
bison –yacc –dv mycalc.y
使用BISON代替了YACC,默认生成的文件是mycalc.c和mycalc.h，所以在添加了—yacc参数，可以生成与YACC同名的文件
3． 编制词法分析器mycalc.l，通过FLEX生成lex.yy.c。命令为：
flex mycalc.l
4． 生成一工程文件，不妨取名为test.prj，将文件lex.yy.c、y.tab.c和y.tab.h，加入之。源程序参考如下：
(1) mycalc.l
附录一 词法分析器生成工具FLEX简介
1． FLEX简介
单词的描述称为模式(Lexical Pattern)，模式一般用正规表达式进行精确描述。FLEX通过读取一个有规定格式的文本文件，输出一个如下所示的C语言源程序。
FLEX的输入文件称为LEX源文件，它内含正规表达式和对相应模式处理的C语言代码。LEX源文件的扩展名习惯上用.l表示。FLEX通过对源文件的扫描自动生成相应的词法分析函数 int yylex()，并将之输出到名规定为lex.yy.c的文件中。实用时，可将其改名为lexyy.c。该文件即为LEX的输出文件或输出的词法分析器。也可将 int yylex()加入自已的工程文件中使用。
2． 模式简介
LEX的模式的格式(也称为规则)是机器可读的正规表达式，正规表达工是用连接、并、闭包运算递归生成的。为了方便处理，LEX在此基础上增加了一些运算。下列是按运算优先级由高往低排列的LEX的正规表达式的运算符。
“[]^-?.*+|()/${}%<>
关于LEX的模式定义，可参见下页附表1.1
3．LEX源文件格式
LEX对源文件的格式要求非常严格，比如若将要求顶行书写的语句变成非顶行书写就会产生致命错误。而LEX本身的查错能力很弱，所以书写时一定要注意。
LEX的源文件由三个部份组成，每个部分之间用顶行的“%%”分割，其格式如下：
定义部份
％％
规则部份
％％
用户附加C语言部份
3.1定义部份
定义部份由C语言代码、模式的宏定义、条件模式的开始条件说明三部份组成。
其中，C代码部份由顶行的%{和}%引入，LEX扫描源文件时将%{和}%之间的部分原封不动的拷贝到输出文件lex.yy.c中.
附表1.1 LEX 的模式定义
| 模 式 | 解 释 | |
|---|---|---|
| X | 匹配单个字符x。(也可将模式写为”x”) | |
| . | 匹配除换行符’\n’之外的任意字符 | |
| [xyz] | 匹配x、y或z | |
| [abj-oZ] | 匹配字符集:a、b、Z以及j到o之间的字母(包括j和o) | |
| [^A-Z] | 匹配字符集A到Z之间字符集的补集。即除大写字母的其它字符 | |
| [^A-Z\n] | 匹配除大写字母和换行符之外的其它字符 | |
| r* | R是正规表达式，r*匹配0个或多个r | |
| r+ | R是正规表达式，r+匹配1个或多个r | |
| r? | R是正规表达式，r?匹配0个或1个r | |
| r{2,5} | R是正规表达式，r{2,5}匹配2个到5个r | |
| r{2,} | R是正规表达式，r{2,}匹配2个或以上r | |
| r{4} | R是正规表达式，r{4}匹配4个r | |
| {name} | name是在定义部份出现的模式宏名，在规则部份将之替换为模式 | |
| “[xyz]\”foo” | 匹配字符串[xyz]”foo | |
| \x | 如x是’a’、’b’、’f’、’n’、’r’或’t’，\x为转义字符，定义同ANSI C,否则，匹配字符x.此方法用于匹配正规表达式的运算符 | |
| \123 | 匹配八进制ASCII码为123的字符 | |
| \x2a | 匹配十六进制ASCII码为2a的字符 | |
| (r) | 匹配r,优先运算正规式r | |
| Rs | 匹配正规式r和s的连接 | |
| r\ | s | 匹配正规式r或s |
| r/s | 匹配正规式r,但是，r之后一定要出现正规式s。称s为r的尾部条件 | |
| ^r | 匹配正规式r,但是，r一定要出现在行首 | |
| r$ | 匹配正规式r,但是，r一定要出现在行尾 | |
| 匹配正规表达式r,但是一定要在开始条件s激活之后 | ||
| < |
匹配文件结束标志 |
模式的宏定义部份如同C语言中的宏定义，通过宏名定义一个模式，这样，可以简化在源文件中多次出现的正规表达式的书写。格式为：
宏名1 宏定义1
宏名2 宏定义2
……
例如：
DIGIT [0-9]
ID [A-Za-z][A-Za-z0-9_]*
宏名是以字母和下划线”_”开始，以字母、数字和下划线组成的字符串，且大小写敏感。宏名必须顶行写，宏名和宏定义必须写在同一行上。宏名和宏定义之间以不包括换行符的白字符(空格符、TAB符、换行符)隔开。
条件模式的开始条件说明格式如下：
％start s1 s2 s3
其中，s1、s2、s3为条件名。必须为大小写敏感的标识符。关于条件模式的使用，我们将在后面作说明。
3.2 规则部份
规则部份是LEX源文件的核心部份，它包括一组模式和在生成分析器识别相应模式后对相应模式进行处理的C语言动作(Action)。格式如下
C语言代码
模式1 动作1
模式2 |
模式3 动作3
……
同定义部分一样，C语言代码必须出现在第一个模式之前，包括在%{和}%之中，且%{必须顶行书写。%{和}%之间的代码部份可用来定义yylex()用到的局部变量。
模式必须顶行书写。模式可为正规式或用{}括起且在定义部份定义过的宏名。动作为用{}括起的C代码。且开始括号{与模式之间用白字符隔开，且须和模式在同一行上。注意，在模式后加一|表示模式2和3采用同一动作3.|和模式2以白字符隔开。
3.3用户附加C语言部份
LEX对此部份不作任何处理，仅仅将之直接拷贝到输出文件lex.yy.c的尾部。在些部份，可定义对模式进行处理的C语言函数、主函数和yylex要调用的函数yywrap()等。如果用户在其它C模块中提供这些函数，用户代码部份可以省略。
3.4 源文件格式小结
综上所述，LEX源文件详细格式如下：
%{
/此模块为定义模块中Ｃ语言代码部份，在下面填入相应C代码/
}%
模式宏名1 模式1
模式宏名2 模式2
……
%start s1 s2 s3
%%
%{
/此模块为规则模块中Ｃ语言代码部份，在下面填入相应C代码/
}%
模式1 动作1
模式2 动作2
……
%%
/此模块为用户附加C语言部份，在下面填入相应C代码/
注意：以上三部份及其中任何一子部份，均可省去。且如无第三部分，第二个%%也可省去，但第一个%%决不可省。
４．LEX的工作原理
LEX通过对源文件的扫描，经过宏替换后，将规则部份的正规表达式转换成与之相应的DFA，并由之产生一个名为int yylex()的词法分析函数，将之拷贝到输出文件lex.yy.c中。由于考虑到C代码的可移植性和运行效率问题，lex.yy.c中大量使用了宏定义，且文件较大(30-50kb)。因此，几乎是不可读的。但是，其可移植性相当好。
lex.yy.c中定义了很多用户可定义的全局变量，以及在LEX源文件的动作中可调用的函数和宏。但是，由于lex.yy.c太过复杂，建议初学者不要随意修改它。用户在了解其的前提下，可在其它C模块中引用之。
５．二义性问题的解决
yylex()函数被调用之后，它首先检查全局文件指针变量yyin是否有定义，如有，则将之设置为将要扫描的文件指针。如无，则设置为标准输入文件stdin.同理，如全局文件指针变量yyout无定义，则将之设置为标准输出文件stdout。
若有多个模式与被扫描文件中的字符串相匹配，则yylex()执行能匹配最长字符串的模式，称为“最长匹配原则”；若还有多个模式匹配长度相同的字符串，则yylex()选择在LEX源文件中排列最前面的模式进行匹配，称为“最先匹配原则”。yylex()常通过超前搜索一个字符来实现这样的原则，如果使用超前搜索匹配了某一模式，则yylex()在进行下一次分析前，将回退一个字符。见下例：
%%
program {printf(“keyword:%s!\n”,yytext); /模式一/}
procedure {printf(“keyword:%s!\n”,yytext); /模式二/}
[a-z][a-z0-9] {printf(“identifier:%s!\n”,yytext); /模式三*/}
%%
如输入串为”programming”，yylex()分析到子串”program”时，有模式一和三可以匹配，但根据最长搜索原则，发现在继续读入输入串时，还可匹配模式三。这样，将输出”identifier:programming!”。如输入串为”program”,则按最先匹配原则，模式一与之匹配，输出”keyword:program!”。注意，若将模式一和模式三在源文件中次序弄反，则模式一永远也得不到匹配。
若无模式可匹配输入串，则使用缺省规则，即将输入串原样拷贝至输出文件yyout中。
６．常用全局变量和宏
lex.yy.c中常用全局变量、函数和宏很多，在此仅指出一些最常用的，若需要更详细信息，请阅读源文件。
(1) FILE yyin,yyout:为指向字符输入和结果输出文件的指针。如用户未对其定义，则设为标准输入文件stdin和stdout。
(2) int yylex():为词法分析程序，它自动移动文件指针yyin和yyout。在定义模式动作时，用户可用return语句结束yylex(),return 必须返回一整数。由于yylex()的运行环境都是以全局变量的方式保存，因此，在下一次调用yylex()时，yylex()可从上次扫描的断点处继续扫描，在语法分析时，可利用这一特性。若用户未定义相应的return语句，则yylex()继续分析被扫描的文件，直到碰到文件结束标志EOF。在读到EOF时，yylex()调用int yywrap()函数(该函数用户必须提供)，若该函数返回非0值，则yylex()返回0而结束。否则，yylex()继续对yyin指向的文件扫描。
(3) char *yytext:存放当前被识别的词形。
(4) int yyleng:存放字符串yytext的长度。
(5) int yywrap():参见(2)
(6) yymore()：将当前识别的词形保留在yytext中，分析器下次扫描时的词形将加追加在yytext中。例模式定义如下
……
hello {printf(“%s!”,yytext);yymore();}
world {printf(“%s!”,yytext);}
……
当输入串为”helloworld”时，将输出”hello!helloworld!”
(7) yyless(int n):回退当前识别的词形中n个字符到输入中
(8) unput(char c):回退字符c到输入，它将作为下一次扫描的开始字符
(9) input():让分析器从输入缓冲区中读取当前字符，并将yyin指向下一字符
(10) yyterminate():中断对当前文件的分析，将yyin指向EOF。
(11) yyrestart(FILE * file):重新设置分析器的扫描文件为file
(12) ECHO:将当前识别的字符串拷贝到yyout
(13) BEGIN:激活开始条件对应的模式
(14) REJECT:放弃当前匹配的字符串和当前的模式，让分析器重新扫描当前的字符串，并选择另一个最佳的模式再次进行匹配。
7.条件模式
LEX提供控制模式在一定状态下使用的功能，称为条件模式。LEX首先在定义部份通过%start来定义条件句。在规则部份可通过宏
BEGIN 条件名 来激活条件。BEGIN INITIAL或BEGIN 0将休眠所有的条件模式，使分析器回到开始状态。
例：将输入文件中的单词”magic” 作如下处理：识别”magic”时，如”magic”所在行行首为字符’a’,则输出”first”;若为’b’,则输出”second”;否则，输出”magic”。如不用条件模式，LEX源文件可这样写：
%{int flag;}%
%%
^a {flag=’a’;ECHO;}
^b {flag=’b’;ECHO;}
\n {flag=0;ECHO;}
magic {
switch(flag)
{
case ‘a’:printf(“first”);break;
case ‘b’:printf(“second”);break;
default :ECHO;break;
}
}
%%
如使用条件模式,则上述源文件可简化为
%start AA BB CC
%%
^a {ECHO;BEGIN AA;}
^b {ECHO;BEGIN BB;}
\n {ECHO;BEGIN 0;}
%%
8．示例
例一：编制LEX源程序,分别统计文本文件a.txt中出现的标识符和整数个数,并显示之。标识符定义为字母开头，后跟若干个字母，数字或下划线。整数可以带+或-号，也可不带，且不以0开头。非单词和非整数则忽略不记，将之滤掉不显示。
设LEX源文件名为count.l.文件内容如下
%{
#include “stdio.h”
#include “stdlib.h”
int num_num=0,num_id=0;
%}
INTEGER [-+]?[1-9][0-9]*
ID [a-zA-Z][a-zA-Z_0-9]*
SPACE [ \n\t]
%%
{INTEGER} { num_num++;
printf(“(num=%d)”,atoi(yytext));//打印数字值
/数字数加一/
}
{ID} {
num_id++;
printf(“(id=%s)”,yytext);
}
{SPACE} |
. {
//什么也不做,滤掉白字符和其它字符
}
%%
void main()
{
yylex();
printf(“num=%d,id=%d”,num_num,num_id);
}
int yywrap()//此函数必须由用户提供
{return 1;}
设count.l所在目录为c:\test，且已用path命令指定flex.exe所在目录。则调用命令
c:\test> flex count.l后可在c:\test目录下得到一文件lex.yy.c，打开C环境，新建工程文件my.prj(TURBOC 或BORLAND C下后缀为.prj，VC下后缀为.dsw),将lex.yy.c加入工程文件中,编译运行可得可执行文件my.exe.若需分析从标准输入中输入的字符串,运行my.exe即可.若需分析放在其它文件中的串,如设在文件hello.txt中,则运行my.exe<hello.txt即可.
例2:编制一LEX源程序,分别求出文件hh.c中字母,数字,回车符的个数.源程序如下:
%{
#include “stdio.h”
#include “stdlib.h”
int num_digit=0,num_letter=0,num_enter=0;
%}
DIGIT [0-9]
LETTER [A-Za-z]
%%
{DIGIT} {num_digit++;}
{LETTER} {num_letter++;}
\n {num_enter++;}
. {/其它字符不作处理/}
%%
void main()
{
yyin=fopen(”hh.c”,r);
yylex();
printf(“num=%d,letter=%d,enter=%d”,
num_digit,num_letter,num_enter);
}
int yywrap()//此函数必须由用户提供
{
return 1;
}
附录二 语法分析器生成工具YACC简介
1．YACC简介
YACC是语法分析器生成工具中最著名的，也是最早开发出来的一个。该工具和LEX都是源于贝尔实验室的UNIX计划，如今YACC也成为了UNIX系统的标准实用程序。它大大地简化了在语法分析器设计时的手工劳动，将程序设计语言编译器的设计重点放在语法制导翻译上来，从而方便了编译器的设计和对编译器代码的维护。Berkeley大学开发了和YACC完全兼容，但代码完全不一样的语法分析器生成工具BYACC，GNU也推出了和YACC兼容的语法分析器生成工具BISON，这也是我们实验时使用的工具，通过这个软件，我们可以学习YACC。
语法分析是对输入文件第二次重组，输入文件是有序的字符串，词法分析是第一次重组，即将有序的字符串转换成单词序列；而语法分析则是在第一次重组的基础上将单词序列转换为语句，它使用的是上下无关文法的形式规则。正如我们所知，一般的程序设计语言的形式方法大多是LALR（1）文法，它是上下无关文法的一个子类。多数程序设计语言的语法分析都采用LALR（1）分析表，YACC也正是以LALR（1）文法为基础。类似于LEX，它通过对输入的形式文法规则进行分析产生LALR（1）分析表，输出以该分析表驱动的语法分析器C语言源程序。YACC的输入文件称为YACC 源文件，它包含一组以巴克斯-鲁尔范式（BNF）书写的形式文法规则以及对每条规则进行语义处理的C语言语句。YACC源文件的文件后缀名一般用.y表示。YACC的输出文件一般有两个，在BISON下：一个是后缀为.c的包含有语法分析函数int yyparse()的C语言源程序xxx.tab.c(其中xxx是源文件的文件名)，称为输出的语法分析器；另一个是包含有源文件中所有终结符(词法分析中的单词)编码的宏定义文件xxx.tab.h(当BISON加参数-d时生成)，称为输出的单词宏定义头文件。
2．YACC的源文件格式
YACC的源文件部分由三个部分组成，即
定义部分
%%
语法规则部分
%%
用户附加C语言代码部分
不象LEX对源文件格式有严格的要求，任何YACC指令都可以非顶行书写。在介绍YACC源文件格式之前，先来回顾有关形式语法的基本概念。
(1) 单词和非终结符。
在YACC源文件中，有两种方式表示的单词（终结符）：一种是在定义部分通过YACC指令%token定义文法中出现的单词，称为有名单词，如%token NUMBER就定义了一有名单词NUMBER，可用它来表示整数的种别码；另一种是单个字符，称为字符单词，如单个字符’+’、’-’,’a’,’4’,’!’等，它们本身作为终结符出现在规则部分，不需要在定义部分说明，可直接加单引使用，如同C语言的字符常量。
非终结符一般为不加引号的标识符，习惯上用小写字母组成的字符串表示。如可用exp表示用来表示表达式的非终结符。
YACC在对源文件进行编译时，将对所有的单词和非终结符进行编码，并用该编码建立分析表和语法分析器。单词的编码原则是：字符单词使用其对应的ASCII码，有名单词则由分析器进行编码。用户在对有名单词进行命名时，一定要注意不要和使用该单词名的C源程序中已有的宏名相同，否则在编译该C模块时是会产生宏定义冲突的。
(2) 定义部分
YACC的定义部分比LEX复杂，在此并未给出其全部规则，只是给出了实验中要用到的部分。有兴趣的同学可以查阅有关资料或与我们联系。
定义部分结构如下：
%{C语言代码部分%}
语义值数据类型定义
单词定义
非终结符定义
优先级定义
其中，C语言代码部分同LEX，语义值数据类型定义部分定义了进行语法分析时语义栈中元素的数据类型，可用宏YYSTYPE定义。本书例中数据类型为double型(算术表达式的语义值)，可直接将之放入到C语言代码部分中，如可在C语言代码部分中加入一句#define YYSTYPE double。非终结符一般不需要作声明，在此略过不谈。
结合次序和优先级别的定义，将让YACC在编译源文件时，面对由文法的二义性引起的移进-归约冲突时，能正确的选择移进或归约。如我们知道，二元’+’和’-‘的优先级低于’*’和’/’，它们优先级又都低于一元减(取负)’-‘,且它们都是左结合的，则我们可以这么定义：
%left ‘+’ ‘-‘
%left ‘*’ ‘/’
%left UMINUS /虚拟单词，它和一元减有相同的优先级别和结合次序/
上面的定义说明了它们的优先级，规则是越在后面定义的优先级越高。而%left说明了是左结合的。注意一元减用了个虚拟单词UMINUS。在规则部分，对一元减作如下处理：
exp :
| ‘-‘ exp %prec UMINUS
……
说明了一元减’-’就是前面定义的UMINUS。
这样就区别了同一算符在不同上下文环境中的优先级别和结合次序。
(3) 语法规则部分
YACC利用BNF范式定义形式语言的递归生成规则。YACC采用下述符号作为每个产生式的控制符号：
冒号‘：’分割产生式的左右两个部份；竖杠‘|’分割同一非终结符对应的多条规则；分号‘;’结束一个产生式。注意：在书写语法规则时一定要区别单词、非终结符和上述控制符号，否则将会导致出错。综上，每个产生式的规则如下：
非终结符： 规则一
| 规则二
………
|规则n
其中，每个规则是由单词和非终结符组成的语法符号串，每个语法符号用白字符分隔。如产生式exp->exp+exp|exp-expNUM可表示为
exp: exp ‘+’ exp
| exp ‘-‘ exp
| NUM
;
规则部分可以是空串，如产生式input->ε可表示为
input : /空串/
;
加注释的目的是为了便于阅读。
YACC最欢迎的是左递归文法，而用右递归文法则可能会导致分析栈溢出，故要尽量避免用右递归文法。
3．语义定义
YACC输出的分析器不仅要识别形式语言，更重要的是要完成语义的翻译。YACC提供一种语法规则制导语义定义的功能，它通过在源程序的语法规则中嵌入求解语义值或者完成相应语义动作的C语言代码，从而定义每个语法规则的语义。
(1)单词（终结符）语义值的计算
输出分析函数int yyparse()在需要向前查看单词或者移进一个单词时将调用函数int yylex(),此函数可通过由词法分析器自动生成，也可手动生成。本书中两例比较简单，采用的是手动生成int yylex（）的方法。用户必须在yylex（）中计算出当前单词的语义值，将该值保存在YACC输出的分析器提供的一个类型是YYSTYPE的全局变量yylval中。注意yyparse()在移进一个单词到分析栈的同时，将yylval的值拷贝到语义栈中。我们不用管yylval是如何进栈的，只需知道,一旦在yylex()中将一个值赋给yylval后，yyparse()每调用yylex()一次,就将yylval进栈一次。
(2)非终结符语义值的计算
计算非终结符的语义值一般随归约动作同时进行，由于归约是利用语法规则进行归约的，所以YACC提供在每个语法规则的尾部附加C语言代码的功能，称为语义动作，当分析器用该规则进行归约时，将执行该段代码。利用这段代码和语义栈中已知语法符号的语义值，可完成对归约的非终结符的语义值的计算。语义动作由花括号引入，格式如下：
非终结符: 规则一 {动作一}
| 规则二 {动作二}
…….
| 规则n {动作n}
;
YACC提供一种简单的方式让用户在语义动作中访问语义栈中栈顶元素的语义值。设当前规则中有n个语法符号，如：
非终结符: S1 S2 ……Sn
对以上产生式进行归约时，语义栈自底向顶分别排列为……S1,S2,……Sn，其相应的语义值可用……$1，$2……$n表示，非终结符对应的语义值用$$表示，在完成语义分析动作，即对$$的处理后，将$$的内容拷贝到语义栈中。如：
exp : ……
| exp ‘+’ exp {$$=$1+$3;}
;
其中，$1和$3分别表示规则中第一个和第二个exp的语义值，$$表示非终结符exp的语义值。
4．其它
YACC的语法比较复杂，用法也很灵活，如它和LEX之间预留的接口是一样的，所以还可以和LEX直接结合使用。这些内容本书均未谈及，留待有兴趣的同学自己查阅有关资料。
5．示例
例一：用YACC生成逆波兰表示计算器
分析：逆波兰表达式文法可定义为
exp->exp exp + |exp exp –
|exp exp * |exp exp / |
exp exp ^ |exp n |NUM
其中，’^’为乘幂符号,’n’为一元减,此文法为无二义性文法。
其YACC源程序(不妨取名为rpcalc1.y)如下
%{
#define YYSTYPE double/ 定义表达式语义值为double型/
#include <stdio.h>
#include <math.h>
#include <ctype.h>
%}
%token NUM /定义有名单词NUM，用来表示数的种别码/
%%
input: /可为空串/
|input line
;
line: ‘\n’
|exp ‘\n’ {printf(“\t%10.g\n”,$1);}
;
exp: NUM {$$=$1;}
|exp exp ‘+’ {$$=$1+$2;}
|exp exp ‘-‘ {$$=$1-$2;}
|exp exp ‘‘ {$$=$1$2;}
|exp exp ‘/‘ {$$=$1/$2;}
|exp exp ‘^’ {$$=pow($1,$2);}
|exp ‘n’ {$$=-$1;}
;
%%
main()
{
printf(“\nPlease input your expression,end with ENTER && CTRL+Z:\n”);
yyparse();
}
yyerror(char *s)
/此函数必须给出，为yyparse()出错时调用/
{
printf(“error=%s”,s);
}
int yylex()
/用户手编的词法分析器/
{
int c;
while((c=getchar())==’ ‘|| c==’\t’);
if(c==’.’ || isdigit(c))
{
ungetc(c,stdin);
scanf(“%lf”,&yylval);/单词为数，将此数的值存入yylval/
return NUM;/返回种别码/
}
if(c==EOF)
return 0;
return c;/其它单个字符则返回其本身，因为其本身就是自己的编码/
}
在DOS提示符下运行
C:>bison rpcalc1.y –d
则在当前目录下生成新文件rpcalc1.tab.c，用TURBOC编译该文件，产生可执行文件rpcalc1.tab.exe。执行该文件
C:>rpcalc1.tab
则运行结果如下：
Please input your expression,end with ENTER && CTRL+Z:
12 35 +
47
例二：用YACC生成中缀表达式计算器
分析 中缀表达式产生式为
exp->exp + exp | exp - exp| exp * exp
|exp / exp |exp ^ exp | - exp
|(exp) |NUM
此文法是一个二义性文法，可通过设立结合性和优先次序来消除二义性。则YACC源程序(rpcalc2.y)如下:
%{
#define YYSTYPE double
#include <stdio.h>
#include <math.h>
#include <ctype.h>
%}
%token NUM
%left ‘-‘’+’
%left ‘*’’/‘
%left UMINUS /虚拟单词，它和一元减有相同的优先级别/
%right ‘^’
/上面代码定义了结合性和优先级/
%%
input: /empty string/
|input line
;
line: ‘\n’
|exp ‘\n’ {printf(“\t%10.g\n”,$1);}
;
exp: NUM {$$=$1;}
|exp ‘+’ exp {$$=$1+$3;}
|exp ‘-‘ exp {$$=$1-$3;}
|exp ‘‘ exp {$$=$1$3;}
|exp ‘/‘ exp {$$=$1/$3;}
|exp ‘^’ exp {$$=pow($1,$3);}
|’-‘ exp %prec UMINUS {$$=-$2;}
|’(‘exp’)’{$$=$2}
;
%%
/用户代码部分同例一相应部分，在此省略不写/
参考文献
[1] 胡伦骏，徐兰芳，刘建农编.编译原理.电子工业出版社,2002,3
[2] 吕映芝，张素琴，蒋维杜.编译原理,1998,1
