内容发布更新时间 : 2024/11/14 13:18:23星期一 下面是文章的全部内容请认真阅读。

语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。

语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。

第4 章 词法分析

第5 章 自顶向下语法分析方法

第1 题对文法G[S] S→a|∧|(T) T→T,S|S

(1) 给出(a,(a,a))和(((a,a),∧,(a)),a)的最左推导。

(2) 对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。 (3) 经改写后的文法是否是LL(1)的?给出它的预测分析表。

(4) 给出输入串(a,a)#的分析过程，并说明该串是否为G 的句子。 答案：(1) 对(a,(a,a)的最左推导为：

S=>（t） => (T,S) => (S,S) => (a,S) => (a,(T)) => (a,(T,S)) => (a,(S,S)) => (a,(a,S)) => (a,(a,a))

对(((a,a),∧,(a)),a) 的最左推导为：

S => (T) => (T,S) => (S,S) => ((T),S) => ((T,S),S) => ((T,S,S),S) => ((S,S,S),S) => (((T),S,S),S)

=> (((T,S),S,S),S) => (((S,S),S,S),S) => (((a,S),S,S),S) => (((a,a),S,S),S) => (((a,a),∧,S),S) => (((a,a),∧,(T)),S) => (((a,a),∧,(S)),S)

=> (((a,a),∧,(a)),S) => (((a,a),∧,(a)),a)

(2) 改写文法为： 0) S→a 1) S→∧ 2) S→( T ) 3) T→S N 4) N→, S N 5) N→ε

非终结符 FIRST 集 FOLLOW 集 S {a,∧,(} {#,,,)} T {a,∧,(} {)}.... N {,,ε} {)}....

对左部为N 的产生式可知： FIRST （→, S N）={，} FIRST （→ε）={ε} FOLLOW （N）={)}

由于SELECT(N →, S N)∩SELECT(N →ε) ={，}∩ { )}= 所以文法是LL(1)的。

预测分析表（Predicting Analysis Table）

也可由预测分析表中无多重入口判定文法是LL(1)的。 (3) 对输入串（a,a）#的分析过程为：

可见输入串（a,a）#是文法的句子。 第3 题

已知文法G[S]：

S→MH|a H→LSo|ε K→dML|ε L→eHf M→K|bLM

判断G 是否是LL(1)文法，如果是，构造LL(1)分析表。 答案：

文法展开为： 0） S→M H 1） S→a 2） H→L S o 3） H→ε

4） K→d M L 5） K→ε 6） L→e H f 7） M→K 8） M→b L M

非终结符 FIRST 集 FOLLOW 集 S {a,d,b,ε,e} {#,o} M {d,ε,b} {e,#,o} H {ε,e} {#,f,o} L {e} {a,d,b,e,o,#} K {d,ε} {e,#,o} 对相同左部的产生式可知：

SELECT(S→M H)∩SELECT(S→a) ={ d,b ,e，#,o }∩ { a }= SELECT(H→L S o)∩SELECT(H→ε) ={ e }∩ { #,f,o }= SELECT(K→d M L)∩SELECT(K→ε) ={ d }∩ { e,#,o }= SELECT(M→K)∩SELECT(M→b L M) ={ d，e,#,o }∩ { b }= 所以文法是LL(1)的。 预测分析表：

由预测分析表中无多重入口也可判定文法是LL(1)的。 第7 题

对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法?试对下面 文法进行改写，并对改写后的文法进行判断。

(１)A→baB|ε

B→Abb|a

(2) A→aABe|a B→Bb|d

(3) S→Aa|b A→SB B→ab

答案：(１)先改写文法为：

0) A→baB 1) A→ε 2) B→baBbb 3) B→bb 4) B→a

再改写文法为：

0) A→baB 1) A→ε 2) B→bN 3) B→a 4) N→aBbb 5) N→b

预测分析表：

由预测分析表中无多重入口判定文法是LL(1)的。 （2） 文法： A→aABe|a B→Bb|d

提取左公共因子和消除左递归后文法变为：

0) A→a N 1) N→A B e 2) N→ε 3) B→d N1 4) N1→b N1 5) N1→ε

非终结符 FIRST 集 FOLLOW 集 A {a} {#,d} B {d} {e} N {a,ε} {#,d} N1 {b,ε} {e}

对相同左部的产生式可知：

SELECT(N→A B e)∩SELECT(N→ε) ={ a }∩ {#,d }= SELECT(N1→b N1)∩SELECT(N1→ε) ={ b }∩ { e }= 所以文法是LL(1)的。

预测分析表（Predicting Analysis Table）

也可由预测分析表中无多重入口判定文法是LL(1)的。 （3）文法：

S→Aa|b A→SB B→ab

第1 种改写：用A 的产生式右部代替S 的产生式右部的A 得：

S→SBa|b B→ab

消除左递归后文法变为： 0) S→b N 1) N→B a N 2) N→ε 3) B→a b

非终结符 FIRST 集 FOLLOW 集 S {b} {#} B {a} {a} N {ε,a} {#}

对相同左部的产生式可知：SELECT(N→B a N)∩SELECT(N→ε) ={ a }∩ {# }=