编译原理 龙书答案

第四章部分习题解答

Aho：《编译原理技术与工具》书中习题 （Aho）4.1 考虑文法 S → ( L ) | a L → L, S | S

a) 列出终结符、非终结符和开始符号 解：

终结符：(、)、a、， 非终结符：S、L 开始符号：S

b) 给出下列句子的语法树

i) (a, a) ii) (a, (a, a)) iii)

(a, ((a, a), (a, a)))

c) 构造b)中句子的最左推导

i) ii) iii)

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

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

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

d) 构造b)中句子的最右推导