编译原理复习题及答案

（4） G[A]:A→aB|ε B→Ab|a ( ) （5） G[E]:E→E+E|E*E|(E)|i ( ) 答：

（1） L1={ a01bd | n>0，m >0} ( 2 型 ) （2） L2={ abcb | n≥0,m>0 } ( 1型 ) （3） L3={ abc| n≥0,m>0 } ( 3型 ) （4） G[A]:A→aB|ε B→Ab|a ( 2型 ) （5） G[E]:E→E+E|E*E|(E)|i ( 2型 ) 26． 按指定类型给出下列语言的文法。 (1) L1={ cadb| n≥0,m>0 } 用正规文法。

(2) L2={ 0a1bc| n>0，m ≥0} 用二型文法。 答：

（1）解：描述L1语言的正规文法如下： S→cA A→aA|B B→dD D→bD|ε

（2）解：描述L2语言的二型文法如下： S→AB A→0A1|0a1 B→bBc|ε

27． 写出表达式(a+b)/(a-b)-a(a+b*c)的三元式序列 答：

⑴.(+,a,b) ⑵.(-,a,b) ⑶.(/,⑴,⑵) ⑷.(*,b,c) ⑸.(+,a,⑷) ⑹.(-,⑶,⑸)

28． 写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。

n

nmmn

mnmnnnmnn

m

答：

逆波兰表示：

abc*＋ab＋/d－

三元式序列：

① (*，b，c) ② (＋，a，①) ③ (＋，a，b) ④ (/，②，③) ⑤ (－，④，d)

29． 将下面的条件语句表示成四元式序列：

if a>b then x:=a+b*c else x:=b-a; 答：

(1) ( j>, a, b, (3)) (2) ( j, , , (7) ) (3) ( *, b, c, T1) (4) ( +, a, T1, T2) (5) ( :=, T2, , x) (6) ( j, , , (9)) (7) ( -, b, a, T3) (8) ( :=, T3, , x) (9) ( … … ) 30． 翻译成四元式序列。

While a＞0 ∨b＜0 do Begin

X：＝X＋1；

if a＞0 then a：＝a－1 else b：＝b＋1 End； 答：

(1) (j＞，a，0，5) (2) (j，－，－，3) (5) (＋，×，1，T1) (6) (：＝，T1，－，×)

(7) (j≥，a，0，9) (8) (j，－，－，12) (9) (－，a，1，T2) (10) (：＝，T2，－，a) (11) (j，－，－，1) (12) (＋，b，1， T3) (13) (：＝，T3，－，b) (14) (j，－，－，1) (15)

31． 已知文法G(S) ： S→a|∧|(T) T→T，S|S

写出句子((a，a)，a)的规范归约过程及每一步的句柄。 答：

句型 归约规则 句柄

((a，a)，a) S→a a ((S，a)，a) T→S S ((T，a)，a) S→a a ((T，S)，a) T→T，S T，S ((S)，a) T→S S ((T)，a) S→S(T) (T) (S，a) T→S S (T，a) S→a a (T，S) T→T，S T，S (T) S→(T) (T) S