编译原理实验指导书
计算机科学与技术系
2007年6月
目录
实验目的和任务 (1)
实验一：词法分析器 (1)
实验二：语法分析器1 (5)
实验三：语法分析器2 (9)
实验四：语义分析和中间代码生成器 (11)
实验目的和任务
编译原理是一门实践性很强的课程，只有通过实践，才能真正理解其理论的深层内涵，切实掌握编译器的生成技术。
实际的编译程序是十分复杂的，有时多达十几万条指令组成，实现起来难度很大。在编译原理的实验中，简化了真实程序设计语言要面临的许多问题，选用了具有一定表现能力的实用语言的子集。实验主要涉及最关键的３个环节──词法分析、语法分析和中间代码生成，每个环节既独立又相互关联，前后衔接，可合为一体，能较清楚地展现编译器前端的工作状况。
编程语言要求：C、C++或JAVA。
实验一：词法分析器
一、实验目的
通过编写词法分析程序，了解词法分析的过程。
二、实验内容
编写能识别给定的程序设计语言的词法规则，输出单词流的识别程序。
三、实验设备及工具
1．硬件：PC机Pentium100以上。
2．软件：Win2000或WinXP、BC++、VC++或JA V A开发环境。
四、实验说明
以下所给文法是进行词法分析和语法分析的依据，并将该文法中涉及到的单词信息提取到了单词符号与种别对照表中。
本次实验要求编写符合该文法构词规则的词法分析器。
1. 文法G（<程序>）
<程序>→BEGIN <语句表> END.
<语句表>→<语句>|<语句>;<语句表>
<语句>→<赋值语句>︱<条件语句>︱︱<复合语句>
<赋值语句>→<变量>=<算术表达式>
<条件语句>→IF <关系表达式> THEN <语句> ELSE <语句>
→WHILE <关系表达式> DO <语句>
<复合语句>→BEGIN <语句表> END
<算术表达式>→<项>|<算术表达式>+<项>|<算术表达式>-<项>
<项>→<变量>|<整数>
<关系表达式>→<算术表达式><关系运算符><算术表达式>
<关系运算符>→<︱= =︱>
<变量>→<标识符>
<标识符>→<标识符><字母>|<标识符><数字>|<字母>
<整数>→<数字>|<数字><整数>
<字母>→A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z
<数字>→0|1|2|3|4|5|6|7|8|9
注意阴影部分，其中<整数>和<标识符>被看作最小词法单位。
2. 单词符号与种别对照表1-1，存放了上述文法的所有单词及种别。
单词符号与种别对照表1-1
五、实验步骤
为了实现编译程序的实用，源程序可采用自由书写格式，即一行内可以书写多个语句，一个语句也可以占领多行书写；标识符的前20个字符有效；整数用2个字节表示。这样词法分析程序的主要工作为：
1．从源程序文件中读入字符。
2．统计行数和列数用于错误单词的定位。
3．删除空格类字符，包括回车、制表符空格。
4．按拼写单词，并用（种别，单词）二元式表示。
5．根据需要是否填写标识符表供以后各阶段使用。
6．这里采用的编译程序的实现方法是一遍扫描，即从左到右只扫描一次源程序，也就是词法分析作为语法分析的一个子程序。故在编写词法分析程序时，用重复调用词法分析子程序取一单词的方法得到整个源程序的二元式流。
7．源程序存放到文件*.pas。
8．词法分析器从*.pas中读取字符流，输出为单词二元式流，并将输出结果存放到*.dc文件中。
9．分别用正确的和错误的源程序测试词法分析器；
正确的源程序示例test.pas：
BEGIN
I=10;
J=I+5;
WHILE I= =10 DO
BEGIN
R=J+I;
I=I-1
END
END.
输出结果为：
（1 ，“BEGIN”）
（17，“I”）
（8 ，“=”）
（16，“10”）
（15，“；”）
………………
10．实验完成后，将词法分析器程序代码、测试程序代码(正确的及错误的至少各一例)、输出的单词二元式流和相应的注释都存放到一个文件中提交打印并书写实验报告。
六、实验类型
验证性实验。
七、实验学时
3学时。
八、考核方式
本实验总分为5分，具体评分标准如下：
5分：实验准备充分，上机准时，能独立编写和调试程序，结果正确，实验报告内容齐全，格式规范。
4分：实验准备良好，上机准时，能在教师指导下顺利编写和调试程序，结果较正确，实验报告内容比较齐全，格式比较规范。
3分：实验准备较好，上机准时，基本完成实验任务，实验报告内容基本齐备，结果基本正确。
2分：程序功能模块基本完整，但没有完成程序调试，无实验结果，提交了实验报告且有重大缺陷。
1分：程序功能模块不完整，有重大问题，没有完成程序调试，无实验结果，提交的实验报告有重大缺陷。
0分：没有参加实验，没有提交实验报告。
九、思考题
1．除了你使用的关键字检查方法，还有哪些可行性方案?比较其优劣。
2．词法分析过程中查出错误后怎样保证分析尽可能继续进行？
3．如何将词法分析器改造成函数，以供语法分析器调用?
