计算机学院本科课程实验建设及实验指导书编写教改项目启动通知

1、 北 京 邮 电 大 学计算机科学与技术学院编译原理与技术 实 验 指 导 书李文生 编著2007年 5 月目 录实验一 词法分析器的设计与实现3实验二 递归调用语法分析器的设计与实现（选作）7实验三 lr语法分析器的设计与实现10实验四 语法分析器的自动生成（选作）13实验五 非递归的预测语法分析器的设计与实现（选作）16实验六 语义分析器的设计与实现19编译原理与技术课程设计22附录a： parser generator的使用说明30教材及主要参考文献3939实验一 词法分析器的设计与实现一、 实验类别：综合型实验二、 实验目的1通过实验进一步理解和掌握词法分析器的工作原理2熟悉c语言环境

2、编程3熟悉lex软件的使用三、 实验学时：4学时四、 实验组人数：1-2人五、 实验设备环境1windows 2000/windows xp2microsoft virtual c+ 6.03parser generator （for windows）六、 实验原理（知识点）1正规表达式、正规文法、有限自动机之间的等价性2单词、模式、与记号3记号的描述与识别4程序设计与调试七、 教学要点与学习难点1本实验教学的要点程序设计语言（如pascal语言）的各类单词符号的正规表达式描述识别各类单词符号的有限自动机的构造2本实验教学的学习难点记号的描述lex软件的使用八、 实验内容和要求1试验内容：编写

3、pascal语言的词法分析器2功能要求1) 可以识别出用pascal语言编写的源程序中的每个单词符号，并以记号的形式输出每个单词符号2) 可以识别并读去源程序中的注释3) 可以统计源程序中的语句行数、单词个数、字符个数，其中标点和空格不计算为单词，并输出统计结果4) 检查源程序中存在的词法错误，并可以报告错误所在的行列位置5) 发现源程序中存在错误后，进行适当的恢复，使词法分析可以继续进行，通过一次词法分析处理，可以检查并报告源程序中存在的所有词法拼写错误3实现要求既可以采用c+作为实现语言，手工编写词法分析器，也可以利用lex软件工具，通过编写lex说明文件自动生成词法分析器。九、 实验步骤

4、1手工编写pascal语言的词法分析器的实验步骤1) 熟悉pascal语言的字符集、保留字、标点符号等2) 对pascal语言的单词符号进行分类和编码，设计翻译表3) 写出每一类单词符号的正规表达式、相应的右线性文法4) 构造识别每一类单词符号的有限自动机（状态转换图）5) 构造词法分析器的状态转换图6) 根据上面的状态转换图构造词法分析器的程序流程图7) 编码、调试8) 设计测试用例（编写pascal程序，对其进行词法分析，对输出结果进行分析），完成测试报告。2利用lex软件工具自动生成pascal语言的词法分析器的实验步骤1) 熟悉pascal语言的字符集、保留字、标点符号等2) 对pas

5、cal语言的单词符号进行分类和编码，设计翻译表3) 写出每一类单词符号的正规表达式4) 写出pascal语言词法分析的lex说明文件5) 用parser generator对该说明文件进行编译、调试、运行等，生成pascal语言的词法分析器6) 在microsoft virtual c+ 6.0环境中对上面生成的词法分析器进行编译、调试、运行等7) 设计测试用例（编写pascal程序，对其进行词法分析，对输出结果进行分析），完成测试报告。十、 可研究与探索的问题分析lex工具软件所生成的词法分析器的结构。研究lex软件的工作原理和实现机制。十一、 实验报告要求实验报告要求涵盖以下内容：1实验题

6、目2实验目的和要求3实验环境4设计，包括： 1) 实现方法（手工实现、lex工具实现） 2) 单词分类（单词的分类、类别编码、单词类的描述、模式、识别等） 3) 词法分析器的输入、输出 4) 词法分析器的算法逻辑5编码（源程序）6测试报告（测试用例、测试结果、测试结果分析）7实验总结 1) 实验中遇到或存在的主要问题 2) 体会/收获 3) 改进建议实验二 递归调用语法分析器的设计与实现（选作）一、 实验类别：综合型实验二、 实验目的1通过实验进一步理解和掌握语法分析器的工作原理2熟悉c语言环境编程三、 实验学时：10学时四、 实验组人数：1-2人五、 实验设备环境1windows 2000/

7、windows xp2microsoft virtual c+ 6.0六、 实验原理（知识点）自顶向下分析方法：消除左递归 构造状态转换图 构造递归调用程序七、 教学要点与学习难点1本实验教学的要点消除文法中的左递归、构造状态转换图2本实验教学的难点所构造语法分析器与词法分析器的集成八、 实验内容和要求1实验内容编写程序，实现对算术表达式进行语法分析，所分析算数表达式由下面的文法产生：e e+t | et | tt t*f | t/f | ff id | (e) | num2实验要求用自顶向下的方法实现，输出分析过程中所用产生式序列九、 实验步骤1）消除文法中存在的左递归2）为上步中得到的文法

8、构造预测分析器状态转换图3）对状态转换图进行化简4）根据化简后的状态转换图构造递归调用程序5）编码、调试6）设计测试用例（编写pascal程序，对其进行词法、语法分析，对输出结果进行分析），完成测试报告十、 可研究与探索的问题分析过程中的错误处理与恢复问题十一、 实验报告要求实验报告要求涵盖以下内容：1实验题目2实验目的和要求3实验环境4设计，包括： 1) 实现方法 2) 消除左递归后的文法、状态转换图 3) 语法分析器的输入、输出 4) 语法分析器的算法逻辑描述5编码（源程序）6测试报告（测试用例、测试结果、测试结果分析）7实验总结 1) 实验中遇到或存在的主要问题 2) 体会/收获 3)

9、改进建议实验三 lr语法分析器的设计与实现一、 实验类别：综合型实验二、 实验目的1通过实验进一步理解和掌握语法分析器的工作原理2熟悉c语言环境编程三、 实验学时：10学时四、 实验组人数：1-2人五、 实验设备环境1windows 2000/windows xp2microsoft virtual c+ 6.0六、 实验原理（知识点）自底向上分析方法：构造识别活前缀的dfa 构造分析表 lr分析程序七、 教学要点与学习难点1本实验教学的要点构造识别文法所有活前缀的dfa、构造lr分析表2本实验教学的难点所构造语法分析器与词法分析器的集成八、 实验内容和要求1实验内容编写程序，实现对算术表达式

10、进行语法分析，所分析算数表达式由下面的文法产生：e e+t | et | tt t*f | t/f | ff id | (e) | num2实验要求用自底向上的方法实现，输出分析过程中所用产生式序列九、 实验步骤1）根据文法构造识别所有活前缀的dfa2）根据dfa构造lr分析表，考虑同步信息的设置3）实现教材p.90算法4.3 lr分析算法4）编码、调试5）设计测试用例（编写pascal程序，对其进行词法、语法分析，对输出结果进行分析），完成测试报告十、 可研究与探索的问题分析过程中的错误处理与恢复问题十一、 实验报告要求实验报告要求涵盖以下内容：1实验题目2实验目的和要求3实验环境4设计，包

11、括： 1) 实现方法 2) 识别活前缀的dfa、分析表 3) 语法分析器的输入、输出 4) 语法分析器的算法逻辑描述5编码（源程序）6测试报告（测试用例、测试结果、测试结果分析）7实验总结 1) 实验中遇到或存在的主要问题 2) 体会/收获 3) 改进建议实验四 语法分析器的自动生成（选作）一、 实验类别：综合型实验二、 实验目的1通过实验进一步理解和掌握语法分析器的工作原理2熟悉c语言环境编程3熟悉yacc软件的使用三、 实验学时：4学时四、 实验组人数：1-2人五、 实验设备环境1windows 2000/windows xp2microsoft virtual c+ 6.03parser

12、 generator （for windows）六、 实验原理（知识点）lr分析器的工作原理七、 教学要点与学习难点1本实验教学的要点yacc说明文件的格式记号及语义规则的设计2本实验教学的难点yacc工具的使用yacc说明文件与词法分析器的集成八、 实验内容和要求1实验内容利用yacc工具自动生成表达式的语法分析程序，实现对由下面的文法所产生的算术表达式的语法分析。e e+t | et | tt t*f | t/f | ff id | (e) | num2实验要求1）对于给定的算术表达式输出分析过程中所用产生式序列九、 实验步骤1）根据文法书写yacc说明文件2）利用yacc工具自动生成语法

13、分析器3）在c语言环境下对所生产的语法分析器进行编译、链接4）调试5）设计测试用例（编写pascal程序，对其进行词法、语法分析，对输出结果进行分析），完成测试报告十、 可研究与探索的问题分析yacc工具软件所生成的语法分析器的结构。研究yacc软件的工作原理和实现机制。十一、 实验报告要求实验报告要求涵盖以下内容：1实验题目2实验目的和要求3实验环境4设计，包括： 1) 实现方法 2) yacc说明文件中用到的记号、规则、辅助过程等的设计 3) 语法分析器的输入、输出的设计5编码（yacc说明文件）6测试报告（测试用例、测试结果、测试结果分析）7实验总结 1) 实验中遇到或存在的主要问题 2

14、) 体会/收获 3) 改进建议实验五 非递归的预测语法分析器的设计与实现（选作）一、 实验类别：验证型实验二、 实验目的1通过实验进一步理解和掌握语义分析器的工作原理2熟悉c语言环境编程三、 实验学时：4学时四、 实验组人数：1-2人五、 实验设备环境：1windows 2000/windows xp2microsoft virtual c+ 6.0六、 实验原理（知识点）自顶向下分析方法：消除左递归 构造预测分析表 预测分析程序七、 教学要点与学习难点1本实验教学的要点消除文法中的左递归、构造预测分析表2本实验教学的难点八、 实验内容和要求1实验内容编写程序，实现对算数表达式进行语法分析，所

15、分析算数表达式由下面的文法产生：e e+t | et | tt t*f | t/f | ff id | (e) | num2实验要求用非递归的预测分析方法实现，输出分析过程中所用产生式序列九、 实验步骤1）消除文法中存在的左递归2）为上步中得到的文法构造预测分析表3）编码实现教材p.79算法4.1 非递归的预测分析方法4）编码、调试5）设计测试用例（编写pascal程序，对其进行词法、语法分析，对输出结果进行分析），完成测试报告十、 可研究与探索的问题分析过程中的错误处理与恢复问题十一、 实验报告要求实验报告要求涵盖以下内容：1实验题目2实验目的和要求3实验环境4设计，包括： 1) 实现方法

16、2) 消除左递归后的文法、预测分析表 3) 语法分析器的输入、输出 4) 语法分析器的算法逻辑描述5编码（源程序）6测试报告（测试用例、测试结果、测试结果分析）7实验总结 1) 实验中遇到或存在的主要问题 2) 体会/收获 3) 改进建议实验六 语义分析器的设计与实现一、 实验类别：综合型实验二、 实验目的1通过实验进一步理解和掌握语义分析器的工作原理2进一步理解和掌握语法制导翻译技术3熟悉c语言环境编程三、 实验学时：4学时四、 实验组人数：1-2人五、 实验设备环境1windows 2000/windows xp2microsoft virtual c+ 6.0六、 实验原理（知识点）综合

17、属性、继承属性语法制导定义、语法制导翻译方案s-属性定义的自底向上翻译七、 教学要点与学习难点1本实验教学的要点语法制导定义的设计，包括属性的定义、语义规则的定义2本实验教学的难点语法制导翻译程序的设计与实现八、 实验内容和要求1实验内容编写程序，实现对算数表达式进行语义分析，所分析算数表达式由下面的文法产生：e e+t | et | tt t*f | t/f | ff(e) | num | num.num2实验要求1）对表达式的类型进行检查，输出在分析过程中识别出的每个表达式的类型2）计算表达式的值，输出在分析过程中识别出的每个表达式的值3）用自底向上的语法制导翻译技术实现对表达式的分析和翻

18、译九、 实验步骤1）设计满足翻译要求的语法制导定义2）构造文法的lr分析表3）定义分析栈的结构4）编码实现语法制导翻译程序、调试5）设计测试用例（编写pascal程序，对其进行词法、语法分析，语义翻译，对输出结果进行分析），完成测试报告十、 可研究与探索的问题分析过程中的错误处理与恢复问题十一、 实验报告要求实验报告要求涵盖以下内容：1实验题目2实验目的和要求3实验环境4设计，包括： 1) 实现方法 2) 设计的语法制导定义、lr分析表 3) 语义分析器的输入、输出 4) 语法分析器的算法逻辑描述5编码（源程序）6测试报告（测试用例、测试结果、测试结果分析）7实验总结 1) 实验中遇到或存在的

19、主要问题 2) 体会/收获 3) 改进建议编译原理与技术课程设计一、 实验类别：综合型实验二、 实验目的1加深理解、进而掌握编译程序的设计原理2理解并掌握编译程序的设计与实现技术3锻炼学生理解问题、分析问题、解决问题的能力4锻炼培养学生团队合作精神、组织协调能力5进一步锻炼学生编程实践能力三、 实验学时：17学时四、 实验组人数：5-6人五、 实验设备环境1windows 2000/windows xp2microsoft virtual c+ 6.03parser generator （for windows）六、 实验原理（知识点）词法分析、语法分析、语法制导翻译、代码生成七、 教学要点与

20、学习难点1本实验教学的要点语法制导定义的设计，包括属性的定义、语义规则的定义2本实验教学的难点语法制导翻译程序的设计与实现八、 实验内容和要求1实验内容设计并实现一个pascal子集sub_p的编译程序2实验要求 按照如下sub_p的语法、并参考pascal语言的语义，设计并实现该子集语言的编译程序，给出各阶段的设计资料和实现成果。下面是关于sub_p语言说明。1） 关键字 该子集语言sub_p中涉及到的关键字有and、array、begin、boolean、do、else、end、false、function、if、integer、not、of、or、procedure、program、re

21、ad、real、record、then、true、var、while、write。2） 专用符号该子集语言sub_p中用到的符号有+、-、*、/、=、=、:=、;、.、(、)、/*、*/。3） sub_p的词法说明l 程序中的注释可以出现在任何单词符号之后，用分界符和或/*和*/括起来。所构造编译程序应能够去掉源程序中的注释。l 程序中的关键字（除开头的program和末尾的end之外），其前、后必须有空格符或换行符，其它单词符号间的空格符是可选的。l 关键字作为保留字。l 标识符记号id匹配以字母开头的字母数字串，其最大长度规定为8个字符。用正规定义式描述为：letter a-za-zdig

22、it 0-9id letter ( letter | digit ) *l “数”的记号num匹配无符号整型常数或无符号实型常数。用正规定义式描述为：digits digit digit *optional_fraction . digits | eoptional_exponent ( e ( + | - | e ) digits ) | enum digits optional_fraction optional_expinentl 关系运算符relop代表 =、=l addop代表运算符 +、-和orl mulop代表运算符 *、/、div、mod和andl assignop代表赋值号:

23、=4） 子集语言sub_p的语法(1) program program_head program_body .(2) program_head program id ( identifier_list );(3) program_body declarations subproc_declarations compound_statement (4) identifier_list identifier_list , id | id(5) declarations var declaration ; | e(6) declaration declaration ; identifier_lis

24、t : type | identifier_list : type(7) type standard_type | array digits . digits of standard_type | record declaretion end(8) standard_type integer | real | boolean | num . num(9) subproc_declarations subproc_declarations subproc_declaration; |e(10) subproc_declaration subproc_head declarations compo

25、und_statement (11) subproc_head function id arguments : standard_type ; | procedure id arguments ;(12) arguments ( parameter_list ) | e(13) parameter_list parameter_list ; identifier_list : type | identifier_list : type(14) compound_statement begin optional_statements end(15) optional_statements sta

26、tement_list | e(16) statement_list statement_list ; statement | statement(17) statement variable assignop expression | procedure_statement | compound_statement | if expression then statement else statement | while expression do statement | read ( identifier_list ) | write ( identifier_list )(18) var

27、iable id | id expression (19) procedure_statement id | id ( expression_list )(20) expression_list expression_list , expression | expression(21) expression simple_expression relop simple_expression | simple_expression(22) simple_expression term | sign term | simple_expression addop term(23) term term

28、 mulop factor | factor(24) factor id | id ( expression_list ) | num | ( expression ) | not factor | true | false(25) sign + | -5） 程序结构说明 该文法产生的一个程序可以包含若干个全程变量声明、过程和函数定义、以及作为主程序体的复合语句。 对全程变量可以进行静态存储分配，也可以分配在主程序的活动记录中。过程或函数中声明的变量分配在其活动记录里。过程和函数都可以递归调用，并且参数的传递可以采用传值和传地址的方式。 该文法是一个lalr(1)文法。对文法消除左递归以后，可

29、以采用递归下降方法进行分析。 需要注意的是，对无参函数的调用和对简单变量的引用这两种情况，在语法上没有区别，都可以由产生式 factor id 生成，就是说，如果 b 已经被说明为函数，则赋值语句 a:=b 把函数b的返回值赋予a。 另外，有能力的同学可以把子集扩大，如增加类型、语句，进行代码优化等。九、 实验步骤 分阶段开发程序，分阶段进行测试，这样可以保证每个局部结果的正确，从而保证最终结果的正确。在开发过程中采用“滚雪球”的方法可以使工作顺利进行，企图一步到位，往往欲速则不达。下面是关于sub_p编译程序的设计中要注意的几点说明。1） 设计符号表及其管理程序 首先需要设计符号表的结构，允

30、许在编译的各个阶段插入或查找名字的相关信息，并且能够反映出名字声明所在的位置，即作用域信息，这就需要相应的管理程序来实现对符号表的各种操作：l 查找操作，即按给定的名字查表，若查找成功则返回该行的指针，若查找失败则返回空指针。l 插入操作，即按给定的名字查表，若查找失败，则在表中建立新的一行，并返回该行的指针；若查找成功则报错。l 定位操作，即为子过程或函数中声明的局部名字创建符号子表。l 重定位操作，即从符号表中删除局部于给定函数或过程的所有名字。2） 设计词法分析器 需要考虑单词符号的种类及其内部编码（这就需要设计翻译表）、行计数等，把词法分析器作为语法分析器调用的函数,词法分析器以二元式

31、的形式输出单词符号的类别编码和属性值。 可以用手工编写实现，建议用词法分析程序生成器lex实现。3） 设计语法分析器 选择适当的分析方法（如预测分析方法或lr分析方法），手工地设计语法分析器；建议用语法分析程序生成器yacc实现。 如用预测分析方法实现，则首先必须消除文法中存在的左递归。4） 设计语义动作和翻译程序 按照pascal语言的语义设计语义动作。为了便于语法制导翻译，需要对给定的文法进行改造，要注意数据类型的相容性，必要时要进行数据类型转换（如inttoreal）。 注意：l 本语言不包括过程嵌套l 收集信息并插入符号表中l 需要进行类型检查，类型检查器要做的处理有：类型是否为空类型

32、、整型、实型、子界、布尔、数组、记录、及函数/过程等；数组引用时维数一致性及越界检查；函数/过程调用时参数的个数及类型的一致性检查等。l 用三地址代码或四元式组作为中间表示，在写程序之前，先设计语义动作，写出翻译方案。5） 目标代码生成程序 以intel兼容微机作为目标机器，采用汇编语言作为目标语言，利用第九章介绍的目标代码生成算法设计目标代码生成程序。6） 错误处理与恢复 在词法分析、语法分析、语义分析、代码生成等各个过程中都要考虑错误的处理与恢复。对于所发现的错误，应打印错误信息（包括错误的行/列位置、错误的具体性质），如有可能，还应对错误进行适当的恢复，并继续进行编译，以便在每次编译中可

33、以发现多个错误。可以编制一个独立的错误处理程序供其他过程调用，根据参数的值执行相应的程序段，完成错误处理及恢复任务。7） sub_p编译程序的测试 当产生了可执行的sub_p编译程序之后，需要对它进行测试，以验证它是否可以正确地完成预期的翻译任务。如果测试失败，则根据失败的原因进行调试。 首先,设计小的、功能单一的测试用例程序，以验证sub_p编译程序个部分的功能。如验证词法分析器是否可发现关键字的拼写错误；是否可检查出缺少运算对象、缺少运算符号、括号不匹配、缺少分号、缺少end、注释未结束等语法错误；是否可以检查出名字未定义而使用的情况、数组是否越界、运算对象的类型是否一致、实参与形参是否匹

34、配等语义错误。 然后，用所构造的程序编译下面的测试程序test，检查是否能够生成目标代码，并能正确执行。程序test读入两个整型数，输出它们的最大公约数。program test(input,output);var x,y:integer;function gtcomdiv(a,b:integer):integer;begin if b=0 then gtcomdiv:=a else gtcomdiv:= gtcomdiv (b,a mod b)end;begin read(x,y); write(gtcomdiv (x,y)end. 最后，用子集语言sub_p编写快速排序的程序sort，并程

35、序sort测试所得到的编译程序。十、 可研究与探索的问题代码优化问题十一、 实验报告要求实验报告要求涵盖以下内容：1设计的题目、内容和要求2总体设计说明，包括： 需求分析，包括数据流图、功能及数据说明等。 软件的总体结构，包括功能模块的划分、总体结构图等。3各部分的详细设计说明，包括： 接口描述 功能描述 所用数据结构说明 算法描述4程序清单 注意编程风格，如： 使用有意义的变量名、程序的缩排、程序的内部注释5测试报告，包括： 测试的功能 测试用例、预期的结果 测试结果及其分析 在设计测试计划时，不但要考虑正确的测试用例，还要考虑含有错误的测试用例。6实验总结 1) 实验中遇到或存在的主要问题

36、 2) 体会/收获 3) 改进建议附录a： parser generator的使用说明一、 directory settings 按照以下图示步骤，在microsoft visual c+ （version 6.00）中进行设置，只需设置一次。1进入virtual c+ 选项设置页面图1 进入选项设置页面2选择directories页面设置1）include 路径platform：win32show directories for：include files增加：parser generatorinclude图2 设置include 路径2）library 路径platform：win32show directories for：library files增加：parser generatorlibmsdev图3 设置library 路径3）source 路径platform：win32show directories for：source files增加：parser gen