回顾例4.1中为输入串构建语法分析树的过程中产生的回溯，是由于面临下一输入符号时，非终结符的多个候选式都可以完成匹配工作，因此无法判断由哪个候选完成展开动作，而产生了试探的过程。为了消除回溯就必须确保进行输入串匹配时，文法的非终结符能够根据所面临的输入符号，准确地指派某一个候选式去执行任务。也就是，任何其他候选式肯定无法完成匹配工作。这样，将不会出现利用候选式试探性地执行任务的过程。
例4.5 判断输入串w=pccadd是否为如下文法的句子
S→p A|qB
A→c Ad|a
输入串语法分析树的构造过程如图4-6所示。以开始符号为根结点，为了与输入符号‘p’相匹配，使用S的第一个候选式完成推导，此时句型变为p A；进而使用A展开树的下一层分支，为了与输入符号‘c’相匹配，使用A的第一个候选式完成推导，得到句型pc Ad；下一个输入符号仍然是‘c’，继续使用A的第一个候选式完成推导，得到句型pcc Ad；最后，由A完成输入符号‘a’的匹配，这次需要选择A的第二个候选式完成推导。最终，构造出了与输入串相匹配的语法树。
图4-6 输入串pccadd确定的自上而下语法分析
依据上述文法为输入串构建语法分析树时，每一步都能够确定应该采用的候选式，没有任何的试探过程。这是因为文法的特点在于，具有相同左部的产生式，右部符号串由不同的终结符开始。因此，在推导过程中完全可以根据当前的输入符号，决定选择相应的候选式进行推导。也就是，哪个候选式的第一个符号与当前输入符号相同就选择哪个候选式。同时，其他候选式因为不能生成与输入符匹配的符号而无法完成推导工作，所以分析过程是唯一确定的。
例4.6 判断输入串w=ccap是否为如下文法的句子
S→Ap|Bq
A→a|cA
B→b|dB
输入串语法分析树的构造过程如图4-7所示。由根结点S出发构造语法树时，对于左部相同但右部以不同非终结符开始的产生式来说，在推导过程中选用哪个候选式不像例4.5所示的文法那样直观。输入串的第一个符号是‘c’，选择S→Ap或是S→Bq，需要知道Ap
或Bq
能够推导出的符号串的首个终结符号是什么。由于‘c’是Ap能够推导出的符号串的首个终结符，但不是Bq能够推导出的符号串的首个终结符，因此仍然能够确定应该选择S→Ap向下推导。
图4-7 输入串ccap确定的自上而下语法分析
依据例4.6所示的文法为输入串构建语法分析树时，每一步也能够确定应该采用的候选式。文法具有与例4.5所示的文法类似的特点，相同左部的产生式右部由不同的终结符或非终结符开始。因为相同左部产生式的各个候选式能够得到的符号串的首个终结符不相同，推导过程中依然可以根据当前的输入符号，决定选择哪个候选式进行推导，而其他候选式无法完成匹配工作。
此外，两个文法中都不含有空产生式。空产生式将为推导带来新的问题，将在下一节进行讨论。
1.FIRST集
为了构造不带有回溯的自上而下分析的文法，需要判断相同左部产生式的各个候选式，能够推导出的符号串的首个终结符是否相同。
定义4.1 文法所有非终结符的每个候选式α，其终结首符集FIRST（α）为
FIPST集(www.xing528.com)
特别是，若α⇒*ε，则ε∈FIRST（α）。
FIRST（α）是α可能推导出的所有符号串的首个终结符或ε构成的集合。如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选αi和αj
FIRST(αi)∩FIRST(αj)=φ
那么，当要求A匹配输入串时，A就能根据所面临的输入符号a，准确地指派终结首符集中包含a的候选式去执行任务，其他候选式一定无法完成推导工作。
2.提取左公因子
许多文法都存在着同一非终结符的候选首符集相交的情况。例如，条件语句的产生式
S→if B then S else S
|if B then S
就是这样一种情形。注意，if、else和then是程序设计语言的关键字，即文法的终结符，不是终结符号串。
通过文法的形式变换可以提取左公因子，将文法改造为任何非终结符的所有候选首符集两两不相交的形式。假定关于A的产生式如下
消除回溯
A→αβ1|αβ2|…|αβn|γ1|γ2|…|γm|
其中，每个γ不以α开头。通过引入新的非终结符A，由A生成左公因子α后面的符号串β，可以将产生式改写为
A→αA|γ1|γ2|…|γm|
A→β1|β2|…|βn
经过反复提取公共左因子，就能够将每个非终结符（包括新引进者）的所有候选首符集变为两两不相交。
例4.7 提取条件语句文法的左公因子
经过上述文法的形式变换，提取条件语句文法的左公因子可得文法
S→if B then S S
S→else S|ε
消除左递归和提取左公因子无法保证将一个文法转换为LL（1）文法，但是在大多数情况下，这两项技术都非常有效。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
