ll(1)句法分析器的设计与实现
作者：万能超
dyet:drdh
摘要：语法分析是编译器的核心部分。 词法分析只是识别字符格式源程序中的每个单词，形成单词的机内表示形式，而这些单词串如何构成更大语法成分的句子则通过语法分析来进行。 语法分析的主要任务是“组词成句”，在词法分析识别单词串的基础上，根据语言的语法生成公式，识别“句子”、“程序”等各种类型的句子，并给出这些句子的语法结构。
关键词：复杂希望式、匹配、非终止符、终止符、FIRST集、FOLLOW集
1引言
L(1)语法是可以进行确定的自上而下语法分析的语法。 自顶向下分析法的基本思路是，从语法的开始符号s开始采用最左导出，逐步推出输入符号串。 换言之，将语法的开始符号s作为语法树的根，自上而下地构建输入符号串(语法树)。 如果叶子的节点是从左到右排列的正好是输入串的话，输入串就是语法的句子，这个语法树就是句子的语法结构。 如果不存在这样的语法树的话，输入符号输出字符串就不是这个语法的句子。 )这种分析过程本质上是一种试探过程，是重复使用不同产生式匹配输入符号串的过程。
如果有语法的话
S-cAd
A-ab|a
输入字符串w=cad。 要自顶向下创建此字符串的分析树，首先创建只有标记s的单个节点树，然后输入指针指向w的第一个符号c。 然后，用s的最初的生成式扩展这个树的话，得到的树如图所示：
SSS
cAd
cAdcAd
(a ) ) )。
aba
(b ) ) c ) )。
最左边的叶子被标记为c，与w的第一个符号一致。 因此，将指针前进到w的第二个符号a，接下来考虑标记为a的词语。 在a的最初选择中扩展a，得到如图(b )所示的树。 现在匹配第二个输入符号a，将输入指针前进到d，然后与标记为b的叶子进行比较。 因为b和d不一致，所以报告失败，返回a，看看是否还有其他选择。 返回a时，必须将指针重置为第二个符号，即第一个进入a的位置。 现在，尝试a的第二个选择，得到图(c )的分析树。 叶a与w的第二个符号一致，叶d与w的第三个符号一致。 这样，产生了w的分析树，宣告分析完全成功。
要实现这种自顶向下的分析法有很多困难：
首先是递归问题。 一个语法包含左递归，当存在非终止符号p时
P=>； Pa
包括左递归在内的语法使上述自上而下的分析过程陷入无限循环。 也就是说，如果要用p使输入列一致，输入记号什么都不识别的情况下，就必须重新求得p进行新的一致。 因此，使用自顶向下分析法需要消除语法的左递归。
其次，是倒退问题。 例如语法： S-xAy
A-**|*
考虑输入字符串x**y。 如果首先对a使用第二个复杂的期望公式，则a成功地使其唯一的子节点*与输入串的第二个符号一致。 但是，s的第三个子节点y与第三个输入符号*不一致。 因此，无法识别输入字符串x**y是一个语句。 但是，如果a最初使用第二个复杂的期望获得的成功匹配是虚假的。 由于这种虚假现象，已经做了很多语义工作应该推倒重来。 这些事情既麻烦又费时间，所以最好消除回溯。 另一方面，ll(1)语法是可以进行确定的自顶向下语法分析的语法，因此也必须排除左递归和回溯。
1. 1消除左递归
直接消除生成式中可见的左递归是比较容易的。 关于非终端符号p的规则是
P-Pa|
不久，卟啉开始出现。 那么，可以将p的规则改写为以下非直接左递归形式：
对过
r-ar|(为空字) ) ) ) ) ) ) r-ar|(为空字) ) )0)
这个形状和原来的形状等价。 也就是说，p发售的符号串是一样的。
一般来说，关于p的所有生成式都是
P-P1|P2……Pm|1| 2|……过
这里，假设各不等于，各自都是开头，则消除p的直接左递归将这些规则改写为P-1R| 2R|.|过r
r-1r|2r|………Mr|
使用该方法，容易删除表面上看到的所有直接左递归。 也就是说，将直接左递归更改为直接右递归。
在间接左递归的消除中，可以采用迭代方法将间接左递归直接变为左递归。
例如有语法：
s-a| (1((1)1) ) ) ) ) ) ) S-A|(1) ) ) ) ) ) )。
a-s(2) )。
因为S=A=S，所以s是间接递归的非终端符号。 为了消除这样间接左递归，只要将式(2)代入式(5)，就能够得到与原来的方法等价的方法(s-s|(3)
表达式是直接左递归，可以用直接消除左递归的方法改写语法，可能的语法： S-进
s-s|
因此，为了消除间接左递归，可以首先检测出具有左递归的非终端符号，将这些非终端符号作为左部的生成式，通过与生成式相关的方法依次直接变为左递归的生成式。 最后，消除其中所有的直接左递归。
/p>下面给出消除左递归的算法：
(1) 把文法G的所有非终结符按任一种顺序排列成P1，P2,……Pn;按此顺序执行;
(2) FOR i:=1 TO n DO
BEGIN
FOR j:=1 TO i-1 DO
把形如Pi->Pjγ。其中Pj->δ1|δ2|…|δk是关于Pj的所有规则;消除关于Pi规则的直接左递归性
END
(3)化简由(2)所得的文法。即去除那些从开始符号出发永远也无法到达的非终结符的产生规则。
1．2消除回溯、提左因子
为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个复杂的盼望去执行任务，并且次复杂的盼望的工作结果是确信无疑的。也就是说，若此复杂的盼望获得成功匹配，那么，这种匹配不会是虚假的；若此复杂的盼望无法完成任务，则任何其它复杂的盼望也肯定也无法完成任务。换句话说，假定现在轮到非终结符A去执行匹配任务，A共有n个复杂的盼望α1，α2，……αn,即A->α1|α2|……αn。A能够根据不同的输入符号指派相应的αi作为全权代表去执行任务，那就肯定无需回溯了。在这里A已不再是让某个复杂的盼望去试探地执行任务，而是根据所面临的输入符号α准确地指派唯一的一个复杂的盼望。其次，被指派复杂的盼望的工作成败也完全代表了A。
2 LL(1)语法分析器的设计策略
首先判别一个文法是否是LL(1)文法，如果不是LL(1)文法则需要转化为LL(1)文法。要判别一个文法是否为LL(1)文法，首先需要给出FIRST集合、FOLLOW集合。
2．1构造FIRST集
根据定义：FIRST(α)={a|α=>a...，a(-Vt}，特别是，若α=>ε，则规定ε(-FIRST(α)
对于文法符号串X(-(Vn∪Vt)＊。其办法是连续使用下面的规则，直至没个集合不在增大为止。
(1) 若X(-Vt，则FIRST(X)={X}。
(2) 若X(-Vn，且有产生式X->a…,则把a加入到FIRST(X)中；若X->ε也是一条产生式则把ε也加到FIRST(X)中。
(3) 若X->Y…是一个产生式且Y(-Vn,则把FIRST(Y)中的所有非ε-元素都加到FIRST(X)中；若X—＞Y1
Y2…Yk是一个产生式，Y1…Yi_1都是非终结符，而且，对于任何j，1≤j≤i-1，FIRST(Yj)都含有ε，则把FIRST(Yj)中的所有非ε-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有ε，j=1，2，…,k，则把ε加到FIRST(X)中。