编译技术课程设计B实验指导书.doc

编译技术实验指导书实验一 词法分析器设计实验名称：词法分析器设计 实验类型: 设计性实验学时：.5天适用对象: 计算机科学与技术专业一、实验目的 本实验是为计算机科学与技术专业的学生在学习编译技术课程后，为加深对课堂教学内容的理解，培养解决实际问题能力而设置的实践环节。通过这个实验，使学生应用编译程序设计的原理和技术设计出词法分析器，了解扫描器的组成结构，不同种类单词的识别方法。能使得学生在设计和调试编译程序的能力方面有所提高，为将来设计、分析编译程序打下良好的基础。二、实验要求设计一个扫描器，该扫描器是一个子程序，其输入是源程序字符串，每调用一次识别并输出一个单词符号。为了避免超前搜索，提高运行效率，简化扫描器的设计，假设该程序设计语言中，基本字（也称关键词）不能作一般标识符用，如果基本字、标识符和常数之间没有确定的运算符或界符作间隔，则用空白作间隔。单词符号及其内部表示如表2-1所示，单词符号中标识符由一个字母后跟多个字母、数字组成，常数由多个十进制数字组成。单词符号的内部表示，即单词的输出形式为二元式：（种别编码,单词的属性值）。表2-1单词符号及其内部表示单词符号种别编码单词的属性值BEGINIFTHENELSEEND标识符整型常数+*（）123456789101112在名字表中的地址十进制整数三、实验原理根据设计扫描器的一般设计方法：对给出的单词语法结构，由单词的语法规则出发，画出识别单词的状态转换图，然后再用程序实现的扫描器设计方法。用程序实现识别单词符号的状态转换图就能得到所要求的扫描器，其方法是对应每一个状态结点设计一个程序段，完成在读进可能输入的符号后该状态下所做的工作，再设计一个控制程序,通过判别当前状态和输入字符确定执行哪个状态对应的程序段。由于设计的扫描器是一个子程序，调试时需设计一个主程序（代表语法分析器）调用它，扫描器将来在语法分析器、语义分析器设计中还要被使用。在程序设计中需要解决以下几个问题：1.源程序字符串的输入输入源程序字符串可以用键盘以字符方式先读入到一个输入缓冲区（字符数组），这样也便于字符回退，再由扫描器一个个读入。也可以直接从键盘以字符方式读入，这时应保存当前输入字符，若它是多读进的字符，则作为下一个单词的第一个字符使用。2.标识符和常数的属性值标识符和常数的属性值（自身值）是该单词在名字表或常数表中登记项的相对地址，当识别出一个标识符或常数时，要查名字表或常数表，若表中有其登记项，则把得到的登记项地址作为其属性值；若表中没有其登记项，则建立一个新登记项，该登记项地址作为其属性值。为了在调试时便于验证输出单词的正确性，也可以输出标识符的字符串编码或常数的十进制表示，即表示为:(6,标识符的字符串)或(7,常数的十进制表示)。四、实验所需仪器、设备、材料PC微机、Windows操作系统、C+或java语言。五、实验预习要求、实验条件、方法及步骤 为了充分利用上机时间，在进行编译技术上机实验前应做好各种准备工作，具体应包括：(1)复习与上机题目有关的知识，熟悉有关定义、概念和实现算法。(2)设计出程序流程框图和数据结构，编写出完整的源程序，进行静态检查。(3)为所编写的程序构思一个运行、调试环境，例如，以什么方式提供输入数据、显示输出数据，如何调用（或启动）编写的程序。制定出程序调试计划和典型输入代码数据。六、思考题 (1)为什么将词法分析器设计为一个子程序？(2) 状态转换图与程序框图有什么区别？七、参考书(1)程序设计语言编译原理(2)计算机综合实践指导 实验二 算符优先分析程序设计实验名称：算符优先分析程序设计 实验类型: 设计性实验学时：.5天适用对象: 计算机科学与技术专业一、实验目的 本实验是为计算机科学与技术专业的学生在学习编译技术课程后，为加深对课堂教学内容的理解，培养解决实际问题能力而设置的实践环节。通过这个实验，使学生应用编译程序设计的原理和技术, 设计、编写和调试算符优先分析程序，了解算符优先分析程序的组成结构，掌握实现通用算符优先分析算法的方法。能使得学生在设计和调试编译程序的能力方面有所提高。为将来设计、分析编译程序打下良好的基础。二、实验要求算符优先分析属于自下而上的分析方法，该语法分析程序的输入是终结符号串（即单词符号串，以一个“”结尾），如果输入串是句子则输出“YES”，否则输出“NO”和错误信息。算符优先分析过程与非终结符号无关，当由文法产生了优先关系之后文法也就失去了作用,本题目给出文法的目的是为了便于对语法分析结果进行验证。(1)文法设算符优先文法为： 说明：i为整型常数或者为标识符表示整型变量；使用中用*表示。(2)优先关系表设优先关系表如表2-3所示。表2-3优先关系表+ * i ( ) # + * i ( ) # 三、实验原理(1)算符优先分析算法算符优先分析算法中需要使用分析栈存放文法符号，变量为栈的栈顶指针,变量存放当前输入符号。为错误处理程序，分析算法见程序设计语言编译原理P93。(2)算符优先方法的程序设计在程序设计中需要解决以下几个问题：涉及到的主要数据结构1)优先关系表用一个数组表示，是一个n*n的二维数组（n=文法中终结符号个数+1），其下标为终结符号，其元素的值为终结符号（将“”看作一个特殊的终结符号）对之间的优先关系：“”、“”、“”之一或者为错误类型（题目给出的优先关系表若该位置为空，则通过自己分析，填上适当的错误类型标志），,。2)分析栈用数组表示，的元素是终结符号、“”或非终结符。错误处理程序该分析程序有错误处理功能，如果分析栈的栈顶元素与当前输入符号之间没有优先关系，说明输入串有语法错误，应该输出错误信息：错误类型、出错位置,并停止语法分析运行。扫描器采用实验一构造的扫描器，作为算符优先分析程序的子程序，每当需要一个单词就调用它。四、实验所需仪器、设备、材料PC微机、Windows操作系统、C+或java语言。五、实验预习要求、实验条件、方法及步骤 为了充分利用上机时间，在进行编译技术上机实验前应做好各种准备工作，具体应包括：(1)复习与上机题目有关的知识，熟悉有关定义、概念和实现算法。(2)设计出程序流程框图和数据结构，编写出完整的源程序，进行静态检查。(3)为所编写的程序构思一个运行、调试环境，例如，以什么方式提供输入数据、显示输出数据，如何调用（或启动）编写的程序。制定出程序调试计划和典型输入代码数据。六、思考题(1)语法分析器的一般结构是什么？(2)试将优先关系表中的空位置（无优先关系）填上错误信息。七、参考书(1)程序设计语言编译原理(2)计算机综合实践指导 实验三 基于算符优先分析方法的语法制导翻译程序设计实验名称：基于算符优先分析方法的语法制导翻译程序设计 实验类型:设计性实验等学时：2天适用对象: 计算机科学与技术专业一、实验目的 本实验是为计算机科学与技术专业的学生在学习编译技术课程后，为加深对课堂教学内容的理解，培养解决实际问题能力而设置的实践环节。通过这个实验，使学生应用编译程序设计的原理和技术, 通过设计、编写和调试语法制导翻译程序，掌握从一种语句的语法和语义出发，构造相应的语义子程序，实现基于算符优先分析方法的语法制导翻译的方法。能使得学生在设计和调试编译程序的能力方面有所提高。为将来设计、分析编译程序打下良好的基础。二、实验要求算符优先分析方法是通过反复把输入符号移进分析栈，使用优先关系表在分析栈顶寻找最左素短语，将其归约为一个非终结符号而实现的。这个分析过程与非终结符号无关，当由文法产生了优先关系之后文法也就失去了作用（所以本题目无需给出文法）。基于算符优先分析方法的语法制导翻译是在算符优先语法分析的基础上进行翻译工作（即语义分析），每当将一个最左素短语归约为一个非终结符号时，就调用对应产生式的语义子程序，去完成相应的语义翻译工作，这步归约使用的产生式对非终结符号不加区分（即将所有的非终结符号用一个通用的非终结符号表示）。语法制导翻译程序的输入是终结符号串（即单词符号串，以一个“”结尾），如果输入符号串是句子,则按照其语义进行翻译,输出等价的四元式序列（作为练习应显示输出）。三、实验原理(1)算符优先语法分析程序设算符优先语法分析程序使用的算符优先关系表和分析算法由实验二给出，该算符优先语法分析程序实现了对算术表达式的语法分析。(2)产生式的语义动作由于算符优先分析方法对产生式的非终结符号不加区分，这里将文法中的非终结符号只用一个表示，各产生式的语义动作表示如下：注：i为整型常数或者为标识符表示整型变量；E为算术表达式，为了区分同一个产生式中不同的非终结符号E，使用了下脚标加以区别；在使用中用*表示； (3)语法制导翻译程序设计为了实现算数表达式的语法制导翻译，按照给出产生式的语义动作,对每个产生式设计出相应的语义子程序，语义子程序使用产生式右部文法符号的语义值，这些语义值取自符号表（终结符号）或分析栈的语义值部分（非终结符号），生成四元式（填入四元式表）和产生式左部文法符号的语义值（存入分析栈的语义值部分），语义子程序的调用由算符优先语法分析程序完成。语义值是非终结符号的一个语义值，表示算术表达式值的存放地址（待分配存储空间后，由此可得到实际存储单元地址）。语义过程、和是一个函数语义过程,其功能是申请一个临时存储单元,将来存放产生式的左部符号的值，函数值是该存储单元的地址,为了简化程序设计，可以假设初值为1,每调用一次其值累加1。是一个语义过程, 其功能是生成一个四元式，将该四元式填入四元式表，该四元式实现的功能是，其中代表一种算术运算符，是非终结符号。是一个函数语义过程, 其功能是用去查常数表或者名字表，函数值是在表中的地址，它代表的语义值（待分配存储空间后，由此可得到实际存储单元地址），为了区分常数表和名字表的地址，可以将表地址加上不同的整型常数（例如：100和200）以示区别。涉及到的主要数据结构1)分析栈在算符优先语法分析中用一个一维数组表示，这里扩展为二维数组，的元素由两部分组成（共用一个栈顶指针），是终结符号、“”或非终结符，是对应中文法符号和的语义值（运算符、“（”和“）”无语义值），类型为整型，表示地址，1in 。2)四元式表用来存放翻译程序生成的四元式序列，用二维数组表示，的元素（一个四元式）由四部分组成，是运算符号（即终结符：“”、“”或“”），、和是语义值，其类型全部为整型，表示地址，1in 。3)有关算符优先语法分析的数据结构参考实验二的相关内容。扫描器采用实验一构造的扫描器，作为语法分析及语法制导翻译程序的子程序，每当需要一个单词就调用它。语义子程序的调用各产生式相应语义子程序的调用是由算符优先语法分析程序实现的。这里要根据选择先归约后调用语义子程序，还是先调用语义子程序后归约的不同情况，在分析栈上对文法符号与语义值的进、出栈进行操作时，保证栈顶指针与之做好配合。四、实验所需仪器、设备、材料PC微机、Windows操作系统、C+或java语言。五、实验预习要求、实验条件、方法及步骤 为了充分利用上机时间，在进行编译技术上机实验前应做好各种准备工作，具体应包括：(1)复习与上机题目有关的知识，熟悉有关定义、概念和实现算法。(2)设计出程序流程框图和数据结构，编写出完整的源程序，进行静态检查。(3)为所编写的程序构思一个运行、调试环境，例如，以什么方式提供输入数据、显