编译实验指导书201410.doc

编 译 原 理 B 实验指导书太原理工大学计算机科学与技术学院2014 年 10 月编译原理实验适用专业：计算机 实验类别：专业实验实验时数：8学时一、 实验课程的性质、目的和任务1 培养学生初步掌握编译原理实验的技能。2 验证所学理论、巩固所学知识并加深理解。3 对学生进行实验研究的基本训练。二、 实验课程的内容、要求及学时分配实验一、 无符号数的词法分析程序（4学时）内容：掌握词法分析的基本思想，并用高级语言编写无符号数的词法分析程序。要求：从键盘上输入一串字符（包括字母、数字等），最后以“；”结束，编写程序识别出其中的无符号数。无符号数文法规则可定义如下： .EE +- 0 1 2 3. 9 读无符号数的程序流程图见下图实验二、 逆波兰式生成程序 内容：掌握语法分析的基本思想，并用高级语言编写逆波兰式生成程序（4学时） 要求：利用逆波兰式生成算法编写程序，将从键盘上输入的算术表达式（中缀表达式）转化成逆波兰式。 逆波兰表达式的生成过程涉及到运算符的优先级，下表中列出几个常用运算符的优先关系。右关系左+-*/（）+-*/（） 常用运算符优先关系矩阵如上表所示的优先关系矩阵表示了+，-，*，/，（，）等七种运算符之间的相互优先关系。“、”三种符号分别代表“大于”、“小于”、“相等”三种优先关系。左边的“”与右边的“（”之间没有优先关系存在，所以表中为空白。逆波兰表达式生成算法的关键在于比较当前运算符与栈顶运算符的优先关系，若当前运算符的优先级高于栈顶运算符，则当前运算符入栈，若当前运算符的优先级低于栈顶运算符，则栈顶运算符退栈。下面给出了逆波兰表达式生成算法的流程图。（为了便于比较相邻运算符的优先级，需要设立一个工作栈，用来存放暂时不能处理的运算符，所以又称运算符栈）。 实验三、 语法分析程序的设计 语法分析阶段根据程序语言的语法规则，对词法分析产生的单词 序列进行语法检查。凡不合语法者，尽可能多和确切地指出错误（包括出错位置、原因和性质），否则，变换成各类语法范畴。（1） 内容：通过设计、编制、调试一个典型的语法分析程序，实现对词 法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌 握常用的语法分析方法。（4学时）（2） 要求：选择具有代表性的语法分析方法，如：LL(K)分析法、递归子程序法、运算符优先数法、LR(K)分析法等方法之一进行设计；选择对各种常见程序语言都通用的语法结构，如赋值语句（尤指表达式）作为分析对象，并与所选语法分析方法要比较贴切；先写出BNF定义，如：赋值语句:=变量=表达式 表达式:=项表达式+项表达式-项 项:=因子项*因子项/因子 因子:= 初等量因子初等量 初等量:= （表达式）i 然后编写语法分析程序；调试：调试例子应包括符合语法规则的算术表达式，以及分析程序能够判别的若干错例。 LL(1)语法分析方法 LL(1)分析器的逻辑结构 构造LL(1)分析表的算法如下:1)对于A:=D(DVN)且select(A:=D)=b1,b2bn 则MA,bi=RE(D)/R 表示:用D的逆替换A,重读当前字符.2)对于A:=a(aVT) 则MA,a= RE()/C 表示:用的逆替换A,继续读入下一字符.3)对于A:=且select(A:=)=b1,b2bn 则MA,bi=RE()/R=/R4)对所有没出现在规则右部的首部的终结符a, 令Ma,a=RE()/C=/C5)对于#,令M#,#=succ,表示分析成功,结束.6)其他情况属于出错，在分析表中用空白表示. 递归下降语法分析法 是一种确定的自顶向下分析法。又称递归子程序分析法。 思想： 对文法中每个非终结符（代表语法成分）编写一个子程序（或递归过程），用来识别它所表示的语法范畴。 例：赋值语句SV:=E变量 Vi | i(E)表达式 EE+T | E-T | T项 TT*F | T/F | F因子 FFP | P初等量 P(E) | i 消除左递归： SV:=E Vi | i (E) ET ( + | - ) T TF ( * | / ) F FP P P(E) | i赋值语句处理流程图: 变量处理流程图表达式处理流程图 项处理流程图因子处理流程图 初等量处理流程图 运算符优先数法 表达式文法GE的优先关系矩阵 + * ( ) i # + * ( = i # = SLR(1)语法分析方法 图11 LR(K)分析器的逻辑结构 表达式文法的SLR(1)分析表状态 ACTION GOTO i + * ( )# E T F S0 S5 S4 1 23 S1 S6acc S2 r2 S7 r2r2 S3 r4r4r4r4 S4 S5 S4 8 2 3 S5 r6 r6r6r6 S6 S5S4 9 3 S7 S5S4 10 S8 S6S11 S9 r1S7r1r1S10 r3r3r3r3S11 r5r5r5r5三、 基本要求： 学生可以从以上三个实验中选做两个。学生应在实验课前仔细阅读实验相关内容，明确实验的目的和要求，然后了解词法分析和语法分析的基本方法，利用一种高级语言（如C语言