发布时间 : 星期三 文章编译原理复习题-给学生(2014)更新完毕开始阅读
《编译原理》复习题
构造SLR(1)分析表如下：
状态 0 1 2 3 4 5
20．构造文法S→AaAb|BbBa A→ε B→ε，的预测分析表。
答：first（S）={a，b},First（AaAb）={a}，First（BbBa ）={b} Follow（A）={a，b} Follow（B）={a，b}
S A B a S→AaAb A→ε b S→BbBa A→ε $ ACTION a s2 s2 s2 b s3 s3 s3 # acc r3 r1 r2 GOTO S 1 4 5 B→ε B→ε
21．设有如下文法： G[E]：E→EWT|T T→T/F|F
F→（E）|a|b|c W→+|-
证明符号串a/(b-c)是句子。
解答：有推导E?T?T/F?F/F?a/F?a/(E)?a/(EWT)? a/(TWT)? a/(FWT)? a/(bWT)? a/(b-T)? a/(b-c)，即从文法开始符号E能够推导出a/(b-c)，所以a/(b-c)是文法G[E]的句子。 55．对于下列文法 G[S]： S→Sb|bA A→aA|a
（1）构造一个与G等价的LL（1）文法G′。 （2）对于文法G′,构造相应的LL（1）分析表。 解：
（1） G′：S→bAS′ S′→b S′|ε
A→aA′
A′→A|ε
（2）FIRST（S）={ b }
FIRST（S′）={ b，ε} FIRST（A）={a}
FIRST（A′）={a，ε} FOLLOW（S）={#}
21
《编译原理》复习题
FOLLOW（S′）={#} FOLLOW（A）={b，#}
FOLLOW（A′）=（b，#）
LL（1）分析表：
a b # S S→bAS′ S′ S′→b S′ S′→ε A A→aA′ A′ A′→A A′→ε A′→ε 22．已知文法G[S]如下：构造该文法的LR（0）分析表。
G[S]：S→BB B→aB|b 解：拓广文法： （0）S?→S （1）S→BB （2）B→aB （3）B→b
识别活前缀的DFA 如下：
I0： S I1： S??.S S??S. S?.BB B?.ab B I2： B I5： B?.b b S?B.B S?BB. b B?.ab a a B?.b b I3： b I4： a B?a.B B?b. B?.ab B?.b B I6： B?aB. LR(0)分析表如下：
状态 Action Goto a b # S B 0 S3 S4 1 2 1 acc 2 S3 S4 5 3 S3 S4 6 4 R3 R3 R3 5 R1 R1 R1
22
《编译原理》复习题
6 R2 R2 R2
语义分析与中间代码生成： 23．给定文法：S→(L) | a L→L,S | S
请书写语义规则，求输出句子中每一个a的括号嵌套深度。 解：
用继承属性depth表示嵌套深度，则 S’ → S S.depth = 0 S → (L) L.depth = S.depth + 1 S → a print(S.depth) L → L(1), S L(1).depth = L.depth; S.depth = L.depth L → S S.depth = L.depth
24. 表达式a*b-c-d$e$f-g-h*i中，运算符的优先级由高到低依次为-、*、$，且均为右结合，请写出相应的后缀式。
解： abcd- -*efgh- - i*$$
25．分别给出表达式 –(a*(b-c))+d 的逆波兰表示和四元式表示。 解：（1）逆波兰式： abc-*@d+ 其中使用@代表一目减运算 （2）四元式： ① (-, b, c, T1) ② (*, a, T1, T2) ③ (@, T2, _, T3) ④ (+, T3, d, T4)
26． 下面的文法产生0和1的串，即二进制的正整数，请给出决定每个二进制数的值（十进制形式）的语法制导定义。
【解】定义值属性为.val，翻译方案如下：
B ? B1 0 { B.val = B1.val ? 2 } B ? B1 1 { B.val = B1.val ? 2 + 1 } B ? 1 { B.val = 1 } B ? 0 { B.val = 0 }
27．把算术表达式?(a + b) ? (c + d) + (e+ f) 翻译成等价的四元式序列（序号从0开始）。 【解】
0（+，a, b ,T1）
1（uminus，T1，-，T2） 2（+，c, d , T3） 3（*，T2，T3，T4） 4（+，e，f，T5） 5（+，T4，T5，T6）
23
《编译原理》复习题
28．给出表达式-a*b+b*c+d/e的抽象语法树和三元式序列。
答：语法树 三元式
+ + / * ①（-，a，-） * ②（*，①，b） d e ③（*，b，c） - b b c ④（+，②，③） ⑤（/，d，e） ⑥（+，④，⑤） a
29．有一语法制导定义如下，其中+表示符号连接运算： S→B print B.vers B→a B.vers=a B→b B.vers=b
B→Ba B.vers=a+B.vers B→Bb B.vers=b+B.vers
若输入序列为abab，且采用自底向上的分析方法，则输出序列为（__________baba_________）。用分析树表示求解过程。
S Print baba B B.vers=baba B b B.vers=aba B a B.vers=ba B b B.vers=a a
30．程序的文法如下：
P → D
D → D;D | id : T | proc id; D; S
写一语法制导定义，打印该程序一共声明了多少个id 【解】 属性num表示id个数 P → D print(D.num) D → D(1)；D(2) D.num = D(1).num + D(2).num D → id : T D.num = 1 D → proc id; D(1); S D.num = D(1).num + 1 例：proc id; proc id; id : T; S; S（从语法树分析入手）
24