华东交通大学2024年统招硕士研究生业务课考试卷答案。
考试时间3小时，卷面150分)
考试科目** 820考试科目名称编译原理
一、（15分）名字解释。
短语：设g[s]是给定文法， w=xuy∈v+，为该文法的句型，如果满足下面两个条件：
1） s xuy；（2）u u；
则称句型xuy 中的子串u是句型xuy的短语。
简单短语：
设g[s]是给定文法， w=xuy∈v+，为该文法的句型，如果满足下面两个条件：
1）s xuy；（2） u u；
则称句型xuy 中的子串u是句型xuy的简单短语（或直接短语）。
最左素短语：
设有文法g[s],其句型的素短语是一个短语，它至少包含一个终结符，并除自身外不包含其它素短语，最左边的素短语称最左素短语。
句柄：一个句型中的最左简单短语称为该句型的句柄。
语法分析：
按文法的产生式识别输入的符号串是否为一个句子的分析过程。
二、（15分）已知文法g[e]为：
e→t|e+t|e-t
t→f|t*f|t/f
f→（e）|i
该文法的开始符号（识别符号）是什么？
请给出该文法的终结符号集合vt和非终结符号集合vn。
找出句型t+t*f+i的所有短语、简单短语和句柄。
解： 该文法的开始符号（识别符号）是e。
该文法的终结符号集合vti}。
非终结符号集合vn=。
句型t+t*f+i的短语为i、t*f、第一个t、t+t*f+i;；
简单短语为i、t*f、第一个t；
句柄为第一个t。
三、（10分）消除下列文法g[e]的左递归。
e→e-t∣t
t→t/f∣f
f→( e )∣i
解：消除文法g[e]的左递归后得到：
e→te’e’→ te’∣ε
t→ft’t’→/ft’∣ε
f→( e )∣i
四、（10分）试给出非确定自动机的定义。
解：一个非确定的有穷自动机（nfa）m是一个五元组：m=（k，σ，f，s ，z）。
其中：1. k是一个有穷集，它的每个元素称为一个状态；
2. σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称σ为输入符号表；
3. f是状态转换函数，是在k×σ→k的子集的映射，即，f: k×σ→2k ；表明在某状态下对于某输入符号可能有多个后继状态；
4. s﹙k是一个非空初态集；
5. z﹙k是一个终态集（可空）。
五、（20分）给定下列自动机，将其转换为确定的自动机。
解：(1)消除ε边，得到nfa：
2)确定化，得到dfa：
六、（20分）给定文法g[z]：
构造此文法的lr(0)项目集规范族，并给出识别活前缀的dfa。
构造其slr（1）分析表。
解：1.首先拓广文法：在g中加入产生式0．z′→z，然后得到新的文法g′，再求g′的识别全部活前缀的dfa：
follow(c)＝
follow(s)＝
follow(e)＝
follow(athen }
则可构造slr（1）分析表为：
七、（10分）给定文法及相应的翻译方案：
对于句型t+(t*(f+t)*i)，处理完该句型后输出是什么？
解：给出句型t+(t*(f+t)*i)的语法树如下图7所示。
图7则对于句型t+(t*(f+t)*i),处理完该句型后输出是：
八、（20分）给定下列中缀式，分别写出等价的后缀式和四元式(运算符优先级按常规理解)。
(a＋b*c)/(a＋b)－d
解： 后缀式：abc*+ab+/d-
四元式：①（b, c, t1）
a, t1, t2)
a, b, t3
(/t2,t3, t4)
t4,d, t5)
x+y≤z∨a>0
解： 后缀式：xy+z≤a0>∨
四元式：①（x, y, t1）
t1,z, t2), a, 0, t3
(∨t2,t3, t4)
x＋y≤0∨ (x―y)>2
解： 后缀式：xy+0≤xy-2>∨
四元式：①（x, y, t1）
t1,0, t2)
x, y, t3
(>t3,2, t4)
(∨t2,t4,t5)
a:= b*c―a) *a
解： 后缀式：abc*a-a*:=
四元式：①（b, c, t1）
t1,a, t2)
t2, a, t3
(:t3, ,a)
九、（15分）给定下列自动机：
把此自动机转换为确定自动机dfa。
给出此dfa的正则表达式。
解：（1）： 有状态矩阵如图：
从而可得dfa如图9-1：
图9-1图9-2
2）此dfa的正则表达式为： (aa*bb)(bab)* 或 a*b（bab）*。
十、（15分）假设基本块中中间**序列已表示成dag，试给出应用dag计算各中间**待用信息的算法。
解：设dag有n个内部结点i是一个线性表，它共有n个登记项，算法的步骤如下。
1） 置初值。
for k；=1 to n do t[k]:=null;
i:=n;2) while 存在未列入t的内部结点 do
begin3) 选取一个未列入t但其全部父结点（即前驱）均已列入t或者没有父结点的内部结点n；
4) t[i]：＝n；i：＝i－1； /把n列入t中 *
5) while n的最左子结m不为叶结且其全部父结均已列入t中 do
begin6t[i]：＝m；i：＝i－1；
7n：＝m；
endend;
8) 最后t[1]，t[2]，…t[n]即为所求的结点顺序。
编译试卷与答案 B
编译原理模拟试卷及答案 二 学生姓名学号。学生系别专业年级班级。课程名称 编译原理课程性质 专业必修。一 文法g的产生式为12 i a 给出 i i i的最左推导 最右推导及相应的推导树 b 列出句型 的所有短语 简单短语和句柄。答 a 最左推导 i i i i i i i i i i i 最右推导...
编译试卷b试卷
哈尔滨学院2010年春季学期期末试卷b 课程名称 编译原理 考试时间 120 分钟考试方式 闭卷。卷面总分100分，占总成绩 60 一 单项选择题 每题1分，共10分 1 若某翻译程序所处理的源程序是高级语言编写的程序，目标程序是汇编语言程序或机器语言程序，则称它为 1 a 汇编语言程序。b 高级语...
试卷B答案
建筑工程施工项目管理 试卷b参 一 填空题 30分 1.明确的目标特定的生命周期 2.组织协调目标控制。3.动态管理节点考核 4.合同措施经济措施。5.企业管理层项目经理 6.施工调查现场准备。7.无节奏流水施工异节奏流水施工 8.编制资源计划进行资源使用效果的分析。9.资金收支对比资金筹措 10....