非终结符号 <项> 的分析程序如下：
<项>→<因子>{（* | /）<因子>} 项 因子 INPUTSYM=下一个符号 Y INPUTSYM=’*’ N Y INPUTSYM=’/’ N 出口
非终结符号 <因子> 的分析程序如下：
<因子>→ID|NUM|(<表达式>) 复值语句的分析程序
因子 N INPUTSYM=’ID’ Y INPUTSYM=下一个符号 N 错误 出口 INPUTSYM=’(’ Y INPUTSYM=下一个符号 Y N 错误 INPUTSYM=’)’
4.4 有文法G[A]：A::=aABe|ε，B::=Bb|b （1）求每个非终结符号的FOLLOW集。 （2）该文法是LL(1)文法吗？ （3）构造LL(1)分析表。 解：
（1） FOLLOW(A)=First(B)∪{#}={b,#}
FOLLOW(B)={e,b}
（2） 该文法中的规则B::=Bb|b为左递归，因此该文法不是LL(1)文法 （3） 先消除文法的左递归（转成右递归），文法变为：A::=aABe|ε，B::=bB’，B’=bB’|ε，
该文法的LL(1)分析表为： A B B’ a e b a e b POP POP ， PUSH(B’b) POP ， PUSH(B’b) POP, NEXTSYM # POP POP ， PUSH(eBAa) POP, NEXTSYM POP POP, NEXTSYM INPUTSYM=’NUM’ Y N 表达式
# A B B’ a A→aABe e B’→ε b A→ε B→bB’ B’→bB’ ACCEPT # A→ε 更常用且简单的LL(1)分析表：
4.5 若有文法A→(A)A|ε
（1）为非终结符A构造FIRST集合和FOLLOW集合。 （2）说明该文法是LL(1)的文法。 解：
（1）FIRST(A)＝｛(, ε｝ FOLLOW(A)＝｛)，#｝ （2）
该文法不含左递归；
FIRST（(A)A）={(}，FIRST（ε）={ε}，FIRST（(A)A）∩FIRST（ε）=Φ， 且FOLLOW(A)＝｛)，#｝，FIRST（(A)A）∩ FOLLOW(A) =Φ， 因此，该文法满足LL(1)文法的条件，是LL(1)文法。
4.6 利用分析表4-1，识别以下算术表达式，请写出分析过程。 （1）i+i*i+i （2）i*(i+i+i) 解：
（1）i+i*i+i 步骤 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 分析栈 #E #E’T #E’T’F #E’T’i #E’T’ #E’ #E’T+ #E’T #E’T’F #E’T’i #E’T’ #E’T’F* #E’T’F #E’T’i #E’T’ #E’ #E’T+ #E’T 余留输入串 i+i*i+i# i+i*i+i# i+i*i+i# i+i*i+i# +i*i+i# +i*i+i# +i*i+i# i*i+i# i*i+i# i*i+i# *i+i# *i+i# i+i# i+i# +i# +i# +i# i# 分析表元素 POP,PUSH(E’T) POP,PUSH(T’F) POP,PUSH(i) POP,NEXTSYM POP POP,NEXTSYM POP,PUSH(T’F) POP,PUSH(i) POP,NEXTSYM POP,NEXTSYM POP,PUSH(i) POP,NEXTSYM POP POP,NEXTSYM POP,PUSH(T’F) 所用产生式 E→TE’ T→FT’ F→i T’→ε T→FT’ F→i F→i T’→ε T→FT’ POP,PUSH(E’T+) E’→+TE’ POP,PUSH(T’F*) T’→*FT’ POP,PUSH(E’T+) E’→+TE’
19 20 21 22 23 （2）i*(i+i+i) 步骤 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #E’T’F #E’T’i #E’T’ #E’ # 分析栈 #E #E’T #E’T’F #E’T’i #E’T’ #E’T’F* #E’T’F #E’T’ )E( #E’T’ )E #E’T’ ) E’T #E’T’ ) E’ T’F #E’T’ ) E’ T’i #E’T’ ) E’ T’ #E’T’ ) E’ #E’T’ ) E’T+ #E’T’ ) E’T #E’T’ ) E’T’F #E’T’ ) E’T’i #E’T’ ) E’T’ #E’T’ ) E’ #E’T’ ) E’ T+ #E’T’ ) E’ T #E’T’ ) E’ T’F #E’T’ ) E’ T’i #E’T’ ) E’ T’ #E’T’ ) E’ #E’T’ ) #E’T’ #E’ # i# i# # # # 余留输入串 i*(i+i+i)# i*(i+i+i)# i*(i+i+i)# i*(i+i+i)# *(i+i+i)# *(i+i+i)# (i+i+i)# (i+i+i)# i+i+i)# i+i+i)# i+i+i)# i+i+i)# +i+i)# +i+i)# +i+i)# i+i)# i+i)# i+i)# +i)# +i)# +i)# i)# i)# i)# )# )# )# # # # POP,PUSH(i) POP,NEXTSYM POP POP ACCEPT 分析表元素 POP,PUSH(E’T) POP,PUSH(T’F) POP,PUSH(i) POP,NEXTSYM POP,NEXTSYM POP, PUSH()E() POP,NEXTSYM POP,PUSH(E’T) POP,PUSH(T’F) POP,PUSH(i) POP,NEXTSYM POP POP,NEXTSYM POP,PUSH(T’F) POP,PUSH(i) POP,NEXTSYM POP POP,NEXTSYM POP,PUSH(T’F) POP,PUSH(i) POP,NEXTSYM POP POP POP,NEXTSYM POP POP ACCEPT F→i T’→ε E’→ε 所用产生式 E→TE’ T→FT’ F→i F→(E) E→TE’ T→FT’ F→i T’→ε T→FT’ F→i T’→ε T→FT’ F→i T’→ε E’→ε T’→ε E’→ε POP,PUSH(T’F*) T’→*FT’ POP,PUSH(E’T+) E’→+TE’ POP,PUSH(E’T+) E’→+TE’
4.7 考虑下面简化了的C声明文法： <声明语句>→<类型><变量表>； <类型>→int|float|char
<变量表>→ID,<变量表>|ID
（1） 在该文法中提取左因子。
（2） （3） （4） （5） 解： （1）
为所得的文法的非终结符构造FIRST集合和FOLLOW集合。 说明所得的文法是LL(1)文法。 为所得的文法构造LL(1)分析表。 假设有输入串为“char x，y，z；”，写出相对应的LL(1)分析过程。
规则<变量表>→ID,<变量表>|ID提取公因子如下：<变量表>→ID（,<变量表>|ε） 增加新的非终结符<变量表1>，规则变为：
<变量表>→ID<变量表1> <变量表1>→，<变量表>|ε
C声明文法改变为：
<声明语句>→<类型><变量表>；
<类型>→int|float|char <变量表>→ID<变量表1> <变量表1>→，<变量表>|ε
（2） FIRST(<声明语句>)＝FIRST(<类型>)＝｛int，float，char｝
FIRST(<变量表>)＝｛ID｝ FIRST(<变量表1>)＝｛，，ε｝
FOLLOW(<声明语句>)＝｛#｝
FOLLOW(<类型>)＝FIRST(<变量表>)＝｛ID｝ FOLLOW(<变量表>)＝FOLLOW(<变量表1>)＝｛；｝
（3） 所得文法无左递归，且
FIRST（int）∩FIRST（float）∩FIRST（char）＝Φ FIRST（，<变量表>）∩FIRST（ε）＝Φ
FIRST（，<变量表>）∩FOLLOW(<变量表1>)＝Φ 因此，所得文法为LL(1)文法。
（4） 所得的文法构造LL(1)分析表如下所示： <声明语句> ； int POP ， PUSH(；<变量表><类型>) POP ， PUSH(int) float POP ， PUSH(；<变量表><类型>) POP ， PUSH(float) char POP ， PUSH(；<变量表><类型>) POP ， PUSH(char) ID ， # <类型> <变量表> POP ， PUSH(<变量表1>ID) <变量表1> POP POP ， PUSH(<变量