《编译原理》
实验指导书
太原理工大学计算机软件学院
《编译原理》实验
适用专业：计算机实验类别：专业实验
实验时数：8学时
一、实验课程的性质、目的和任务
1．培养学生初步掌握编译原理实验的技能。
2．验证所学理论、巩固所学知识并加深理解。
3．对学生进行实验研究的基本训练。
二、实验课程的内容、要求及学时分配
实验一、无符号数的词法分析程序（4学时）
内容：掌握词法分析的基本思想，并用高级语言编写无符号数的词法分析程序。
要求：从键盘上输入一串字符（包括字母、数字等），最后以“；”结束，编写程序识别出其中的无符号数。
无符号数文法规则可定义如下：
<无符号数>→<无符号实数>│<无符号整数>
<无符号实数>→<无符号整数>.<数字串>[E<比例因子>]│
<无符号整数>E<比例因子>
<比例因子>→<有符号整数>
<有符号整数>→[+│-]<无符号整数>
<无符号整数>→<数字串>
<数字串>→<数字>{<数字>}
<数字>→0 1 2 3 (9)
读无符号数的程序流程图见下图
实验二、逆波兰式生成程序（4学时）
内容：掌握语法分析的基本思想，并用高级语言编写逆波兰式生成程序；
要求：利用逆波兰式生成算法编写程序，将从键盘上输入的算术表达式（中缀表达式）转化成逆波兰式。
逆波兰表达式的生成过程涉及到运算符的优先级，下表中列出几个常用运算
符的优先关系。
常用运算符优先关系矩阵
如上表所示的优先关系矩阵表示了+，-，*，/，↑，（，）等七种运算符之间的相互优先关系。“＞、＜、＝”三种符号分别代表“大于”、“小于”、“相等”三种优先关系。左边的“＝”与右边的“（”之间没有优先关系存在，所以表中为空白。
逆波兰表达式生成算法的关键在于比较当前运算符与栈顶运算符的优先关系，若当前运算符的优先级高于栈顶运算符，则当前运算符入栈，若当前运算符的优先级低于栈顶运算符，则栈顶运算符退栈。
下面给出了逆波兰表达式生成算法的流程图。（为了便于比较相邻运算符的优先级，需要设立一个工作栈，用来存放暂时不能处理的运算符，所以又称运算符栈）。
实验三、语法分析程序的设计（4学时）
语法分析阶段根据程序语言的语法规则，对词法分析产生的单词序列进行语法检查。凡不合语法者，尽可能多和确切地指出错误（包括出错位置、原因和性质），否则，变换成各类语法范畴。
（1）内容：通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌
握常用的语法分析方法。（4学时）
（2）要求：选择具有代表性的语法分析方法，如：LL(K)分析法、递归子程序法、运算符优先数法、LR(K)分析法等方法之一进行设计；选择对各种常见程序语言都通用的语法结构，如赋值语句（尤指表达式）作为分析对象，并与所选语法分析方法要比较贴切；先写出BNF定义，如：〈赋值语句〉::=〈变量〉=〈表达式〉
〈表达式〉::=〈项〉│〈表达式〉+〈项〉│〈表达式〉-〈项〉
〈项〉::=〈因子〉│〈项〉*〈因子〉│〈项〉/〈因子〉
〈因子〉::= 〈初等量〉│〈因子〉↑〈初等量〉
〈初等量〉::= （〈表达式〉）│i
然后编写语法分析程序；调试：调试例子应包括符合语法规则的算术表达式，以及分析程序能够判别的若干错例。
①LL(1)语法分析方法
LL(1)分析器的逻辑结构
输入串
分析栈
构造LL(1)分析表的算法如下:
1)对于A::=Dβ(D∈VN)且select(A::=Dβ)={b1,b2…bn}
则M[A,bi]=RE(Dβ)/R
表示:用Dβ的逆替换A,重读当前字符.
2)对于A::=aβ(a∈VT)
则M[A,a]= RE(β)/C
表示:用β的逆替换A,继续读入下一字符.
3)对于A::=ε且select(A::=ε)={b1,b2…bn}
则M[A,bi]=RE(ε)/R=ε/R
4)对所有没出现在规则右部的首部的终结符a,
令M[a,a]=RE(ε)/C=ε/C
5)对于#,令M[#,#]=succ,表示分析成功,结束.
6)其他情况属于出错，在分析表中用空白表示.
②递归下降语法分析法
是一种确定的自顶向下分析法。又称递归子程序分析法。
思想：对文法中每个非终结符（代表语法成分）编写一个子程序（或递归过程），用来识别它所表示的语法范畴。
例：赋值语句S→V:=E
变量 V→i | i(E)
表达式 E→E+T | E-T | T
项 T→T*F | T/F | F
因子 F→F↑P | P
初等量 P→(E) | i
消除左递归：
S→V:=E
V→i | i (E)
E→T { ( + | - ) T }
T→F { ( * | / ) F }
F→P {↑P }
P→(E) | i
赋值语句处理流程图:
变量处理流程图
项处理流程图
初等量处理流程图：
③运算符优先数法
表达式文法G[E]的优先关系矩阵
④SLR(1)语法分析方法
下
推
分
析
栈
图11 LR(K)分析器的逻辑结构
表达式文法的SLR(1)分析表
三、基本要求：
学生可以从以上三个实验中选做两个。要求在实验课前仔细阅读实验相关内容，明确实验的目的和要求，然后了解词法分析和语法分析的基本方法，利用一种高级语言（如C语言、C++语言、PASCAL、JA V A语言等），编写无符号数的词法分析程序、逆波兰式生成程序、语法分析程序（选做一种语法分析方法）。调试程序后，打印程序代码及实验结果，写出实验报告。
四、考核以学生的实验报告、实验内容、实验结果和实验态度为考核依据。
