编译原理实验手册1.4版.doc

兰州大学计算机科学与技术专业编译原理实验手册（V1.4）第一节 概述一、实验目的编译原理是一门实践性很强的课程，但由于课时所限，只能在课堂上讲授一些通用的原理和方法。而为了真正学好这门课程，必须自己动手构造出一个编译器，才能对书里讲到的原理、方法和技术有较全面的体会，才能对学生以后的程序设计和解决实际问题的能力有所帮助。实际的编译程序是十分复杂的，有时由多达十几万条指令组成。为此，编译原理的实践教学，采用简化编译过程的办法，选择最关键的三个环节词法分析、语法分析、语义分析和中间代码产生，每个环节作为一个实践课题，逐步深入，扩展功能，直至得到一个简单实用的编译器。本实验不涉及到优化。二、实验内容任何一个实用的高级语言，其语法都比较复杂，如选其作为源语言，很难实践全过程。故本试验将定义一个简化的语言PASCAL语言的一个子集作为源语言，分三个课题、一步步地构造出它的编译程序。所有试验项目前后贯穿这一条主线进行。本实验共进行6周，每周3学时，共18学时。本实验主要包括以下三个课题：1. 词法分析：以源程序为输入，输出单词符号流；2. 语法分析：以源语言的文法为依据，调用词法分析器，使用递归下降分析法或算符优先分析法或LR(1)分析法，构造能识别源语言各种语法结构的语法分析器；(语发单元，语法树碑)3. 语义分析和中间代码产生：使用语法制导翻译技术，对源语言程序进行简单的翻译，输出四元式序列。在本节的第三部分给出了PASCAL语言两个子集的文法，对这些文法稍加变换，即可获得用于语法分析的LL(1)文法或LR(1)文法。学生可以直接选择一个作为编译器的源语言，也可以对这些文法进行改造，以获得能力更为强大的源语言。学生也可以自己设计源语言，来完成这些题目；唯一的要求是源语言必须包含三种基本的程序设计结构（顺序、选择、循环）和至少两种不同的数据类型。本实验要求： 所有的输入输出均采用文件形式。 独立完成。 语言不限，开发工具不限；但必须有可运行的程序和规范的注释。三、PASCAL语言子集的文法由于Pascal语言结构严谨，层次清晰，语法与C语言接近，也便于理解，因此本实验抽取Pascal语言的一个子集，稍加改造，作为源语言，姑且命名为LittleP。一个LittleP程序由一系列全局数据声明和一个主程序体组成。所有数据采用静态存储分配，没有I/O，只支持一种基本数据类型：无符号整数。Procedure，procedurehead，procedurebody，variable,declare,compound,Statment，definition,list,empty,variablename,style,statement,Block，condition,cycle,arithmeticexpression,relationexpression,term,add,muti,factor,num,identifier,letter,digit,endue赋予1. LittleP的文法：程序程序首部程序体程序首部 program程序名； 程序体变量声明复合语句变量声明 var变量定义列表|空 变量定义变量定义列表|变量定义；变量定义变量名列表: ； 变量名|变量名,变量名列表 integer 复合语句 begin语句块end 语句块语句语句 ；语句块语句赋值语句|条件语句|循环语句|复合语句|空赋值语句左部:= 右部 左部变量名右部算术表达式条件语句 if关系表达式then语句else语句循环语句 while关系表达式do语句 算术表达式关系运算符算术表达式 项| 算术表达式加运算符项 因子| 项乘运算符因子因子变量名(算术表达式) 整数程序名标识符变量名标识符标识符字母标识符字母标识符数字整数数字整数数字关系运算符 | = | | 加运算符 + | - 乘运算符 * | / 字母 a|b|x|y|z 数字 1|2|3|4|5|6|7|8|9|02.在此基础上加以扩充，可得功能较强的一个 LittleP 语言的超集：LittleP+。该语言引入了实数、一维数组和过程、函数的定义，参数传递采用传值方式。另外，加入了I/O支持，编译器提供两个系统函数：read()和write()。程序程序首部程序体程序首部 program程序名； 程序体变量声明复合语句变量声明 var变量定义列表|空 变量定义变量定义列表|变量定义；变量定义变量名列表: ； 变量名|变量名,变量名列表 | integer | real array 下界.上界 of 分程序 分程序声明|空分程序 分程序首部变量声明复合语句分程序首部 procedure过程名( )；| function函数名( ) : ； 形参定义 ,形参列表|形参定义|空形参定义变量名列表: 复合语句 begin语句块end 语句块语句语句；语句块语句赋值语句|条件语句|循环语句|过程调用语句|复合语句|读写语句|空赋值语句左部:= 右部左部变量名变量名 算术表达式 右部算术表达式条件语句 if关系表达式then语句else语句循环语句 while关系表达式do语句过程调用语句过程名( ) |函数名( ) 算术表达式| 算术表达式,实参列表|空读写语句 read ( ) | write ( ) 算术表达式关系运算符算术表达式 项| 算术表达式加运算符项 因子| 项乘运算符因子因子变量名(算术表达式)函数名() 变量名 算术表达式 整数实数程序名标识符变量名标识符过程名标识符函数名标识符标识符字母标识符字母标识符数字整数数字整数数字实数整数 . 整数 关系运算符 | = | | 加运算符 + | - 乘运算符 * | div | mod 字母 a|b|x|y|z|A|B|X|Y|Z数字 1|2|3|4|5|6|7|8|9|03.对源程序语法的其他说明：a) 出现在 里的所有字符作为注释跳过。b) 各单词符号之间的空格可有可无，但关键字和标识符必须分隔开来。c) 过程没有返回值，只能出现在过程调用语句中；函数有且只有1个返回值，只能出现在算术表达式中或作为赋值语句的右部。函数返回值通过函数名带回，因此在函数体内必须给函数名赋值。d) 标识符的长度不得超过8个字符。e) 关键字保留，包括read和write。四、实验要求：每个课题完成后写出实验报告。实验报告应该包括： 程序设计时考虑的算法和主要的数据结构； 可执行的程序 至少2个测试用例，包括： 至少1个合法的源程序及其运行结果； 至少1个非法的源程序及其错误报告。第二节 词法分析一、目的与要求.目的通过设计、调试词法分析程序，实现从源程序中分离出各种单词的方法；加深对课堂教学的理解，尤其是对正规式、有穷自动机的原理和用途的理解；为以后软件开发过程中设计高效率的扫描器打下基础。.要求 应有适当的预处理。 输入源程序，输出定长单词符号流，均采用文件形式。 针对选定的源语言，构造识别其合法单词符号的词法分析器。 实现时可以借助LEX（如何使用请参考教材并上网搜索资料）。 应考虑到后续阶段的需要，合理设计词法分析器的结构。 本实验应在一周内完成。二、设计步骤（要求文档）1. 问题分析：l 分析源语言的文法，找出各种词法单位的构词规则。l 工作流程：构词规则（正规式NFADFA）状态转换图程序 ；（算法的一部分） 构词规则状态转换图程序 。l 预处理：有哪些预处理工作要做。2. 总体设计：l 输入输出缓冲区，输出格式（等长二元式序列）；l 表格设计（设计几张表，每张表登记什么信息）： 关键字表 算符、分隔符表 变量表：简单变量、数组、过程与函数 错误信息表（扫描一遍源程序，登记错误信息，最后再输出到文件）l 出错处理：错误位置、错误消息格式、错误恢复等。3. 程序流程设计：明确程序所使用的主要算法，一般以伪代码或程序流程图表示。图1给出了一个程序流程图的例子，作为参考。4. 编码与测试：编写程序并调试通过，然后自己设计至少3个测试用例。测试用例包括两部分：输入（源程序代码）和预期结果（运行结果或错误信息）。5. 编写实验报告。图1 词法分析程序流程图 三、扩充有余力的同学，可适当扩大分析对象。譬如：1. 加入更多的基本类型，如：考虑引入布尔型变量和逻辑运算。2. 加入复杂的数据类型，如：类似java中的String类型。3. 加入二义性文法结构，如：单分支和双分支的选择语句。第三节 语法分析一、目的与要求1. 目的通过设计、编写、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法分析和检查，进一步掌握常用的语法分析方法的实现技术。2. 要求 调用词法分析器，分析源程序的语法结构（区分出各种语法结构），检查语法错误。 推荐使用算符优先分析算术表达式，用递归子程序法分析其他各种语法结构，如赋值语句、IF语句、WHILE语句等。也可以使用LR分析法完成这些工作，实现时可以借助YACC（如何使用请参考教材并上网搜索资料）。 输入文本文件形式的源程序；识别出程序中主要的语法结构，以注释的形式给出简单的说明信息，如“变量声明语句”、“IF语句”、“循环开始”、“循环结束”等。若有错误，则在相应位置给出错误提示(要求比这要高才行)。 本课题应在两周内完成。因时间紧张，建议采用增量开发模式：从简单到复杂、能力逐渐增强。 二、设计步骤1. 问题分析： 使用哪种语法分析方法？单独使用递归下降分析法可以完成任务吗？ 从文法中提炼出主要的语法结构，如：程序、变量声明、分程序声明、复合语句、IF语句、算术表达式等，认真分析他们的语法结构。 如何利用前面构造的词法分析器和相关表格？ 考虑错误处理的方法。2. 总体设计： 对文法进行必要的等价变换，使之符合所选语法分析方法的要求。 若有必要，对上次实验后得到的词法分析器及相关符号表进行调整。 针对产生算术表达式（关系表达式）的文法，构造算符优先关系表，在此基础上，编写一小段程序，分析这类语法结构。（算法示例见附录一） 针对各种语法结构，逐一产生其递归下降分析的状态转换图，再一一翻译为程序段。（算法示例见附录二） 设计输出的形式。 将前面的工作组合起来，形成一个完整的语法分析器。3. 程序流程设计。4. 编码和测试：编写代码，调试通过，并设计测试用例。5. 编写实验报告。 三、程序流程示例：题目：递归下降法分析表达式（此题目仅供参考，而且不完全准确）1. 分析对象的BNF定义如下：算术表达式项|算术表达式项|算术表达式项项因式|项因式|项因式因式变量（算术表达式）变量字母字母A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z 用递归下降法分析上述算术表达式的框图，如图2所示。(a) (b) (c)(d) (e) (f)图2 递归下降法分析表达式之框图(a) ZC 过程；(b) E 过程；(c) T 过程；(d) F 过程；(e) 函数过程 SYM ；(f) 过程 ADVANCE这里，ZC过程为总控程序，主要完成： 通知外界键入算术表达式； 控制过程分析算术表达式； 根据分析结果之正误，分别通知外界不同的信息。ZC过程被设计成可以分析无穷多个算术表达式。E、T和F三个过程分别对应算术表达式、项和因式三个产生式的处理。它们用到两个公共过程。一个是函数过程SYM，它负责从输入字符串ST中取出下一个字符，并存入SYM中等待分析。另一个过程ADVANCE负责剔除ST中的首字符。四、扩充有余力的同学，可适当扩大分析对象。譬如：1. 加入 for 循环语句： for i:=1 to 5 do begin dosomething() end ;2. 引入二义性文法： stmt if cond then stmt else stmt | if cond then stmt 3. 加强语法检查，尽量 多 和 确切 地指出各种错误。第四节 语义分析和中间代码产生一、目的与要求1. 目的通过上机实习，加深对语法制导翻译和运行时存储空间分配的理解，掌握将语法分析所识别的语法范畴变换为某种中间代码的语义翻译方法。2. 要求l 采用语法制导翻译技术。l 可以考虑实现简单的静态语义检查。l 语义分析的对象重点考虑经过语法分析后已是正确的语法范畴，程序设计的重点是语义子程序的设计。l 中间代码选用四元式。l 以两周内完成为宜。3. 源语言的语法结构大致可分为以下六类：n 声明语句：简单类型、复杂类型及其数据空间特性（如全局数据、局部数据等），以及过程声明。重点是符号表的操作。n 顺序结构：典型代表是两类表达式（算术表达式、布尔表达式）及相应的赋值语句。重点是算术表达式的翻译方法（各种属性值的计算）。n 控制结构：if语句。重点是跳转的地址问题（拉链返填）。n 子程序结构：过程和函数的调用。重点是参数传递和返回地址（活动记录）。n 循环结构：while语句。重点是循环的优化（本实验暂不涉及）。n 格式语句：主要指输入输出语句的格式加工。在LittleP+中, read(a,b,c)表示从键盘读入三个无符号整数；write(x, Y+2)表示向屏幕打印两个表达式的值。二、设计步骤1. 问题分析： 如何把语法分析和语义分析结合起来（语义子程序的处理时机）； 如何设计语义子程序来产生四元式； 有哪些静态语义检查工作？（应着重考虑实现以下几点：）i. 标识符必须先说明，再使用；ii. 同一作用域内不得重复定义（在符号表中记录标识符的作用域）；iii. 操作数与操作符的类型匹配a) 定义在integer上的运算：+ - * div mod 和关系运算符；b) 定义在boolean上的运算：not or and ；c) 赋值运算符:=两端的类型应该相同。iv. 对于不满足上述规则的，应给出错误提示。2. 总体设计： 对文法进行必要的等价变换，并为每条产生式添加语义子程序。 针对表达式的产生式，自下而上地计算其综合属性。 针对各种语句的产生式，自上而下地计算其继承属性。 将各种语法结构翻译为四元式序列（四元式的格式见本节第四部分）。 把四元式按顺序编号，输出到文件。3. 程序流程设计：核心是语法制导翻译的实现算法。4. 编码与测试。5. 编写实验报告。三、算法示例 题目：在对简化的算术表达式进行语法分析的同时生成四元式（仅作参考）。 四元式生成程序的核心部分（指表达式、项和因式的处理）的算法，可描述如下： PROCEDURE E; BEGIN E1PLACE:=T; WHILE SYM=+ OR - DO BEGIN ADVANCE; E2PLACE:=T; T1:=NEWTEMP; GEN(,E1PLACE,E2PLACE,T1); E1PLACE:=T1 END; RETURN(E1PLACE) END; PROCEDURE T; BEGIN T1PLACE:=F; WHILE SYM=* OR / DO BEGIN ADVANCE: T2PLACE:=F; T1:=NEWTEMP; GEN(*/,T1PLACE,T2PLACE, T1); T1PLACE:=T1 END; RETURN(T1PLACE) END; PROCEDURE F: BEGIN IF SYM= 标识符 THEN BEGIN ADVANCE; RETURN(ENTRY(i) END ELSE IF SYM=( THEN BEGIN ADVANCE; PLACE:=E; IF SYM=) THEN BEGIN ADVANCE; RETURN(PLACE) END ELSE ERROR END ELSE ERROR END.这里：E表达式；T项；F因子；ADVANCE将输入串指针调整至指向下一个输入字符；NEWTEMP分配一个新的工作单元；GEN将一个四元式填入四元式表；ENTRY查找变量名表，并获得名字所在位置值。四、建议生成的四元式统一采用如下的形式： 形如 x := y op z 的赋值语句，其中op是二元运算符；或者形如 x := op z 的赋值语句，其中op是not。 形如 x:=y 的复制语句，将y的值复制给x。 无条件跳转 goto L , L是接下来要执行的四元式的编号或地址。 条件跳转 jump x L ，若x为真，则跳转至L所指的四元式；否则顺序执行。 过程调用系列：n 传参数 param x ，有n个参数就生成n条传参数四元式； n 过程调用call p, n ，其中：p是过程或函数名，n 表示参数的个数；n 返回值 return y 。 形如 x := yi 和 xi := y 的变址赋值语句。 读写语句：n 传参数 param x ，有n个参数就生成n条传参数四元式； n 过程调用call read/write, n ，其中n 表示参数的个数。 附录一 算符优先分析算法示例Tree term2Rest( Tree t , int minprec) / minprec is the lowest precedence of all binary operators. Tree odStack = newOdStack(); /stack of operands; int opStack = newOpStack(); /stack of top = 0; /top pointer of stack.odStack0 = t ; int startPos = S.pos ; / S is a scanner. It returns a token and its position everytime ./topOp is always the top element of opStack. Its initial value is topOp = ERROR; while ( prec( S.token) = minprec) /移进opStacktop = topOp; top+;topOp = S.token;int pos = S.pos ;S.nextToken(); odStacktop = term(); / term() 分析表达式中的“项”/规约while ( top0 & prec(topOp) = prec( S.token ) ) / You can do something here, such as creating a syntax tree or calculating the value. odStacktop-1 = makeop( pos, topOp, odStacktop-1, odStacktop ) ; top- ; topOp = opStacktop;. .#附录二 递归下降分析算法示例SyntaxTree* Parser:Statement() SyntaxTree *tree = NULL; switch(currentToken.type) . case ID: this-nextTo