《编译原理实验指导书》由会员分享，可在线阅读，更多相关《编译原理实验指导书（31页珍藏版）》请在金锄头文库上搜索。
1、编译原理实验指导信息科学与工程学院计算机系2009.12.25实验一 词法分析程序一、目的和内容1实验目的：通过完成词法分析程序，了解词法分析的过程。2. 实验内容：用C / C+实现对Pascal的子集程序设计语言的词法识别程序。3实验要求：将该语言的源程序，也就是相应字符流转换成内码，并根据需要是否对 于标识符填写相应的符号表供编译程序的以后各阶段使用。二、程序设计语言的描述程序设计语言的描述采用扩充的 BNF 表示：程序f 程序首部 分程序.程序首部f PROGRAM标识符；分程序f 常量说明部分 变量说明部分 过程说明部分 复合语句常量说明部分fCONSTv常量定义, 常量定义；常量定
2、义标识符=无符号整数变量说明部分fVAR变量定义（； 变量定义）；变量定义标识符，标识符： 类型 类型 fINTEGERILONG过程说明部分f过程首部分程序；过程首部分程序；过程首部f PROCEDURE标识符；| PROCEDURE标识符（标识符： 类型）；语句f赋值语句|条件语句|当型循环语句|过程调用语句|读语句|写语句|复合语句| 8赋值语句 一标识符：=表达式条件语句fIFv条件THEN句当型循环语句fWHILEv条件DOv语句过程调用语句f标识符|标识符（表达式）读语句fREAD（标识符，标识符）写语句fWRITE（v表达式, 表达式）复合语句fBEGIN语句； 语句END条件f
3、 表达式 关系运算符 表达式 | ODD 表达式v表达式f +|-项加型运算符 项项 因子乘型运算符 因子因子f标识符|无符号整数| （表达式）加型运算符f+|-f * | /lvlv=ll=其中：用左右尖括号括起的字符串表示非终结符号 ：= ： 定义为 ：表示该语法成分可以 0n 次重复。 ：表示方括号内为可选项，即 0 或 1 次。三、程序设计语言单词的内部编码如表 1-1 为词法分析中的内码单词对照表。表 1-1 内部码对照表内码单词内码单词内码单词内码单词1PROGRAM2CONST3VAR4INTEGER5LONG6PROCEDURE7IF8THEN9WHILE10DO11READ1
4、2WRITE13BEGIN14END15ODD16+17-18*19/20=21222325=26272829:30:=31(32)33无符号整数34标识符35#四、词法分析程序的设计思想 为了实现的编译程序实用，这里规定源程序可采用自由书写格式，即一行内可以书写多 个语句，一个语句也可以占领多行书写；标识符的前 20 个字符有效；整数用2 个字节表示； 长整数用 4个字节表示。这样词法分析程序的主要工作为：（1）从源程序文件中读入字符。（2）统计行数和列数用于错误单词的定位。（3）删除空格类字符，包括回车、制表符空格。（4）按拼写单词，并用（内码，属性）二元式表示。（5）根据需要是否填写标识
5、符表供以后各阶段使用。 这里采用的编译程序的实现方法是一遍扫描，即从左到右只扫描一次源程序，也就是词 法分析作为语法分析的一个子程序。故在编写词法分析程序时，用重复调用词法分析子程序 取一单词的方法得到整个源程序的内码流。扫描程序流程图，如图 1-1。取单词子程序流程 图；如图 1-2。取字符和统计字符行列位置子程序；如图 1-3。图 1-1 词法分析总程序流程图实验二 语法分析 1递归子程序法一、目的和内容1、实验目的：通过完成语法分析程序，了解语法分析的过程和作用2、实验内容：用递归子程序法实现对pascal的子集程序设计语言的分析程序3、实验要求：对源程序的内码流进行分析，如为文法定义的
6、句子输出 ”是”否则输出”否”,根据需要处理说明语句填写写相应的符号表供以后代码生成时使用二、文法的改变为适合递归子程序法，对实验一中的文法改写成无左递归和无左共因子的BNF如下:程序f 程序首部 分程序。程序首部f PROGRAM标识符；分程序f常量说明部分 变量说明部分 过程说明部分 复合语句常量说明部f CONSTv常量定义 常量定义后缀I 常量定义标识符=无符号整数常量定义后缀-, 常量定义常量定义后缀I变量说明部分f VARv变量定义 变量定义后缀I 变量定义标识符标识符后缀： 类型；标识符后缀f,标识符 标识符后缀 I 变量定义后缀f 变量定义 变量定义后缀 I 类型 f INTE
7、GER I LONG过程说明部分f 过程首部分程序; 过程说明部分后缀|过程首部f PROCEDURE标识符 参数部分；参数部分f（标识符： 类型）|过程说明部分后缀f 过程首部分程序; 过程说明部分后缀|语句f赋值或调用语句lv条件语句IV当型循环语句lv读语句|写语句 IV复合语句I赋值或调用语句f标识符V后缀V后缀f：=表达式I（V表达式）I条件语句fIF条件THENV语句当型循环语句f WHILEv条件DO 语句读语句fREAD （标识符标识符后缀）写语句fWRITE（V表达式表达式后缀）表达式后缀f, V表过式v表达式后缀IV复合语句f BEGIN V语句V语句后缀ENDV语句后缀f
8、； V语句语句后缀IV条件f V表达式v关系运算符v表达式I ODDv表达式V表达式f+项项后缀I-v项项后缀项项后缀V项后缀f V加型运算符项项后缀I项 因子X因子后缀因子后缀f乘型运算符 因子 因子后缀le因子一标识符|无符号整数| （v表达式）加型运算符一+|-乘型运算型一*|/ 关系运算符一 =| |=|=三、非终结符和函数名对照表为适用递归子程序，表 2-1 为非终结符和函数名对照表表2-1非终符，和函数名对照表非终结符函数名非终结符函数名程序program程序首部proghead分程序block常量说明部分consexpl常量定义consdefi变量说明部分varexl常量定义后缀
9、conssuff变量定义vandefi变量定义后缀varsuff过程说明部分procdefi类型typeil过程首部procedh过程说明部分后缀procsuff赋值或调用语句assipro语句sentence后缀suffix条件语句ifsent读语句read当型循环语句whilsent标识符后缀idsuff写语句Write复合语句compsent表达式后缀Exprsuff语句后缀sentsuff条件Conditio项后缀termsuff表达式Express项term因子后缀Factsuff参数部分argument因子Factor加型运算符addoper乘型运算符Muloper关系运算符res
10、poper四、递归子程序的设计思想为每个非终结符设计一个识别的子程序，寻找该非终结符也就是调用相应的子程序。由 于单词在语法分析中作为一个整体，故在语法识别中仅使用其内码。在这里将词法分析作为 语法分析的一个子程序，当语法分析需要单词时，就调用相应的词法分析程序获得一个单词 语法分析的作用是识别输入符号串是否是文法上定义的句子，即判断输入符号串是否是满足 “程序”定义的要求。也就是当语法识别程序从正常退出表示输入符号串是正确的“程序”； 若从出错退出，则输入符号串不是正确的“程序”。出错时，可以根据读字符的位置判断出 错的位置。五、部分子程序流程图图 2-1a 表示程序是由首部、分程序和“”组
11、成的；图 2-1b 表示程序首部的组成；图2-lc为分程序的语法成分，图2-ld表示语句的组成；图2-le为因子的构成。（分程序*常量说明部分 变量说明部分 1过程说明部分语句 一返回图 2-lc图 2-l 部分递归子程序的流程图语句N*条件语句图 2-ld图 2-le*赋值或调用语句NWHILENYREADN因子NN出错取下一 个单词符号整数N*当型循环语句*读语句*写语句*复合语句取下一个单词、Y1-取下一个单词1YY取下一个单词J表达示N出错图 2-l 部分递归子程序的流程图实验三 语法分析 2预测分析法返回一、目的和内容1、实验目的：通过完成预测分析法的语法分析程序，了解预测分析法和递
12、归子程序法的 区别和联系。2、实验内容：构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分 析程序。3、实验要求：源程序的内码流用预测分析法进行分析。如为文法定义的句子输出“是”， 否则输出“否”，并根据需要处理说明语句填写相应的符号表供以后代码生成时使用。二、文法的改变由于预测分析和递归子程序都是自顶向下的分析方法，且在实验二中已将它变换成无回 溯的和无左公因子的文法。则可直接用实验二中的文法。三、非终结符的内码表 为了将非终结符和终结符一起存入栈参，将非终结符的内码从128 开始标记。其对照表 见表 3-1。表 3-1 非终结符和内码对照表128131134137140143146149152155158161非终结符程序常量说明部分变量说明部分类型过程说明部分后缀后缀读语句表达式后
