2.1 设字母表a=，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及a+.
x0=(aaa)0=ε x0|=0
xx=aaaaaa |xx|=6
x5=aaaaaaaaaaaaaaa | x5|=15
a+ =a1 ∪ a2 ∪ a n ∪…
a* =a0 ∪a1 ∪ a2 ∪ a n ∪…
2.2 令∑=，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3
xy=abcb |xy|=4
xyz=abcbaab |xyz|=7
xy)3=(abcb)3 =abcbabcbabcb | xy)3 |=12
2.3 设有文法g[s]：s∷=ss*|ss+|a，写出符号串aa+a*规范推导，并构造语法树。
s=>ss*=>sa*=>ss+a*=>sa+a*=>aa+a*
2.4 已知文法g[z]：z∷=u0∣v1 、 u∷=z1∣1 、 v∷=z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。
z=>u0=>z10=>u010=>1010
z=>u0=>z10=>v110=>0110
z=>v1=>z00=>u000=>1000
z=>v1=>z00=>v100=>0100
2.5 已知文法g[s]： s∷=ab a∷=aa︱ε b∷=bbc︱bc , 写出该文法描述的语言。
a∷=aa︱ε描述的语言：
b∷=bbc︱bc描述的语言：
l(g[s])=
2.6 已知文法e∷=t∣e+t∣e-t 、 t∷=f∣t*f∣t/f 、 f∷=(e)∣i，写出该文法的开始符号、终结符号集合vt、非终结符号集合vn、
开始符号：e
vti}vn=
2.7 对2.6题的文法，写出句型t+t*f+i的短语、简单短语以及句柄。
短语：t+t*f+i,t+t*f
i (简单短语)
t (简单短语、句柄)
t*f2.8 设有文法g[s]：s∷=s*s|s+s|(s)|a，该文法是二义性文法吗？
根据所给文法推导出句子a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。
2.9 写一文法，使其语言是奇正整数集合。
a::=1|3|5|7|9|na
n::=n0|n1|n2|n3|n4|n5|n6|n7|n8|n9|
n::=0|1|2|3|4|5|6|7|8|9
2.10给出语言的文法。
g[s]: s::=ab
a::=aa|a
b::=bb|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 因...
编译原理作业20150515 答案
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 ...