编译原理 龙书答案

i) ii) iii)

S (L) (L, S) (L, a) (S, a) (a, a)

S (L) (L, S) (L, (L)) (L, (L, S)) (L, (L, a)) (L, (S, a)) (L, (a, a)) (S, (a, a)) (a, (a, a))

S (L) (L, S) (L, (L)) (L, (L, S)) (L, (L, (L))) (L, (L, (L, S))) (L, (L, (L, a))) (L, (L, (S, a))) (L, (L, (a, a))) (L, (S, (a, a))) (L, ((L), (a, a))) (L, ((L, S), (a, a))) (L, ((L, a), (a, a))) (L, ((S, a), (a, a))) (L, ((a, a), (S, S))) (S, ((a, a), (a, a))) (a, ((a, a), (a, a)))

e) 该文法产生的语言是什么

解：设该文法产生语言（符号串集合）L，则

L = { (A1, A2, …, An) | n是任意正整数，Ai=a，或Ai∈L，i是1～n之间的整数}

（Aho）4.2考虑文法 S→aSbS | bSaS |

a) 为句子构造两个不同的最左推导，以证明它是二义性的 S aSbS abS abaSbS ababS abab

S aSbS abSaSbS abaSbS ababS abab

b) 构造abab对应的最右推导

S aSbS aSbaSbS aSbaSb aSbab abab S aSbS aSb abSaSb abSab abab

c) 构造abab对应语法树

d) 该文法产生什么样的语言？

解：生成的语言：a、b个数相等的a、b串的集合

（Aho）4.3 考虑文法

bexpr → bexpr or bterm | bterm bterm → bterm and bfactor | bfactor

bfactor → not bfactor | ( bexpr ) | true | false a) 试为句子not ( true or false) 构造分析树 解：