编译原理实验指导书2009..doc

编译原理实验指导 信息科学与工程学院 计算机系 2009.12.25 实验一 词法分析程序 一、目的和内容 1．实验目的：通过完成词法分析程序，了解词法分析的过程。 2．实验内容：用C／C++实现对Pascal的子集程序设计语言的词法识别程序。 3．实验要求：将该语言的源程序，也就是相应字符流转换成内码，并根据需要是否对于标识符填写相应的符号表供编译程序的以后各阶段使用。 二、程序设计语言的描述 程序设计语言的描述采用扩充的BNF表示： 程序→程序首部分程序． 程序首部→PROGRAM标识符； 分程序→[常量说明部分][变量说明部分][过程说明部分]复合语句 常量说明部分→CONST常量定义{，常量定义}； 常量定义→标识符=无符号整数 变量说明部分→VAR变量定义(；变量定义)； 变量定义→标识符{，标识符}：类型 类型→INTEGER|LONG 过程说明部分→过程首部分程序；{过程首部分程序；} 过程首部→PROCEDURE标识符；| PROCEDURE标识符(标识符：类型)； 语句→赋值语句|条件语句|当型循环语句|过程调用语句 |读语句|写语句|复合语句|ε 赋值语句→标识符：=表达式 条件语句→IF条件THEN语句 当型循环语句→WHILE条件DO语句 过程调用语句→标识符 | 标识符(表达式) 读语句→READ(标识符，{标识符}) 写语句→WRITE(表达式{，表达式}) 复合语句→BEGIN语句{；语句}END 条件→表达式关系运算符表达式 | ODD表达式 表达式→[+|-]项{加型运算符项} 项→因子{乘型运算符因子} 因子→标识符 | 无符号整数 | (表达式) 加型运算符→+|- 乘型运算符→* | / 关系运算符→=|||=||= 其中： ? ：用左右尖括号括起的字符串表示非终结符号 ：：= ： 定义为 { }：表示该语法成分可以0—n次重复。 [ ]：表示方括号内为可选项，即0或1次。 三、程序设计语言单词的内部编码 如表1-1为词法分析中的内码单词对照表。 表1-1 内部码对照表 内码 单词 内码 单词 内码 单词 内码 单词 1 PROGRAM 2 CONST 3 VAR 4 INTEGER 5 LONG 6 PROCEDURE 7 IF 8 THEN 9 WHILE 10 DO 11 READ 12 WRITE 13 BEGIN 14 END 15 ODD 16 + 17 - 18 * 19 / 20 = 21 22 23 = 24 25 = 26 . 27 . 28 ; 29 : 30 := 31 ( 32 ) 33 无符号整数 34 标识符 35 # 四、词法分析程序的设计思想 为了实现的编译程序实用，这里规定源程序可采用自由书写格式，即一行内可以书写多个语句，一个语句也可以占领多行书写；标识符的前20个字符有效；整数用2个字节表示；长整数用4个字节表示。这样词法分析程序的主要工作为： （1）从源程序文件中读入字符。 （2）统计行数和列数用于错误单词的定位。 （3）删除空格类字符，包括回车、制表符空格。 （4）按拼写单词，并用（内码，属性）二元式表示。 （5）根据需要是否填写标识符表供以后各阶段使用。 这里采用的编译程序的实现方法是一遍扫描，即从左到右只扫描一次源程序，也就是词法分析作为语法分析的一个子程序。故在编写词法分析程序时，用重复调用词法分析子程序取一单词的方法得到整个源程序的内码流。扫描程序流程图，如图1-1。取单词子程序流程图；如图1-2。取字符和统计字符行列位置子程序；如图1-3。 实验二 语法分析1——递归子程序法 一、目的和内容 实验目的：通过完成语法分析程序，了解语法分析的过程和作用 实验内容：用递归子程序法实现对pascal的子集程序设计语言的分析程序 实验要求：对源程序的内码流进行分析，如为文法定义的句子输出”是”否则输出”否”,根据需要处理说明语句填写写相应的符号表供以后代码生成时使用 二、文法的改变 为适合递归子程序法，对实验一中的文法改写成无左递归和无左共因子的ＢＮＦ如下： 程序→程序首部分程序。 程序首部→PROGRAM标识符； 分程序→常量说明部分变量说明部分过=无符号整数 常量定义后缀→，常量定义常量定义后缀?|ε 变量说明部分→VAR变量定义变量定义后缀 |ε 变量定义→标识符标识符后缀：类型； 标识符后缀→，标识符标识符后缀?|ε 变量定义后缀→变量定义变量定义后缀?|ε 类型→INTEGER | LONG 过程说明部分→过程首部分程序；过程说明部分后缀|ε 过程首部→PROCEDURE标识符参