一、实验目的：
通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。
编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）
二、实验预习提示
1、词法分析器的功能和输出格式
词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式(单词种别码，单词符号的属性值)。本实验中，采用的是按类来安排种别码的方式。
2、部分单词的BNF表示（可参考教材43页的状态转换图）
<标识符>-> <字母><字母数字串>
<字母数字串>-><字母><字母数字串>|<数字><字母数字串>|
<下划线><字母数字串>|ε
<无符号整数>-> <数字><数字串> <数字串>-> <数字><数字串> |ε <加法运算符>-> + <减法运算符>-> - <大于关系运算符>-> >
<大于等于关系运算符>-> >=
3、 做词法分析器需要把对象语言的词法全部描述出来，在这我们取C语言子集，它的
词法如下： （1）关键字
main if else int return void while…….. 所有的关键字都是小写。 （2）专用符号
= + - * / ＜＝ ＞ ＞＝ == ！= ； ： ， { } [ ] （ ）
（3）空格和空白、制表符和换行符。
空格一般用来分隔ID、NUM、专用符号和关键字，在词法分析阶段通常被忽略。
各种单词符号的种别码，这是一种符号一个编码的设计。只供参考！ 单词符号 main int char If
种别码 2 1 3 4 单词符号 [ ] { } 1
种别码 28 29 30 31 else for while ID NUM = + - * / ( ) 5 6 7 10 20 21 22 23 24 25 26 27 , : ; > < >= <= == != ‘\\0’ ERROR 32 33 34 35 36 37 38 39 40 1000 -1 4、“超前搜索”方法 词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“a>+”,当前字符为’>’，此时，分析器倒底是将其分析为大于关系运算符还是大于等于关系运算符呢？显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符’+’，这时可知应将’>’解释为大于运算符。但此时，超前读了一个字符’+’，所以要回退一个字符，词法分析器才能正常运行。在分析标识符，无符号整数等时也有类似情况。
5、模块结构 见附图
三、实验过程和指导：
（一）准备：
1.阅读课本有关章节，明确语言的语法，写出基本保留字、标识符、常数、运算符、分隔符和程序例。 2.编制好程序。
3.准备好多组测试数据。 （二）上机调试： （三）程序要求：
程序输入/输出示例：
如源程序为C语言。输入如下一段：
main() {
int a,b; a = 10; b = a + 20; }
要求输出如右图。
2
（2，“main”） （5，“（” ） （5，“ ）” ） （5，“{ ” ） （1，“int” ） （2，“a” ） （5，“,” ） （2，“b” ） （5，“;” ） （2，“a” ） （4，“=” ） （3，“10” ） （5，“;” ） （2，“b” ） （4，“=” ） （2，“a” ） （4，“+” ） （3，“20” ） （5，“;” ） （5，“}” ） 说明：
识别保留字：if、int、for、while、do、return、break、continue；
单词种别码为1。
其他的都识别为标识符；单词种别码为2。 常数为无符号整形数；单词种别码为3。
运算符包括：+、-、*、/、=、>、<、>=、<=、!= ；单词种别码为4。 分隔符包括：,、;、{、}、(、)； 单词种别码为5。 以上为参考，具体可自行增删。 程序思路（参考）：
这里以开始定义的C语言子集的源程序作为词法分析程序的输入数据。在词法分析中，自文件头开始扫描源程序字符，一旦发现符合“单词”定义的源程序字符串时，将它翻译成固定长度的单词内部表示，并查填适当的信息表。
经过词法分析后，源程序字符串（源程序的外部表示）被翻译成具有等长信息的单词串（源程序的内部表示），并产生两个表格：常数表和标识符表，它们分别包含了源程序中的所有常数和所有标识符。 0.定义部分：定义常量、变量、数据结构。
1.初始化：从文件将源程序全部输入到字符缓冲区中。 2.取单词前：去掉多余空白。
3.取单词后：去掉多余空白（可选，看着办）。
4.取单词：利用实验一的成果读出单词的每一个字符，组成单词，分析类型。（关键是如何判断取单词结束？取到的单词是什么类型的单词？） 5.显示结果。
为了设计好程序，注意以下事情：
1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。 2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。
3
3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。
四、 实习报告的书写
实习题目： 1 实习目的:
2 设计方案（算法）和关键性代码
这部分要求先对程序设计的算法进行描述（可以用流程图表示，其他形式亦可），然后书写出源程序设计中的关键性代码，并加上必要的注释。 3 总结
这部分包括实习中出现的问题，如何解决问题以及收获等内容。
4
实习二 递归下降分析
一、实验目的：
根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本
次实验的目的主要是加深对递归下降分析法的理解。另：程序开始变得复杂起来，需要利用到程序设计语言的知识和大量编程技巧，递归下降分析法是一种较实用的分析法，通过这个练习可大大提高软件开发能力。通过练习，掌握函数间相互调用的方法。
二、实验预习提示
1、递归下降分析法的功能
词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 2、递归下降分析法的前提
改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法， 3、递归下降分析法实验设计思想及算法
为G的每个非终结符号U构造一个递归过程,不妨命名为U。 U的产生式的右边指出这个过程的代码结构：
(1)若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；否则出错。 (2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,
可用选择结构实现。 具体为：
（1）对于每个非终结符号U->u1|u2|„|un处理的方法如下：
U( ) {
ch=当前符号;
if(ch可能是u1字的开头) 处理u1的程序部分; else if(ch可能是u2字的开头)处理u2的程序部分; „
else error() }
（2）对于每个右部u1->x1x2„xn的处理架构如下：
处理x1的程序； 处理x2的程序； „
处理xn的程序；
（3）如果右部为空，则不处理。 （4）对于右部中的每个符号xi
① 如果xi为终结符号： if(xi= = 当前的符号) {
NextChar()； /% NextChar为前进一个字符函数。%/ return;
5
}
else 出错处理
② 如果xi为非终结符号，直接调用相应的过程xi()
三、实验过程和指导：
（一）准备：
1.阅读课本有关章节， 2.考虑好设计方案；
3.设计出模块结构、测试数据，初步编制好程序。 （二）上机：
将源代码上机调试，发现错误，再修改完善。 （三）程序要求：
程序输入/输出示例：
对下列文法，用递归下降分析法对任意输入的符号串进行分析： （1）E->TG
（2）G->+TG|－TG|ε （3）T->FS
（4）S->*FS|/FS|ε （5）F->(E)|i 输出的格式如下：
(1)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (2)输出结果：i+i*i#为合法符号串
备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。 注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符I，结束符#；
2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 3.学有余力的同学，可以详细的输出推导的过程，即详细列出每一步使用的产生式。
（四）程序思路（供参考）
0. 定义部分：定义常量、变量、数据结构。
1. 初始化：从文件将输入符号串输入到字符缓冲区中。
2. 利用递归下降分析法分析，对每个非终结符编写函数，在主函数中调用文法开始
符号的函数。 注意：
1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。 2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。 3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。
四、 实习报告的书写
实习题目： 1 实习目的:
6
2 设计方案（算法）和关键性代码
这部分要求先对程序设计的算法进行描述（可以用流程图表示，其他形式亦可），然后书写出源程序设计中的关键性代码，并加上必要的注释。 3 总结
这部分包括实习中出现的问题，如何解决问题以及收获等内容。
实习三 LL（1）分析
一、实验目的：
根据某一文法编制调试
LL（1）分析程序，以便对任意输入的符号串进行分析。本
次实验的目的主要是加深对预测分析LL（1）分析法的理解。
二、实验预习提示
1、LL（1）分析法的功能
LL（1）分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以及LL（1）分析表，对输入符号串自上而下的分析过程。 2、LL（1）分析法的前提
改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法， 3、LL（1）分析法实验设计思想及算法
三、实验过程和指导：
（一）准备：
1.阅读课本有关章节， 2.考虑好设计方案；
7
3.设计出模块结构、测试数据，初步编制好程序。 （二）上机： （三）程序要求：
程序输入/输出示例：
对下列文法，用LL（1）分析法对任意输入的符号串进行分析： （1）E->TG
（2）G->+TG|－TG|ε （3）T->FS
（4）S->*FS|/FS|ε （5）F->(E)|i 输出的格式如下：
(1)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串 (2)输出过程如下：
步骤 分析栈 剩余输入串 所用产生式 1 E i+i*i# E->TG
(3)输入符号串为非法符号串(或者为合法符号串)
备注：(1)在“所用产生式”一列中如果对应有推导则写出所用产生式；如果为匹配终结符则写明匹配的终结符；如分析异常出错则写为“分析出错”；若成功结束则写为“分析成功”。
(2) 在此位置输入符号串为用户自行输入的符号串。
(3)上述描述的输出过程只是其中一部分的。 注意：
1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；
3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；
（四）程序思路（供参考）： 模块结构：
（1）定义部分：定义常量、变量、数据结构。
（2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时
变量等）；
（3）控制部分：从键盘输入一个表达式符号串；
（4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆
栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。 （五）练习该实验的目的
8
程序相当复杂，需要利用到大量的编译原理，也用到了大量编程技巧和数据结构，通过练习可大大提高软件开发能力。 （六）为了设计好程序，注意以下事情：
1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。 2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。 3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。
实习四 算符优先分析
一、实习目的
通过上机实习，加深对算符优先分析过程的理解，掌握优先函数法。
二、实习提示
先定义入栈优先函数f（如表1所示）和比较优先函数（如表2所示）。设立两个栈，即算符栈和操作数栈。
表1 入栈优先函数f。 x ) F（x） 9
表2 比较优先函数g x ) G（x） 1
↑ 7 *，/ 5 +，- 3 （ 1 ＄ 0 ↑ 6 *，/ 4 +，- 2 （ 8 ＄ 0 分析过程：
先在算符栈置“＄”，然后开始顺序扫描表达式。若读来的单词符号是操作数，则直接进操作数栈，然后继续下一个单词符号，分析过程从头开始，并重复进行；若读来的是运算符θ2 ，则将当前处于运算符栈顶的运算符θ1 的入栈优先函数f与θ2 比较优先函数g进行比较。
（1）若f（θ1）≤g（θ2），则θ2 进算符栈，并续继顺序往下扫描，分析过程从头开始。
（2）若f（θ1）＞g（θ2），则产生对操作数栈顶的若干项进行θ1 运算的中间代码，并从运算符栈顶移去θ1 ，并且从操作数栈顶移去若干项，然后把执行θ1 运算的结果压入操作数栈。接着以运算符栈新的项与θ2 进行上述优先函数的比较，即重复（1），（2）。
（3）重复（1）、（2），直到“＄”和“＄”配对为止。 优先函数的分析过程示意图如图四所示。
三、实习过程和指导
（一）准备：
1.阅读课本有关章节， 2.考虑好设计方案；
3.设计出模块结构、测试数据，初步编制好程序。 （二）上机：
9
（三）程序要求：
1．采用算符优先分析法对表达式进行分析，并给出四元式序列。 2．设计四元式的方案。
3．参考前面的实习，设计输入输出方式。 程序输入/输出示例：
对下列文法，用算符优先分析法对任意输入的符号串进行分析：
（1）E->TG
（2）G->+TG|－TG|ε （3）T->FS
（4）S->*FS|/FS|ε （5）F->(E)|i
置初值或初态 读一个单词符号 是操作数 是否算符 压入操作数栈 是 ＜ θ2 进算符栈顶 ＞ 产生执θ中间代码 1 f（θ1）与g（θ2 ） 的= 否 出错处理 ＄是否配对 修改算符栈和操作数栈 是 出口 图四 优先函数的分析过程示意图
四、 实习报告的书写
实习题目： 1 实习目的:
2 设计方案（算法）和关键性代码
这部分要求先对程序设计的算法进行描述（可以用流程图表示，其他形式亦可），然后书写出源程序设计中的关键性代码，并加上必要的注释。
10
3 总结
这部分包括实习中出现的问题，如何解决问题以及收获等内容。
实习五 语义分析
一、实习目的
通过上机实习，加深对语法制时翻译原理的理解，掌握将语法分析所识别的语法成分变换为中间代码的语义翻译方法。 二、实习要求
采用递归下降语法制导翻译法对算术表达式、赋值语句、条件语句、循环语句进行语义分析生成四元式序列。
三、实习过程和指导
（一）实习的输入和输出
1．输入语法分析提供的正确的单词串，输出四元式序列。例如：对于语句串： float r , h , s; s=2*3.1416*r*(h+r) 2．输出的四元式序列如下： （1）（*，2，3.1416，T1） （2）（*， T1， r, T2） （3）（+， h, r, T3） （4）（*， T2， T3， T4） （5）（=， T4， —， s） （二）程序算法 （供参考） 1．设置语义过程
（1）int gen (op, argl, arg2,result)
该函数是将四元式(op, argl, arg2,result)送到四元式表中。 （2）char *newtemp ( )
该函数回送一个新的临时变量名，临时变量名产生的顺序为T1，T2„„ （3）int merge (p1,p2 )
该函数将以p1和p2为头指针的两条链合并为一，合并后的链首为返回值。 （4）int bp ( p, t )
该函数的功能是把p所链接的每个四元式的第四区段都填为t。 2．主程序示意图
置初值 主程序示意图如图所示。
3．函数Irparse在原来语法分析的基础上插入
相应的语义动作。将输入串翻译成四元式序 调用scaner 列。在实习中仅对表达式、if语句和while 语句进行翻译。
四、 实习报告的书写
1 实习目的:
法）和关键性代码
11
实习题目：
调用Irparser 2 设计方案（算这部分要求先
打印四元式序列 结束 对程序设计的算法进行描述（可以用流程图表示，其他形式亦可），然后书写出源程序设计中的关键性代码，并加上必要的注释。
3 总结
这部分包括实习中出现的问题，如何解决问题以及收获等内容。
综合实习 构造一个编译器
以词法分析给出的语言子集和语法分析给出的语法集为分析的基础，运用《软件工程》思想和方法，考虑词法、语法、语义分析各模块的结构将其集成；构造一个编译器，输入一个源程序，输出四元式序列。
选作： 逆波兰式的产生及计算
一、实验目的：
将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。
12
二、实验预习提示
1、逆波兰式定义
将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式，其优点在于易于计算机处理表达式。 2、产生逆波兰式的前提 中缀算术表达式
3、逆波兰式生成的实验设计思想及算法
(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。
(2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。
(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。
(4)如果不是数字，该字符则是运算符，此时需比较优先关系。
做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。
(5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。 3、逆波兰式计算的实验设计思想及算法
13
(1)构造一个栈，存放运算对象。
(2)读入一个用逆波兰式表示的简单算术表达式。
(3)自左至右扫描该简单算术表达式并判断该字符，如果该字符是运算对象，则将该字符入栈。若
是运算符，如果此运算符是二目运算符，则将对栈顶部的两个运算对象进行该运算，将运算结果入栈，并且将执行该运算的两个运算对象从栈顶弹出。如果该字符是一目运算符，则对栈顶部的元素实施该运算，将该栈顶部的元素弹出，将运算结果入栈。
(4)重复上述操作直至扫描完整个简单算术表达式的逆波兰式，确定所有字符都得到正确处理，我
们便可以求出该简单算术表达式的值。
三、实验过程和指导： （一）准备：
1.阅读课本有关章节， 2.考虑好设计方案；
3.设计出模块结构、测试数据，初步编制好程序。 （二）上课上机：
将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。 （三）程序要求： 程序输入/输出示例： 输出的格式如下：
(1)逆波兰式的生成及计算程序，编制人：姓名，学号，班级 (2)输入一以#结束的中缀表达式(包括+—*/（）数字#)：在此位置输入符号串如(28+68)*2# (3)逆波兰式为：28&68+2* (4)逆波兰式28&68+2*计算结果为192 备注：(1)在生成的逆波兰式中如果两个数相连则用&分隔，如28和68，中间用&分隔； (2)在此位置输入符号串为用户自行输入的符号串。 注意：
1.表达式中允许使用运算符（+-*/）、分割符（括号）、数字，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；
3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；
（四）程序思路（仅供参考）：
14
模块结构：
（1）定义部分：定义常量、变量、数据结构。
（2）初始化：设立算符优先分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）； （3）控制部分：从键盘输入一个表达式符号串；
（4）利用算符优先分析算法进行表达式处理：根据算符优先分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。 （5）对生成的逆波兰式进行计算。 （五）为了能设计好程序，注意以下事情：
1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。 2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。 3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。
15
因篇幅问题不能全部显示，请点此查看更多更全内容