第5-7章课后作业（含答案）
1、将文法g[s] 改写为等价的g′[s]，使g′[s]不含左递归和左公共因子。g[s]： s→bsae|ba a→abd | dc | a
解】：g[s]：s→bs’ s’→sae|a
a→(dc|a)a’ a’ →bd a’ |
2、有文法g[s]：s→abf a→bbs|e b→dag|ε
证明文法g是ll(1)文法，并构造**分析表。
解】：计算first、follow、select集。
由上表可知：该文法中，所有相同左部不同右部的产生式select集两两相交均为空集，所以该文法为ll(1)文法。
构造**分析表。
3、已知文法g[s]：s→(a)│a│b a→acs│s 构造文法的算符优先矩阵，并判断该文法是否是算符优先文法。
解】：拓展该文法：s’→#s# s→(a)│a│b a→acs│s
计算firstvt与lastvt:
计算算符优先关系：
# < firstvt(s) (firstvt(a) c< firstvt(a)
lastvt(s) ># lastvt(a) >lastvt(a) >c
构造算符优先矩阵（注：按终结符出现顺序列表）:
因为该文法g为2型文法，且不含空产生式，没有形如 u…vw…的产生式，其中v,w∈vn，所以 g 为算符文法；又因为g 中任意两个终结符间至多有一种算符优先关系存在(算符优先矩阵无冲突，见上表)，所以g 为算符优先文法。
4、课后习题 p122：4(2)
已知文法：s→ s;g|g g→ g(t)|h h→ a|(s) t→ t+s|s
求句型a(t+s);h;(s) 的短语、直接短语、句柄、素短语与最左素短语。
解】：该句型的对应的语法树如下：
短语： a t+s h (s) a(t+s);h a(t+s);h;(s)
直接短语： a t+s h (s)
句柄： a素短语： a t+s (s)
最左素短语：a
5. 给定文法g[a]：a→(a)│a，构造出该文法的lr(1)分析表。
解】对该文法拓广，得其拓广文法g[s’]：
(0) s’→a
(1) a→(a)
(2) a→a
计算其lr(1)项目集规范族如下：
i0 = i1 = goto(i0，a) =
i2 = goto(i0，()
i3 = goto(i0，a) =
i4 = goto(i2，a) =
i5 = goto(i2，()
i6 = goto(i2，a) =
i7 = goto(i4，))
i8 = goto(i5，a) =
goto(i5，()i5 ; goto(i5，a) =i6
i9 = goto(i8，))
构造lr(1)分析表：
6、证明文法 s bb b b*a b a
不是lr(0)文法，而是 slr(1)文法。
解】对该文法拓广，得其拓广文法g[s’]：
(0) s’→s (1) s bb (2) b b*a (3) b a
计算其lr(0)项目集规范族如下：
i0 = closure =
i1 = goto(i0，s) =
i2 = goto(i0，b) =
i3 = goto(i2，b) =
i4 = goto(i2，a) =
i5 = goto(i3，*)
i6 = goto(i5，a) =
因为该文法的lr(0)项目集规范族中有一个项目集i3同时存在移进项目与归约项目，即“移进-归约”冲突，所以不是lr(0)文法。
i3 = 而，follow（s
follow(s
即可采用follow集能解决其冲突，所以该文法是slr(1)文法。
编译原理平时作业 含答案
1 对于下列语言分别写出它们的正规表达式。1 英文字母组成的所有符号串，要求符号串中顺序包含五个元音。答 令letter表示除这五个元音外的其它字母。letter a letter e letter i letter o letter u letter 2 英文字母组成的所有符号串，要求符号串中的字...
编译原理6章作业答案
第五章。练习5.1.1 对于图5 1中的sdd，给出下列表达式对应的注释语法分析树 1 3 4 5 6 n 练习5.2.4 这个文法生成了含 小数点 的二进制数 s l lb b b 0 1 设计一个l属性的sdd来计算即输入串的十进制数值。比如，串101.101应该被翻译为十进制的5.625。提示...
编译原理作业1答案
计算机科学系 2012春季学期。编译原理 第一次作业参 一 下列正则表达式定义了什么语言 用尽可能简短的自然语言描述 1.b ab ab 所有含有偶数个a的由a和b组成的字符串。2.c a a c b a b c c b b c a a b c 答案一 所有至少含有1个a和1个b的由a，b和c组成的...