1. 写一文法，使其语言是偶正整数的集合。要求：
1）允许0打头；
2）不允许0打头。
【解】：1) 允许0打头且含0的偶正整数集合的文法为：
n—>(0|d|e)n|(e|0)
d—>1|3|5|7|9
e—>2|4|6|8
2) 不允许0打头的偶正整数集合的文法为：
r—>(d|e)n|e
n—>(0|d|e)n|(e|0)
d—>1|3|5|7|9
e—>2|4|6|8
3) 允许0打头的偶正整数集合的文法为：
s—>0s|r
r—>(d|e)n|e
n—>(0|d|e)n|(e|0)
d—>1|3|5|7|9
e—>2|4|6|8
2.一个上下文无关文法生成句子abbaa的推导树如下：sabs
a s b b a a
b b a1）给出该句子的相应的最左推导，最右推导。
2）该文法的产生式集合p可能有哪些元素？
3）找出该句子的所有短语，简单短语，句柄。
解】：1）最左推导：
s=>abs=>abs=>asbbs=>abbs=>abbs=>abbs=>abbaa=>abbaa
最右推导：s=>abs=>abaa=>abaa=>asbbaa=>asbbaa=>asbbaa=>abbaa=>abbaa
2) 产生式集合p：
s—>abs | aa|
a—>a
b—>sbb | b
3) 短语：a , b , bb , aa , abbaa
直接短语：a , b
句柄：a3、给出生成下述语言的上下文无关文法：
解】：1）s—>aa
a—>aab |
2）s—>1s0 | a
a—>0a1 |
第4章课后作业。
1. 构造一个状态数最小的dfa，它接受∑=上所有倒数第二个字符为1的字符串。（编辑：张超）
解： 构造正规式：（0│1）* 1（0│1）
由正规式构造nfa：
nfa转化为dfa ：
t0=ε－closure（）=
用子集构造法求dfa状态，t0为初态，t2，t3为终态。
用0,1,2,3代表t0，t1，t2，t3，得到如下dfa ：
最小化dfa ：
p0=（，p1=（，
无等价状态。
没有找到多余状态，∴ 无多余状态。
上图为最小化的dfa。
2、将下图的nfa确定化为dfa，并最小化。（编辑：张超）
解：用子集构造法求dfa状态，t0为初态，t3为终态。
用0,1,2,3代表t0，t1，t2，t3，得到如下dfa ：最小化：
0和1是等价的，∴ 得到最小化的dfa 如下 ：
第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) 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)文法。
7. 给出下面赋值语句的逆波兰式： x :=a*(b+c)-d/e
解】 x a b c + d e /
8. 把下列语句翻译成四元式(四元式的编号从100开始）。
while a∨b∧～c∨d do
if a > b then x :=m - k
else y :=m + k;
解】 对应的四元式序列为：
100（jnz， a， ，108 ）
101（j ， 102 ）
北语18秋《编译原理》作业1234满分答案
18秋 编译原理 作业1 词法分析器用于识别 a.字符串。b.语句。c.单词。d.标识符。正确答案 c 一个句型中的最左 称为该句型的句柄。a.短语。b.简单短语。c.素短语。d.终结符号。正确答案 b 如果文法g是无二义的，则它的任何句子 a.最左推导和最右推导对应的语法树必定相同。b.最左推导和...
编译原理作业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组成的...
编译原理作业7答案
软件学院 2012秋季学期。编译原理 第七次作业参 一 证明下列文法。s aa bac dc bdaa d是lalr 1 文法但不是slr 1 文法。构造lr 1 自动机 没有需要合并的状态 没有状态存在冲突，因而是lalr 1 文法。构造lr 0 自动机 在状态i6，由于 a follow a 因...