本节书摘来自华章出版社《编译与反编译技术》一书中的第3章，第3.3节自上而下的语法分析，作者庞建民，陶红伟，刘晓楠，岳峰，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
3.3 自上而下的语法分析所谓自上而下的语法分析方法是指对于一个给定的输入单词符号串，尝试从文法的开始符号出发，寻求该串的一个最左推导，或者试图从根结点出发，自上而下地为该串建立一棵语法树。其本质上是一种试探过程，是一种反复使用不同产生式谋求匹配输入串的过程，对文法的限制比较多。3.3.1 LL(1)分析方法下面首先用一个例子来说明自上而下的语法分析过程。例3.14 假定文法G(S)有如下产生式S→xAy A→cd | c 若输入串为xcy，则自上而下的语法分析过程如下：1）首先按文法的开始符号建立根结点S，并让指示器IP指向输入串的第一个符号x。2）文法关于S的产生式只有一个，利用S的这个产生式将语法树发展为如图3-3a所示。此时，该树的最左叶结点为终结符x与输入串第一字符x匹配。将IP调整为指向下一个输入符号c，期待着与语法树中在x右侧且与x相邻的叶结点A匹配。3）非终结符A有两个候选式，先选用第一个候选式去匹配输入串，于是把语法树发展为如图3-3b所示，这时A子树的最左叶结点c恰与IP所指的字符c匹配。4）将IP调整为指向下一个输入符号y，它期待与图3-3b中第三个叶结点d匹配，但匹配时发现这两个字符是不同的，即匹配失败。这意味着A的第一个候选式此刻不适用于构造输入串xcy的语法分析树。5）因不匹配，将A所生成的这棵子树注销，把指示器IP回退到输入串的第二个字符c。6）A选用第二个候选式去匹配，并生成长语法树如图3-3c所示，这时第二个叶结点c与输入串的第二个结点c匹配。7）将指示器IP指向输入串的下一个待分析字符y，而语法树的下一个未匹配的叶结点也为y，两者恰好匹配。因此，图3-3c的语法树即为输入串xcy的语法树。自上而下的语法分析过程中可能会遇到如下一些问题。
左递归问题定义3.10（直接左递归和间接左递归） 假设P是文法G的一个非终结符，如果存在形如P→Pα的产生式，则称该文法含有直接左递归。如果存在形如P?+Pα的推导，则称该文法含有间接左递归。含有左递归的文法将会使上述的自上而下的语法分析过程陷入无限循环。例3.15 采用自上而下的分析方法分析i*i+i是否为式（3.2）文法的句子。解：按照自上而下的分析思想，选用产生式（1）来推导E ? E + T，并将语法分析树发展为如图3-4a所示。图3-4a所对应的语法树末端结点最左符号为非终结符E，所以选用产生式（1）继续推导E?E+T?E+T+T，并将语法分析树发展为如图3-4b所示。图3-4b中的语法树末端结点最左符号仍为非终结符E，所以仍选择产生式（1）继续推导，也即E?E+T?E+T+T?E+T+T+T如此重复下去，会得到一个无穷循环的推导过程E?E+T?E+T+T?E+T+T+T?…因此，无法用自上而下的分析方法判断i*i+i是否为式（3.2）文法的句子。由例3.15可知自上而下的语法分析方法无法处理左递归文法，因此需要一种方法来消除左递归。通过引入新的非终结符P'可以将直接左递归P→Pα | β其中α不等于ε，β不以P开头，转化为等价的非左递归P→βP'P'→αP' | ε这种方法就是把左递归转化为右递归，由于自上而下的语法分析过程是从左向右进行的，所以右递归不会导致无穷推导问题。例3.16 考虑式（3.2）文法，通过消除E和T的直接左递归后，可以得到如下不含左递归的文法：（1）E→TE' （2）E'→+TE' （3）E'→ε（4）T→FT' （5）T'→*FT'（6）T'→ε（7）F→(E) （8）F→i（3.4）一般而言，假定含有直接左递归的非终结符P的全部产生式如下P→Pα1 | Pα2 | … | Pαm | β1 | β2| … |βn其中，每个α都不等于ε，每个β都不以P开头。那么，消除P的直接左递归性就是把这些产生式改写成： P→β1P' | β2P' | … | βnP'P'→α1P' | α2P' | … | αmP' | ε上述方法只能消除直接左递归，但不能消除间接左递归。例3.17 考虑文法G(S)：S→Qc | c Q→Rb | b R→Sa | a （3.5）该文法虽没有直接左递归，但S、Q、R都是左递归的，比如，S?Qc?Rbc?Sabc然而S不是直接左递归，所以无法通过上述方法来消除左递归。如果一个文法当中不含有循环推导（即形如A?+A的推导）和ε-产生式（以ε为右部的产生式），则以下算法3.1可以消除间接左递归。该算法的基本思想就是对非终结符进行编号，然后通过代入将间接左递归转化为直接左递归，再用上面所介绍的方法消除直接左递归。而循环推导和ε-产生式多数情况下可以从文法中系统地消除。算法3.1 消除文法左递归输入：不含循环推导和ε-产生式的文法G输出：与G等价的不含左递归的文法步骤：1.把文法G的所有非终结符按任一种顺序进行排列，假设排序后记为P1，P2，…，Pn。2.for i:=1 to n
{for m:=1 to i-1
{ 把形如Pi→Pmγ的产生式改写成Pi→δ1γ | δ2γ | … | δkγ；（其中Pm→δ1 |δ2 | … |δk是关于Pm的所有产生式）
}消除关于Pi产生式的直接左递归性
}8.化简由上述所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生式。
例3.18 考虑式（3.5）文法，令它的非终结符的排序为R、Q、S。对于R不含有直接左递归。把R代入到Q的有关候选式中，Q的产生式变为Q→Sab | ab | b现在的Q不含直接左递归，把它代入到S的有关候选后，S变成S→Sabc | abc | bc | c消除S的直接左递归后：S→abcS' | bcS' | cS' S'→abcS' | ε Q→Sab |ab | bR→Sa | a 关于Q和R的产生式已是多余的，化简为：S→abcS' | bcS' | cS' S'→abcS' | ε（3.6）注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。例3.19 若对例3.17中式（3.5）文法的非终结符排序选为S、Q、R，那么，最后所得的无左递归文法是：S→Qc | cQ→Rb | bR→bcaR' | caR' |a R' R'→ bca R' | ε（3.7）式（3.6）和（3.7）文法的等价性是显然的。2.回溯问题由例3.14可知，如果非终结符A有多个候选式存在公共前缀，则自上而下的语法分析无法根据当前输入符号准确地选择用于推导的产生式，只能试探。当试探不成功时就需要退回到上一步的推导，查看A是否还有其他候选式，这就是回溯。由于回溯的存在，可能在已经做了大量的语法分析工作之后，才发现走了一大段错路而必须回头，就要把已经做的一大堆语义工作（指中间代码产生工作和各种表格的登记工作）推倒重来。回溯使得自上而下语法分析只具有理论意义而无实际使用的价值。因此，要使自上而下语法分析具有实用性就要消除回溯。为了消除回溯，必须保证，对文法的任何非终结符，当要用它匹配输入串时，我们能够根据当前所面临的输入符号准确地指派它的一个候选式执行任务。这个准确是指：若此候选式匹配成功，那么这种匹配绝不是虚假的；若此候选式无法完成匹配任务，则任何其他候选式也肯定无法完成该任务。换句话说，假定现在轮到非终极符A执行匹配任务，A共有n个候选式α1，α2，…，αn，即A→α1 | α2 | … | αn，A所面临的当前输入符号为a，如果A能够根据不同的输入符号准确指派相应的候选式αi作为全权代表去执行任务，那就肯定无须回溯了。那么在不带回溯的前提下，对文法需要做什么样的限制呢？前面已经说过，要进行自上而下的语法分析，文法不得含有左递归，因此令G是一个不含左递归的文法。我们首先对G的所有非终结符的每一个候选式α定义首符号集。定义3.11（首符号集） 对一个给定的文法G(S)，其所有非终结符的每一个候选式α的首符号集FIRST(α)定义如下：FIRST(α)={a | α ?* a…，a∈VT}特别是α ?* ε时，规定ε∈FIRST(α)。也即，FIRST(α)是α的所有可能推导的开头终结符或可能的ε。假设A是文法G的一个非终结符，其共有n个候选式α1，α2，…，αn，即A→α1 | α2 | … | αn，则FIRST(A)=FIRST(α1 )?∪?…?∪?FIRST(αn)如果文法G的非终结符A的所有候选式α1，α2，…，αn的首符号集两两相交为空，并且均不含ε，即FIRST(α1)∩FIRST(α2)?∩…∩FIRST(αn)=? 且ε?(FIRST(α1)?∪?FIRST(α2)?∪?…?∪?FIRST(αn))则可以对G的句子进行不带回溯的自上而下的语法分析：如果a∈FIRST (αi)，则可以唯一地选择A的候选式αi来替换A。需要指出的是，许多文法都存在非终结符，其所有候选式的首符号集并非两两相交为空，比如式（3.3）文法。如何将一个文法改造成任何非终结符的所有候选式的首符号集两两相交为空呢？其方法就是提取左公因子。假定关于A的产生式是：A→δβ1 | δ β2 |… | δ βn | γ1 | γ2 | … |γm （其中，每个γ不以δ开头）那么可以将这些产生式改写为：A→δA' | γ1 | γ2 | … |γmA'→β1 | β2 |… |βn经过反复提取左因子，就能够把每个非终结符（包括新引进者）的所有候选首符号集变成为两两不相交。例3.20 对式（3.3）文法提左因子，可以得到如下每个非终结符（包括新引进者）的所有候选首符号集两两相交为空的文法：stmt→ if expr then stmt optional_else_part | otheroptional_else_part→ else stmt| ε 提取左公因子可以解决候选式首符号集两两相交为空的问题，但不一定每个含有左公因子的文法都能在有限的步骤内替换成无左公因子的文法。例3.21 假设有文法G的产生式为：（1）S→Ap | Bq（2）A→aAp | d（3.8）（3）B→aBq | e在式（3.8）文法中，用产生式（2）、（3）的右部替换产生式（1）中的A、B使文法变为：（1）S→aApp | aBqq（2）S→dp | eq（3）A→aAp | d（3.9）（4）B→aBq | e对式（3.9）文法中产生式（1）提取左公共因子可得：S→a(App | Bqq)再引入新非终符S'结果得等价文法为：（1）S→aS'（2）S→dp | eq（3）S'→App | Bqq（4）A→aAp | d（3.10）（5）B→aBq | e同样在式（3.10）文法中，分别用产生式（4）、（5）的右部替换产生式（3）中右部的A、B再提取左公共因子最后结果得：（1）S→aS'（2）S→dp | eq（3）S'→aS''（4）S'→dpp | eqq（5）S''→Appp | Bqqq（6）A→aAp | d（3.11）（7）B→aBq | e可以看出若对式（3.11）文法中产生式（5）的A、B继续用产生式（6）、（7）的右部替换，只能使文法的产生式无限增加，但不能得到提取左公共因子的预期结果。如果文法不含左递归，并且对于文法中每一个非终结符A的各个产生式的候选首符号集两两不相交，是否就一定可以进行确定的自上而下的语法分析呢？如果文法的非终结符A的某个候选式αi的首符号集 FIRST(αi)中含ε，并且文法允许当前输入符号a在某个句型中紧跟在非终极符A后面出现，与此同时，存在A另一个候选式αj的首符号集中含有a，此时就无法确定a是跟在A后面的符号，还是推导出来的首符号，也就无法决定是选择αi还是αj，由此可知，非终结符A的后继终结符也是影响候选式选择的重要信息。因此引入非终结符A的后继终结符集的概念。定义3.12（后继终结符集） 对一个给定文法G(S)，A是其一个非终结符，A的后继终结符集FOLLOW(A)定义如下：FOLLOW(A) = {a | S ?*…Aa…，a∈VT}如果A是某个句型的最右符号，也即S ?*…A，那么“#”属于FOLLOW(A)。换句话说，FOLLOW(A)是G(S)的所有句型中出现在紧接A之后的终结符或“#”。引入FOLLOW(A)之后，A的某个候选式αi的首符号集FIRST(αi)中含ε，如果当前输入符号a不属于A的其他候选式的首符号集，但是a属于FOLLOW(A)，那么仍可以唯一地选择αi来代替A，实现不带回溯的自上而下的语法分析，即，如果αi?*ε，a∈FOLLOW(A)且对A的其他候选式αj (i≠j)，FIRST(αj)?∩?FOLLOW(A) = ?均成立，就可以选择来αi来代替A，从而可以对G的句子进行确定的自上而下分析。综上所述，为了能够进行不带回溯的自上而下的语法分析，则文法G需要满足：对于其每一个非终结符号A的任何两个不同产生式A→α | β，下面的条件成立。1）FIRST(α)?∩?FIRST(β)=?。2）假若β?*ε，那么，FIRST(α)∩ FOLLOW(A)=?。假若α?*ε，那么，FIRST(β)∩ FOLLOW(A)=?。称满足上述条件的文法G是LL(1)文法。第一个“L”代表从左向右扫描输入符号串，第二个“L”代表产生最左推导，“1”代表在分析过程中执行每步推导都要向前查看一个输入符号。对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为A→α1 | α2 | … | αn1）若a∈FIRST(αi)，则指派αi执行匹配任务。2）若a不属于任何一个候选首符号集，则：①若ε属于某个FIRST(αi)且a∈FOLLOW(A)，则选择来αi来代替A。②否则，a的出现是一种语法错误。任何LL(1)文法都是无二义的，且不含左递归，但并不是所有的语言都可以用LL(1)文法来描述，因此，不带回溯的自上而下的语法分析只能分析一部分上下文无关语言。不存在这样的算法，即它能判定任意上下文无关语言能否由LL(1)文法产生，但存在一种算法，它能判定任一文法是否为LL(1)文法。下面就是讨论LL(1)文法的判断问题。要判断一个文法是不是LL(1)文法，由其定义可知需要求出该文法所有候选式的FIRST集和所有非终结符的FOLLOW集。下面介绍FIRST集和FOLLOW集的计算方法。算法3.2和算法3.3分别用来计算单个文法符号X和文法符号串α的FIRST集，算法3.4是用来计算非终结符A的FOLLOW集。算法3.2 计算FIRST(X)输入：文法G=(VT，VN，P，S)，X∈(VT?∪?VN)输出：FIRST(X)步骤：对每一文法符号X∈VT?∪?VN，连续使用下面的规则，直至每个集合FIRST(X)不再增大为止：1.若X∈VT，则FIRST(X)={X}。2.若X∈VN，且有产生式X→a…，则a∈FIRST(X)；3.若X∈VN，且X→ε，则ε∈FIRST(X)；4.若X∈VN，且X→Y…是一个产生式，Y∈VN，则把FIRST(Y)中的所有非ε-元素都加到FIRST(X)中；5.若X∈VN，X→Y1Y2…Yk是一个产生式，Y1…Yi-1?*ε，则把FIRST(Yj) (1≤j≤i-1)中的所有非ε-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有ε (1≤j≤k)，则把ε加到FIRST(X)中。算法3.3 计算FIRST(α)输入：文法G=(VT，VN，P，S)，α∈(VT?∪?VN) *，α=X1…Xn输出：FIRST(α)步骤：
1.计算FIRST(X1)； 2. FIRST(α):= FIRST(X1)-{ε}； 3. k:=1； 4. while (ε∈FIRST(Xk) and k<n) do 5. { FIRST(α):= FIRST(α)?∪?(FIRST(Xk+1)-{ε})； 6. k:=k+1} 7. if (k=n and ε∈FIRST(Xk)) then FIRST(α):=FIRST(α) ?∪?{ε}；例3.22 对于式（3.4）文法，构造每个非终结符以及各个非终结符的候选式的FIRST集。解：由算法3.2的步骤1可知，对于每一个终结符有FIRST(+)={+}FIRST()={}FIRST( ( )={ ( }FIRST( ) )={ ) }FIRST(i)={i}由算法3.2的步骤2和步骤3可知FIRST(E')={+, ε}FIRST(T')={*, ε}FIRST(F)={(, i} 因为T→FT'和E→TE'，由算法3.2的步骤4和步骤5可知FIRST(F)?FIRST(T)?FIRST(E)，且有FIRST(T)=FIRST(E)={(, i}由算法3.3，易得对各个非终结符的候选式有如下结果：FIRST(TE')= {(, i}FIRST(+TE')= {+}FIRST(FT')= {(, i}FIRST(FT')= {}FIRST((E))= {(}FIRST(ε)= {ε}算法3.4 计算FOLLOW集输入：文法G=(VT，VN，P，S)，A∈VN输出：FOLLOW(A)步骤：1.对A∈VN，FOLLOW(A) := ?；
FOLLOW(S) := {#}，#为句子的结束符；3.对A∈VN，重复下面的第4步到第5步，直到所有FOLLOW集不变为止。4.若A→αBβ∈P，则FOLLOW(B):=FOLLOW(B)?∪?(FIRST(β)-{ε})；5.若A→αB或A→αBβ∈P且β?*ε (即ε∈FIRST(β))，则FOLLOW(B):=FOLLOW(B)?∪?FOLLOW(A)；例3.23 对于式（3.4）文法，构造每个非终结符的FOLLOW集，并判断该文法是否为LL(1)文法。解：依据例3.22中的计算结果，构造FOLLOW集的步骤如下：1）FOLLOW(E)={#}；2）由E→TE'知FIRST(E')-{ε}?FOLLOW(T)，即FOLLOW(T)={+}；3）由T→FT'知FIRST(T')-{ε}?FOLLOW(F)，即FOLLOW(F)={*}；4）由F→(E)知FIRST( ) ) ?FOLLOW(E)，即FOLLOW(E)={)，#}；5）由E→TE'知FOLLOW(E) }?FOLLOW(E')，即FOLLOW(E')={)，#}；6）由E→TE'且E'→ε知FOLLOW(E) }?FOLLOW(T)，即FOLLOW(T)={+，)，#}；7）由T→FT'知FOLLOW(T) }?FOLLOW(T')，即FOLLOW(T')={+，)，#}；8）由T→FT'且T'→ε知FOLLOW(T) }?FOLLOW(F)，即FOLLOW(F)={*，+，)，#}。最终的计算结果如下FOLLOW(E)={)，#}FOLLOW(E')={)，#}FOLLOW(T) ={+，)，#}FOLLOW(T')={+，)，#}FOLLOW(F) ={*，+，)，#}根据LL(1)文法的定义，只有E'、T'和F有多于一个的候选式，所以只需考虑这些产生式即可。由例3.22中的计算可知，对于E'→+TE' | ε，FIRST(+TE')={+}，FIRST(ε)={ε}，两者相交为空，并且FIRST(+TE')?∩?FOLLOW(E')= ?对于T'→FT' | ε，FIRST(FT')={*}，FIRST(ε)={ε}，两者相交为空，并且FIRST(*FT')?∩?FOLLOW(T')= ?对于F→(E) | i，FIRST((E))={(}，FIRST(i)={i}，两者相交为空。因此式（3.4）文法为LL(1)文法。3.3.2 预测分析程序预测分析法又称LL(1)分析法，是一种不带回溯的非递归自上而下分析法。其基本思想是根据输入串的当前输入符号来唯一确定选用某个产生式来进行推导；当这个输入符号与推导的第一个符号相同时，再取输入串的下一个符号，继续确定下一个推导应选的产生式；如此下去，直到推导出被分析的输入串为止。预测分析程序采用预测分析法实现语法分析，又称为预测分析器或者LL(1)分析器。预测分析程序采用表驱动的方式来实现，包含一个输入缓冲区、一个输出缓冲区、一个符号栈、一个预测分析表（又称为LL(1)分析表）和一个总控程序，如图3-5所示。其中：1）输入缓冲区用来存放待分析的符号串，它以界符“#”作为结束标志（“#”不是文法的终结符，我们总把它当做输入串的结束符）。2）输出缓冲区用来存放分析过程中所使用的产生式序列。3）符号栈中存放分析过程中的文法符号，分析开始时栈底先放入一个“#”，然后再压入文法的开始符号；当分析栈中仅剩“#”，输入串指针也指向待分析串尾的“#”时，分析成功。4）预测分析表用一个矩阵（或二维数组）M[A，a]表示，其中A为非终结符，而a为终结符或“#”。分析表元素M[A，a]中的内容为一条关于A的产生式，表明当A面临输入符号a时当前推导所应采用的候选式；当元素内容为空白（空白表示“出错标志”）时，则表明A不应该面临这个输入符号a，即输入串含有语法错误。5）总控程序根据符号栈栈顶符号X和当前输入符号a来决定分析器的动作：① 若X=a='#'，则分析成功，分析器停止工作。② 若X=a≠'#'，即栈顶符号X与当前扫描的输入符号a匹配，将X从栈顶弹出，输入指针指向下一个输入符号，继续对下一个字符进行分析。③ 若X为非终结符A，则查M[A，a]：a）若M[A，a]中为一个A的产生式，则将A自栈顶弹出，并将M[A，a]中的产生式右部符号串按逆序逐一压入栈中；如果M[A，a]中的产生式为A→ε，则只将A自栈顶弹出。b）若M[A，a]中为空，则发现语法错误，调用出错处理程序进行处理。对于任意一个给定的文法G=(VT，VN，P，S)，其预测分析程序的总控程序可以用算法3.5来描述。算法3.5 预测分析程序的总控程序。输入：输入串w和文法G=(VT，VN，P，S)的预测分析表M输出：如果w属于L(G)，则输出w的最左推导，否则报告错误步骤：
1. 将栈底符号#和文法开始符号S压入栈中； 2. repeat 3. X:=当前栈顶符号； 4. a:=当前输入符号； 5. if X∈{VT?∪?{#}} then 6. if X= =a then 7. { if X != # then 8. { 将X弹出栈； 9. 前移输入指针}} 10. else error 11. else 12. if M[X，a]=X→Y1Y2…Yk then 13. { 将X弹出栈； 14. 依次将Yk，…，Y2，Y1压入栈； 15. 输出产生式X→Y1Y2…Yk } 16. else error 17. until X=#例3.24 已知式（3.4）文法的预测分析表如表3-1所示，试对输入串i1*i2+i3利用分析表3-1进行预测分析。表3-1 式（3.4）文法的预测分析表
i + * ( ) #E E→TE' E→TE' E' E'→+TE' E'→ε E'→εT T→FT' T→FT' T' T'→ε T'→*FT' T'→ε T'→εF F→i F→ (E)
解：利用分析表对输入串i1*i2+i3进行预测分析的步骤如表3-2所示。表3-2 对输入串i1*i2+i3进行预测分析的过程步骤 符号栈 输入缓冲区 输出 步骤 符号栈 输入缓冲区 输出步骤 符号栈 输入缓冲区 输出 步骤 符号栈 输入缓冲区 输出0 #E i1*i2+i3# 6 #E'T'F i2+i3# 1 #E'T i1*i2+i3# E→TE' 7 #E'T'i i2+i3# F→i2 #E'T'F i1*i2+i3# T→FT' 8 #E'T' +i3# 3 #E'T'i i1*i2+i3# F→i 9 #E' +i3# T'→ε4 #E'T' *i2+i3# 10 #E'T+ +i3# E'→+TE'5 #E'T'F i2+i3# T'→*FT' 11 #E'T i3# 12 #E'T'F i3# T→FT' 15 #E' # T'→ε13 #E'T'i i3# F→i 16 # # E'→ε14 #E'T' #
在表驱动的预测分析器中，除了预测分析表因文法的不同而异之外，符号栈、总控程序都是相同的。因此，构造一个文法的预测分析器实际上就是构造该文法的预测分析表。构造预测分析表的主要思想如下：如果A→α是产生式，当A呈现于栈顶：1）当前输入符号a∈FIRST(α)时，α应被选作A的唯一代表，即用α展开A，所以M[A，a]中应放入产生式A→α。2）当α?*ε时，如果当前输入符号b（包括#）∈FOLLOW(A)，则认为A自动得到匹配，因此，应把产生式A→α放入M[A，b]中。根据上述思想，在对文法G的每个非终结符A及其任意候选α都求出FIRST(α)和FOLLOW(A)之后，便可得到预测分析表的构造方法，如算法3.6所示。利用算法3.6，可以构造任何文法的分析表，但对于某些文法，有些M[A，a]中可能有若干条产生式，这称为分析表的多重定义或者多重入口。一个文法G(S)，若它的分析表M不含多重定义，则称它是一个LL(1)文法，它所定义的语言恰好就是它的分析表所能识别的全部句子。如果G是左递归或二义的，那么，M至少含有一个多重定义。因此，消除左递归和提取左因子将有助于获得无多重定义的分析表M。可以证明，一个文法G的预测分析表M不含多重定义，当且仅当该文法为LL(1)文法。算法3.6 构造预测分析表输入：文法G=(VT，VN，P，S)输出：文法G的预测分析表M步骤：
1. for 文法G的每个产生式A→α { 2. for 每个终结符号a∈FIRST(α) 3. 把A→α放入M[A，a]中； 4. if ε∈FIRST(α) then 5. { for 任何b∈FOLLOW(A) 6. 把A→α放入M[A，b]中；} } 7. for 所有无定义的M[A，a] 标上错误标志例3.25 对于式（3.4）文法，构造其相应的预测分析表。解：根据算法3.6检查文法的每一个产生式。1）对于产生式E→TE'：由例3.22中的计算结果可知，FIRST(TE')= { (，i }，故应把E→TE'放入M[E，(]和M[E，i]中。2）对于产生式E'→+TE'：同样由例3.22中的计算结果可知，FIRST(+TE')={ + }，所以，应把E'→+TE放入M[E'，+]中。3）对于产生式E'→ε：由于FOLLOW(E')={ )，# }，故应把E'→ε放入M[E'，)]和M[E'，#]中。4）依次检查其余产生式，就可得如表3-1所示的预测分析表。
