陈志刚《编译原理》实验指导书.doc

编译原理实验指导书编著 陈志刚中南大学软件学院2006年11月9第一部分 词法分析（实验一必作）实验一 词法分析程序设计与实现一、实验目的加深对词法分析器的工作过程的理解；加强对词法分析方法的掌握；能够采用一种编程语言实现简单的词法分析程序；能够使用自己编写的分析程序对简单的程序段进行词法分析。二、实验内容自定义一种程序设计语言，或者选择已有的一种高级语言，编制它的词法分析程序。词法分析程序的实现可以采用任何一种编程语言和编程工具。从输入的源程序中，识别出各个具有独立意义的单词，即关键字、标识符、常数、运算符、界符。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）三、实验要求：1. 对单词的构词规则有明确的定义；2. 编写的分析程序能够正确识别源程序中的单词符号；3. 识别出的单词以的形式保存在符号表中，正确设计和维护符号表；4. 对于源程序中的词法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成整个源程序的词法分析；四、实验步骤1. 定义目标语言的可用符号表和构词规则；2. 依次读入源程序符号，对源程序进行单词切分和识别，直到源程序结束；3. 对正确的单词，按照它的种别以的形式保存在符号表中；4. 对不正确的单词，做出错误处理。五、实验报告要求详细说明你的程序的设计思路和实现过程。用有限自动机或者文法的形式对词法定义做出详细说明，说明词法分析程序的工作过程，说明错误处理的实现。参考资料一、程序要求1、以下面一段程序为例main() int a,b;a = 10; b = a + 20;2、需要识别的词1. 关键字：if、int、for、while、do、return、break、continue；单词种别码为1。2. 标识符；单词种别码为2。3. 常数为无符号整形数；单词种别码为3。4. 运算符包括：+、-、*、/、=、=、=、!= ；单词种别码为4。5. 分隔符包括：,、;、(、)； 单词种别码为5。3、程序输出形式要求输出下面的形式：（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，”“）二、程序设计思路这里以开始定义的C语言子集的源程序作为词法分析程序的输入数据。在词法分析中，自文件头开始扫描源程序字符，一旦发现符合“单词”定义的源程序字符串时，将它翻译成固定长度的单词内部表示，并查、填适当的信息表。经过词法分析后，源程序字符串（源程序的外部表示）被翻译成具有等长信息的单词串（源程序的内部表示），并产生两个表格：常数表和标识符表，它们分别包含了源程序中的所有常数和所有标识符。1. 定义部分：定义常量、变量、数据结构。2. 初始化：从文件将源程序全部输入到字符缓冲区中。3. 取单词前：去掉多余空白。4. 取单词：利用实验一的成果读出单词的每一个字符，组成单词，分析类型。5. 显示结果。第二部分 语法分析（任选其中一个做实验）实验二 预测分析法设计与实现一、实验目的加深对语法分析器工作过程的理解；加强对预测分析法实现语法分析程序的掌握；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译。二、实验内容在实验1的基础上，用预测分析法编制语法分析程序，语法分析程序的实现可以采用任何一种编程语言和工具。三、实验要求：1. 对语法规则有明确的定义；2. 编写的分析程序能够对实验一的结果进行正确的语法分析；3. 对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程；4. 实验报告要求用文法的形式对语法定义做出详细说明，说明语法分析程序的工作过程，说明错误处理的实现。四、实验步骤1. 定义目标语言的语法规则；2. 求解预测分析方法需要的符号集和分析表；3. 依次读入实验一的分析结果，根据预测分析的方法进行语法分析，直到源程序结束；4. 对遇到的语法错误做出错误处理。五、实验报告要求详细说明你的程序的设计思路和实现过程。实验报告要求用文法的形式对语法定义做出详细说明，说明语法分析程序的工作过程，说明错误处理的实现。实验三 算符优先分析法设计与实现一、实验目的加深对语法分析器工作过程的理解；加强对算符优先分析法实现语法分析程序的掌握；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译。二、实验内容在实验1的基础上，用算符优先分析法编制语法分析程序，语法分析程序的实现可以采用任何一种编程语言和工具。三、实验要求：1. 对语法规则有明确的定义；2. 编写的分析程序能够对实验一的结果进行正确的语法分析；3. 对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程；四、实验步骤1. 定义目标语言的语法规则；2. 求解预测分析方法需要的符号集和分析表；3. 依次读入实验一的分析结果，根据预测分析的方法进行语法分析，直到源程序结束；4. 对遇到的语法错误做出错误处理。五、实验报告要求详细说明你的程序的设计思路和实现过程。实验报告要求用文法的形式对语法定义做出详细说明，说明语法分析程序的工作过程，说明错误处理的实现。实验四 递归下降分析法设计与实现一、实验目的根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。二、实验内容程序输入/输出示例（以下仅供参考）： 对下列文法，用递归下降分析法对任意输入的符号串进行分析： （1）E-TG（2）G-+TG|TG（3）G-（4）T-FS（5）S-*FS|/FS（6）S-（7）F-(E)（8）F-i输出的格式如下：(1)递归下降分析程序，编制人：姓名，学号，班级(2)输入一以#结束的符号串(包括+*/（）i#)：在此位置输入符号串例如：i+i*i# (3)输出结果：i+i*i#为合法符号串备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。注意：1. 表达式中允许使用运算符（+-*/）、分割符（括号）、字符I，结束符#； 2. 如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）。三、实验要求：1. 对语法规则有明确的定义；2. 编写的分析程序能够对实验一的结果进行正确的语法分析；3. 对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程；四、实验报告要求详细说明递归下降分析法程序的工作过程，并且详细说明你的程序的设计思路和实现。实验五 LR(1)分析法设计与实现一、实验目的构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。二、实验要求程序输入/输出示例（以下仅供参考）： 对下列文法，用LR（1）分析法对任意输入的符号串进行分析： （1）E-E+T（2）E-ET（3）T-T*F（4）T-T/F（5）F-(E)（6）F-i输出的格式如下：(1)LR（1）分析程序，编制人：姓名，学号，班级(2)输入一个以#结束的符号串(包括+*/（）i#)：在此位置输入符号串 (3)输出过程如下：步骤 状态栈 符号栈 剩余输入串 动作 10#i+i*i#移进(4)输入符号串为非法符号串(或者为合法符号串)备注：1. 在“所用产生式”一列中如果对应有推导则写出所用产生式；如果为匹配终结符则写明匹配的终结符；如分析异常出错则写为“分析出错”；若成功结束则写为“分析成功”。2. 在此位置输入符号串为用户自行输入的符号串。注意：1. 表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#； 2. 如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；3. 对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个