编译原理复习题_给学生(2014)

.. .. ..

FOLLOW（S′）={#} FOLLOW（A）={b，#} FOLLOW（A′）=（b，#）

LL（1）分析表：

S S′ A A′ a A→aA′ A′→A b S→bAS′ S′→b S′ A′→ε # S′→ε 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??.S S?.BB B?.ab B?.b b a I3： a B?a.B B?.ab B?.b B I6： B?aB. S I1： S??S. B b I2： S?B.B B?.ab B?.b b B I5： S?BB. a b I4： B?b. LR(0)分析表如下：

状态 a 0 1 2 3 4 5 6

语义分析与中间代码生成： 23．给定文法：S→(L) | a

参考材料

Action b S4 S4 S4 R3 R1 R2 # acc R3 R1 R2 S 1 Goto B 2 5 6 S3 S3 S3 R3 R1 R2 .. .. ..

L→L,S | S

请书写语义规则，求输出句子中每一个a的括号嵌套深度。 解：

用继承属性depth表示嵌套深度，则

S’ → S S → (L) S → a

S.depth = 0

L.depth = S.depth + 1 print(S.depth)

L(1).depth = L.depth; S.depth = L.depth S.depth = L.depth

L → L(1), S L → S

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）

28．给出表达式-a*b+b*c+d/e的抽象语法树和三元式序列。

答：语法树 三元式

参考材料