编译原理与技术主要内容4.1自顶向下语法分析的一般方法例4.1：设文法G[S]：S→cAd，A→ab|a，输入串为cad，自顶向下进行语法分析，并构造相应语法树。这种一般方法存在一些问题：(1)左递归问题自顶向下分析采取最左推导，文法中含有左递归会使自上而下的分析过程陷入无限循环。因此，必须消除文法的左递归。(2)回溯问题反复寻找可正确匹配的产生式时可能需要不断回溯，虚假匹配现象需要使用更复杂的回溯技术。这样将会产生许多额外工作，因此应设法消除回溯。(3)出错处理分析不成功时，要确定出错的具体位置比较困难。(4)效率问题这种带回溯的自顶向下方法实际上是一种穷尽一切可能的试探法，因此效率很低，代价较高，从而该方法只有理论意义，在实际应用中价值不大。4.2LL(1)文法首符集FIRST4.2LL(1)文法4.2LL(1)文法4.2LL(1)文法由上面两个例子可知，一个文法在推导过程中是否会产生回溯，与文法中具有相同左部的每个产生式右部所能推出的开头符号有关系。定义4.1:设G=(VN,VT,P,S)是上下文无关文法，对于α∈V*，V=VN∪VT，定义首符集FIRST(α)为FIRST(α)={a|αβ,a∈VT,α,β∈V*}即FIRST(α)={a|αa…,a∈VT,α∈V*}特别地，若αε，则规定ε∈FIRST(α)，即FIRST(α)是α能推导出的所有在开头位置的终结符或空符。4.2LL(1)文法4.2LL(1)文法4.2LL(1)文法因此，一个文法能否进行确定的自顶向下语法分析，不仅仅与文法中具有相同左部的产生式右部的FIRST集有关系，若有产生式右部可能推出ε，则还与其左部非终结符的后继符号集合有关。定义4.2:设G=(VN,VT,P,S)是上下文无关文法，对于P∈VN，定义后继符集FOLLOW(P)为FOLLOW(P)={a|SP且a∈FRIST(),∈VT*,∈V+}即FOLLOW(P)={a|S…Pa…,a∈VT}。特别地，若S…P，则规定$∈FOLLOW(P)。即FOLLOW(P)是推导过程中所有可能紧跟在P之后的终结符或边界符号$（$用来界定输入串，表示为：$输入串$）。可以看出，开始符号S后面不会跟任何符号，但是有S…S，因此FOLLOW(S)={$}。非终结符A后面可能不跟任何符号，即S…A，也可能跟开始符号S，而S推导的符号串只能以a,d开头，即FIRST(S)={a,d}，因此FOLLOW(A)={a,d,$}。一般地，文法中含有形如P→α|β，P∈VN，α,β∈V*的产生式时，若α,β不能同时推导出空符，不妨设αε,βε，则当FIRST(α)∩(FIRST(β)∪FOLLOW(P))=时，对于非终结符P可以确定地选取产生式。选择集SELECT定义4.3:给定不含左递归的上下文无关文法的产生式P→α,P∈VN,α∈V*，定义选择集SELECT(P→α)为若αε，则SELECT(P→α)=FIRST(α)若αε，则SELECT(P→α)=(FIRST(α)-{ε})∪FOLLOW(P)也就是说，当文法中含有形如P→α|β（P∈VN，α,β∈V*,α,β不同时能推出ε）的产生式时，能够使用确定的自顶向下分析必须使文法满足SELECT(P→α)∩SELECT(P→β)=比如，例4.5中SELECT(S→aA)=FIRST(aA)={a}，SELECT(S→d)=FIRST(d)={d}SELECT(A→bAS)=FIRST(bAS)={b}，SELECT(A→ε)=(FIRST(ε)-{ε})∪FOLLOW(A)={a,d,$}SELECT(S→aA)∩SELECT(S→d)={a}∩{d}=SELECT(A→bAS)∩SELECT(A→ε)={b}∩{a,d,$}=因此，文法G4可以进行确定的自顶向下语法分析。LL(1)文法定义4.4:文法G是LL(1)文法，当且仅当每个非终结符P的任何两个候选式P→α|β（α,β∈V*）满足：①不存在终结符a，使得α和β推出的符号串都能以a开头。即FIRST(α)∩FIRST(β)=②若αε,βε，则α所能推出的符号串的开头符号不在FOLLOW(P)中。即FIRST(α)∩FOLLOW(P)=4.2LL(1)文法4.2LL(1)文法4.2LL(1)文法4.2LL(1)文法4.3递归下降分析技术4.3递归下降分析技术4.3递归下降分析技术4.3递归下降分析技术4.3递归下降分析技术4.3递归下降分析技术4.3递归下降分析技术4.3递归下降分析技术4.3递归下降分析技术4.3递归下降分析技术4.3递归下降分析技术4.3递归下降分析技术4.3递归下降分析技术4.