北京交通大学。
2011 ―2012 学年第二学期期末考试试题(a)
课程名称： 编译原理出题教师： 徐金安于双元丁丁_
专业班级姓名学号。
注意：请将所有题答案写在答题纸上，标明题号。
一、 选择题（每空2分，共20分）
1．编译程序的各个阶段都涉及 b 。
a．词法分析b．**管理和错误处理。
c．语法分析d．语义分析。
2．设有文法 g[s]=(p,s)，其中p为：
s→wz w→x|y x→x|xx y→y|yy z→z|zz
则该文法所描述的语言的正则式是 b 。
a． xx*│yy*│zzb．(xx*│yy*)zz*
c．xx* (yy*zzd．(xx│yy) *zz*
e．xx*yy*zz*
3．已知文法g[s]: s→atb|,
t→r r→r/s|s
则句型 ar/asb/atb/,b的最左素短语是 b 。
a．atb b．asb c．s d．re. ,4．下述正则表达式中 d 与(0*|1)*(等价。
a. 0*(+1(+|
b. 0*(+1(+|
c. 0*(+1*(+
d. (0|1)*+0|1)*-
5．下列文法 g[s]: s→aa a→aa|a 不是ll(1)文法的理由是 c 。
a．first(s)∩first(a)≠φ
b．first(s)∩follow(a)≠φ
c．first(aa)∩first(a)≠φ
d．都不是。
6．给定文法g(e):
e→e+t∣tt→t*f∣ff→i∣(e)
则l(g)中的一个句子i+i+(i*i)*i的逆波兰表示（后缀式）为 c 。
a．iiii*ib．ii+iii**+
c．ii+ii*id．都不是。
7．设有文法g[s]: s→et∣rt
t→dr∣ε
r→dr∣ε
d →a∣bd
则first（s）是 bfollow（r）是 c
a． b．8．有一语法制导翻译如下所示：
t→ada
d→（aprint “2”}
d→dprint “3”}
a→ddprint “4”}
若输入字符序列为a（（（dd）d）d）a，且采用自上而下的分析方法，则输出序列为 c 。
a．32224441b．34242421
c．12424243d．14442223
9. 下列文法中，属于slr(1)文法的是c 。
g1：p→pap∣b
g2：p→bpb∣cpc ∣b∣c
g3：p→bpb∣bpc ∣d
可选项：a. 仅g1 b.仅g2 c. 仅g3 d. g2和g3
二、 (2小题，共8分)
1．证明下列文法是二义性文法。(4分)
s→s*s∣s+s∣(s) ∣a
参***： 一个句子有两颗不同的语法树（或一个句子有不同的推导）
2．已知文法g[s]
s daba aa | a
b bb |ε
写出该文法产生的语言。(4分)
参***：l（g[s]）=
三、 (2小题，共18分)
1．设字母表σ=,给出σ上正则式r=（a|ba）*
（1）构造nfa m′，使l(m′)=l(r)（4分）
（2）将nfa m确定化，最小化，得到dfa m使l(m)=l(m′)；4分）
（3）求右线性文法g，使l(g)=l(m) （4分）参***：
2） 将nfa确定化为dfa的转换矩阵。
对应的dfa如图：
将所求dfa最小化：状态集合。
最小化后的dfa：
3） 等价的右线性文法：
s as| ba |ε
a as四、 设有文法 g[a1小题，共12分)
a→a∨b|b
b→b∧c|c
c→﹁d|d
d→(a)|i
1）消除下列文法的左递归（6分）
2) 构造该文法的ll(1)分析表（6分）
参***：1） 改写后的文法：
a→ba′a′→∨ba′|ε
b→cb′b′→∧cb′|ε
c→﹁d|d
d→(a)|i
2） first (ba′)
first (cb′)
first (d) =
follow(a′) follow(a)∪ follow(a′)=
follow(b′) follow(b)∪ follow(b′)
(first(a′)-follow(a) ∪follow(a′)
ll(1)分析表：(每空1’)
五、 设文法g[s]：
1） 构造各非终结符的firstvt和lastvt集合；(6分)
2） 构造优先关系表(不含#号)； 6分)
参***：1）(6分，每个1’)
firstvt(ei }
firstvt(t)=
firstvt(f)=
lastvt(ei }
lastvt(t)=
lastvt(f)=
1. 相等关系：（=
2. 求小于关系：
t + firstvt (t)
f * firstvt (f)
e ( firstvt (e)
3. 求大于关系。
e+ lastvt(e) >
t* lastvt(t) >
e) lastvt(e) >
优先关系表： (6分)
六、构造文法g[s]:
s→asb |asc |ab
的lr(0)项目族，判断该文法是lr(0)还是slr(1)文法，说明原因并构造相应的分析表。（12分）
参***：解：拓广文法加入非终结符s'，文法的拓广为（1’）：
s'->s s→asb |asc |ab
下面构造它的lr(0)项目集规范族为：(5’，每个0.5’)
1. s'→·s
2. s'→s·
3. s→·asb
4. s→a·sb
5. s→as·b
6. s→asb·
7. s→·asc
8. s→a·sc
9. s→as·c
10. s→asc·
11. s→·ab
12. s→a·b
13. s→ab·
其中： 接受项目 2
归约项目移进项目
待约项目dfa如下：
从上表可看出，不存在移进-归约冲突以及归约归约冲突，该文法是lr(0)文法。（1’）
从而有下面的lr(0)分析表：(5’，每个0.5’)
七、 写出表达式：
while a< c and bif a = 1 then c:=c+1
else if a 的四元式中间**，并注明拉链回填的过程。（12分）
参***：1) (j<， a，c，3)
2) (j， -15)
3) (j<， b，d，5)
4) (j， -15)
5) (j=， a，1，7)
6) (j， -10)
7) (c，1，t1)
8) (t1，-，c)
9) (j， -1)
10) (j<， a，d，12)
11) (j， -1)
12) (a， 2，t2)
13) (t2，-，a)
14) (j， -1)
每条四元式1’
六、 现有如下基本块的四元式序列。
1)（+a, b, t1）
编译原理试题
语法分析 自顶向下的分析。重点与难点。重点 自顶向下分析的基本思想，分析器总体结构，分析表的构造，递归下降分析法基本思想，简单算术表达式的递归下降分析器。难点 first和follow集的求法，对它们的理解以及在构造ll 1 分析表时的使用。递归子程序法中如何体现分析的结果。基本要求。掌握语法分析 ...
编译原理试题
编译原理模拟试题。班级姓名学号。1 20分 写出字母表 上语言l 的正规式，并画出接受该语言的最简dfa。2.10分 计算文法g m 的每个非终结符的first和follow集合，并判断该文法是否是ll 1 的，请说明理由。g mm tb t ba b db et d d 3.10分 写一个文法使其...
编译原理试题
东南大学。一 文法g1 e et t t tf f f fp p p e i1 试证明符号串tet i 是g1的一个句型 要求画出语法树 2 写出该句型的所有短语，简单短句和句柄。三 1 试写出一个上下文无关文法g3，它能产生配对的圆括号串 例如等，甚至包含0对括号 2 使用文法g3给出输入串 的自...