20 21 22 23 suc
# ExprTail ) ) # ExprTail ) # ExprTail # )) # ) # # # ExprTail→ε ExprTail→ε
5、把下面文法改写为LL(1)的： Declist→Declist；Decl∣Decl Decl→IdList：Type IdList→IdList，id∣id
Type→ScalarType∣array(ScalarTypeList) of Type ScalarType→id∣Bound..Bound Bound→Sign IntLiteral∣id Sign→+∣-∣ε
ScalarTypeList→ScalarTypeList，ScalarType∣ScalarType
分析：本题主要考察理解和运用消除文法的左递归、提取公因子等算法的能力，为判断文法是否是LL(1)文法，还要计算文法的FIRST集合和FOLLOW集合。
消除文法的左递归的基本思想是，将文法规则中的左递归结构变换成等价的右递归结构。提取左公因子的算法，是对包含公共左因子的产生式候选，反复提取左因子，就能够把每个非终结符（包括新引进者）的所有候选首符集变成为两两不相交。消除文法的左递归、提取左公共因子后，再计算文法的各非终结符（X）的首符集FIRST（X）和随符集FOLLOW(X)，然后根据LL(1)文法的充分必要条件（即LL(1)文法的定义）来判断文法是否是LL(1)文法。 解：
首先消除左递归，得到文法G(Declist)： Declist→Decl Declist’ Declist’→；Decl Declist’∣ε Decl→IdList：Type IdList→id IdList’ IdList’→，id List’∣ε Type→ScalarType∣array(ScalarTypeList) of Type ScalarType→id∣Bound..Bound Bound→Sign IntLiteral∣id Sign→+∣-∣ε ScalarTypeList→ScalarType ScalarTypeList’ ScalarTypeList’→，ScalarType ScalarTypeList’∣ε
显然，改造后的文法没有左公共因子，计算每个非终结符的FIRST集合和FOLLOW集合如下： FIRST(Declist)={id} FIRST(Declist’)={；，ε} FIRST(Decl)={id} FIRST(IdList)={id} FIRST(IdList’)={；，ε}
FIRST(Type)={id，+，-，IntLiteral，array} FIRST(ScalarType)={id，+，-，IntLiteral} FIRST(Bound)={id，+，-，InLiteral} FIRST(Sign)={+，-，ε}
FIRST(ScalarTypeList)={id，+，-，IntLiteral } FIRST(ScalarTypeList’)={，，ε}
FOLLOW(Declist)={#} FOLLOW(Declist’)={#} FOLLOW(Decl)={id，；} FOLLOW(IdList)={：} FOLLOW(IdList’)={：} FOLLOW(Type)={id，；} FOLLOW(ScalarType)={id，；，），，} FOLLOW(Bound)={id，；，）’，’..} FOLLOW(Sign)={IntLiteral} FOLLOW(ScalarTypeList)={)} FOLLOW(ScalarTypeList’)={)} 显然，改造后的文法是LL(1)的。
第五章 语法分析——自下而上分析
1、令文法G1为 E→E+T∣T T→T*F∣F F→(E)∣i
证明E+T*F是它的一个句型，指出这个句型的所有短语，直接短语和句柄。 解：因为E=>E+T=>E+T*F，所以E+T*F是该文法的一个句型。 短语：E+T*F，T*F 直接短语：T*F 句柄：T*F
2、考虑下面的表格结构文法G2： S→a∣∧∣(T) T→T，S∣S
（1） 给出(a，(a，a))和(((a，a)，∧，(a))，a)的最左和最右推导。
（2） 指出(((a，a)，^，(a))，a)的规范归约及每一步的句柄。根据这个规范
归约，给出“移进-归约”的过程，并给出它的语法树自下而上的构造过程。
分析：要理解最左推导和最右推导的含义。所谓最左推导是指任何一步α=>β都是对α中的最左非终结符进行替换的；最右推导是指任何一步α=>β都是对α中的最右非终结符进行替换的。 解：
（1）最左推导： S=>(T)=>(T，S)=>(S，S)=>(a，S)=>(a，(T))=>(a，(T，S))=>(a，(S，S))=>
(a，(a，S))=>(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) 最右推导： S=>(T)=>(T，S)=>(T，(T))=>(T，(T，S))=>(T，(T，a))=>(T，(S，a))=>(T，(a，a))=>(S，(a，a))=> (a，(a，a)) S=>(T，S)=>(T，a)=>(S，a)=>((T)，a)=>((T，S)，a)=>((T，(T))，a)=>((T，(S))，a)=>((T，(a))，a)=>((T，S，(a))，a)=>((T，∧，(a))，a)=>((S，∧，(a))，a)=>(((T)，∧，(a))，a)=>(((T，S)，∧，(a))，a)=>(((T，a)，∧，(a))，a)=>(((S，a)，∧，(a))，a)=> (((a，a)，∧，(a))，a) （2）(((a，a)，^，(a))，a)的规范归约如下： (((a，a)，∧，(a))，a) (((S，a)，∧，(a))，a) (((T，a)，∧，(a))，a) (((T，S)，∧，(a))，a) (((T)，∧，(a))，a) ((S，∧，(a))，a) ((T，∧，(a))，a) ((T，S，(a))，a) ((T，(a))，a) ((T，(S))，a) ((T，(T))，a) ((T，S)，a) ((T)，a) (S，a) (T，S) (T)
“移进—归约”过程： 步骤 栈 输入串 动作 0 # (((a，a)，∧，(a))，a)# 预备 1 #( ((a，a)，∧，(a))，a)# 进 2 #(( (a，a)，∧，(a))，a)# 进 3 #((( a，a)，∧，(a))，a)# 进 4 #(((a ，a)，∧，(a))，a)# 进 5 #(((S ，a)，∧，(a))，a)# 归 6 #(((T ，a)，∧，(a))，a)# 归 7 #(((T， a)，∧，(a))，a)# 进 8 #(((T，a )，∧，(a))，a)# 进 9 #(((T，S )，∧，(a))，a)# 归 10 #(((T )，∧，(a))，a)# 归 11 #(((T) ，∧，(a))，a)# 进 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #((S #((T #((T， #((T，∧ #((T，S #((T #((T， #((T，( #((T，(a #((T，(S #((T，(T #((T，(T) #((T，S #((T #((T) #(S #(T #(T， #(T，a #(T，S #(T #(T) #S ，∧，(a))，a)# ，∧，(a))，a)# ∧，(a))，a)# ，(a))，a)# ，(a))，a)# ，(a))，a)# (a))，a)# a))，a)# ))，a)# ))，a)# ))，a)# )，a)# )，a)# )，a)# ，a)# ，a)# ，a)# a)# )# )# )# # # 归 归 进 进 归 归 进 进 进 归 归 进 归 归 进 归 归 进 进 归 归 进 归 3、（1）计算练习2文法G2的FIRSTVT和LASTVT。
（2）计算G2的优先关系。G2是一个算符优先文法吗？ （3）计算G2的优先函数。 （4）给出输入串（a，（a，a））的算符优先分析过程。
分析：在计算得到FIRSTVT集合和LASTVT集合，并构造文法的优先关系矩阵之后，可以根据优先关系矩阵判断文法是否是算符优先文法：如果优先关系矩阵不存在冲突，即文法的任何终结符对至多只存在一种优先关系，则该文法是一个算符优先文法，否则，该文法不是算符优先文法。算符优先法是根据算符的优先关系进行分析，在“移进—归约”过程中，总是根据算符之间的有限关系确定栈顶是否出现了可规约串——最左素短语，一旦出现便进行规约（注意规约使用的产生式），否则进行移入操作。 解：
（1）FIRSTVT和LASTVT如下： FIRSTVT(S)={a，∧，(} FIRSTVT(T)={，，a，∧，(} LASTVT(S)={a，∧，)}
LASTVT(T)={，，a，∧，)}
（3） 构造优先关系表如下：
a ∧ ( a ^ ( < < < ) ， < < < # < < < G2是算符文法，且是算符优先文法。 （3）优先函数表如下： A ∧ ( f 4 4 2 g 5 5 5 ) > > = > > ， > > < > > # > > > = ) 4 2 ， 4 3
（4）输入串（a，（a，a））的算符优先分析过程如下： 栈 输入字符串 动作 # (a，(a，a))# 预备 #( a，(a，a))# 进 #(a ，(a，a))# 进 #(s ，(a，a))# 归 #(t ，(a，a))# 归 #(t， (a，a))# 进 #(t，( a，a))# 进 #(t，(a ，a))# 进 #(t，(s ，a))# 归 #(t，(t ，a))# 归 #(t，(t a))# 进 #(t，(t，a ))# 进 #(t，(t，s ))# 归 #(t，(t ))# 归 #(t，(t) )# 进 #(t，s )# 归 #(t )# 归 #(t) # 进 #s # 归 成功
4、存在一种称为简单优先的自下而上分析法，这种分析法不会把错误句子当作为正确句子。一个文法G，如果它不含ε-产生式，也不含任何右部相同的不同产生式，并且它的任何符号对（X，Y）——X和Y为终结符或非终结符——顶多存在下述三种关系=、<、>之一，则称这个文法G是一个简单优先文法。这三种关系的定义是：
A、X=Y当且仅当G中含有形如P→?XY?的产生式；