自顶向下语法分析方法
-
什么叫确定：
两个确定：①确定对最左的非终结符进行替换（最左推导）②对于同一个非终结符，确定一个产生式进行推导（SELECT集，无回溯）。
-
一个上下文无关文法是LL(1)文法的充分必要条件：
关于一个非终结符的各个产生式的可选集互不相交。
-
LL(1)文法的判定过程：
-
检查产生式中是否有含有左递归或左公因子：
含有左递归或左公因子的文法一定不是LL(1)文法；
不含有左递归或左公因子的文法也不能确定是否为LL(1)文法；
-
标记能推导出ε的非终结符：
先找出能直接推出ε的非终结符，然后再查看其他产生式的右部，通过这些非终结符检查还有没有其他非终结符也可推出ε，直到没有发现为止。
-
计算每个产生式的FIRST集：
①如果这个产生式右部第一个字符是终结符，那么这个终结符就属于它的FIRST集。
②如果这个产生式右部第一个字符是非终结符，那么这个非终结符的FIRST集就属于它的FIRST集。
如果这个非终结符的FIRST集中含ε，那么后面的字符如果是终结符......
③如果这个产生式右部可以推出ε，那么ε也属于它的FIRST集。
-
计算每个非终结符的FOLLOW集：
首先向开始符号的FOLLOW集中添加
#，然后对于所有非终结符，不断的找含有它的产生式右部：①该非终结符后面的字符若是终结符，那么这个终结符就属于它的FOLLOW集；
②该非终结符后面的字符若是非终结符，那么这个非终结符的FIRST()集中的所有元素就属于它的FOLLOW集；
如果这个非终结符的FIRST()集中含ε，将ε删去，同时将这个产生式左部FOLLOW集中的所有元素添加至它的FOLLOW集中；
注意：不需要考虑后面的字符了，因为已经包含在FIRST()集中了。
-
计算每个产生式的SELECT集：
①如果这个产生式可以推出ε，那么它的SELECT集是
{FIRST(该产生式右部)-ε}∪FOLLOW(该产生式左部的非终结符)。②如果这个产生式不能推出ε，那么它的SELECT集是
{FIRST(该产生式右部)}。 -
检查相同左部产生式的SELECT集的交集：
检查相同左部产生式的SELECT集的交集，如果全为空集说明该文法是LL(1)文法，反之则不是。
-
-
消除左公因式：
有显式的左公因式和隐式的左公因式，对于隐式的左公因式要先化成显式；
例：
显式：
A→aB|aC
隐式：
A→ad|Bc
B→ae
解决方法：类似合并同类项，将左公因式提出，不同的部分用或连接，并用一个新的非终结符指向它。
注意：某些特殊的含左公因式的文法可能会出现循环替换的情况，此时无法解决左公因式问题。
-
消除左递归：
有直接左递归和间接左递归和一般左递归，对于间接左递归要先化成直接；
例子：
Ⅰ直接（模板）：
P → P α | β
可改写为：
P → βQ（因为P一定是β开头）
Q → αQ | ε（Q就是α+）
其中Q为新增的非终结符Ⅱ间接：
S → PQ | a
P → QS | bⅢ一般：
S → PQ | a
P → QS | b
Q → SP | c
做以下变换：
①S → PQ | a
P → SPS|cS|b②S → SPSQ|cSQ|bQ|a
③按照直接左递归方法消除后：
S → cSQR|bQR|aR
R → PSQR | ε④结果：
S → cSQR|bQR|aR
P → SPS|cS|b
Q → SP | c
R → PSQR | ε -
递归下降分析法：
通过计算的SELECT集判断编写子程序：
例子：
递归下降分析法ParseE'函数表示进入E'的产生式，通过switch函数分离相同左部的产生式，然后依次检查产生式右部字符，如果是终结符，则通过MatchToken函数判断符合，不符合则出错；如果是非终结符，则继续递归跳转至它所对应的Parse函数。
递归下降分析法对应的是最左推导过程
优点：程序结构和层次清晰明了，易于手工实现；
对于语义加工，这种方法十分灵活；
缺点：递归调用可能带来效率问题。 -
表驱动LL(1)分析方法（预测分析法 ）
例子：
预测分析法首先根据计算出的SELECT集绘制出预测分析表
预测分析表然后新建一个分析栈，向空栈中依次压入
#和文法的开始符号E，然后比较剩余输入串的首字符和分析栈顶元素，如果不同，则先将分析栈顶元素出栈，然后将对应预测分析表中的产生式右部<u>从后向前</u>依次入栈；如果相同，则先将分析栈顶元素出栈，并将剩余输入串的首字符删去；然后重复以上过程直到栈为#，剩余输入串也为#，则表示语法匹配成功。分析过程
-
LL(1)分析中的一种错误处理办法 ：
发现错误的情况：
(1) 栈顶的终结符与当前输入符不匹配;
(2) 非终结符A于栈顶，面临的输入符为a，但分析表M的M[A,a]为空 （FIRST(A)中没有a）;应急”恢复策略:
对于错误(1) 跳过输入串中的一些符号直至遇到和栈顶的终结符相同的字符为止。对于错误((2) 跳过输入串中的一些符号直至遇到“同步符号”为止 。
同步符号的选择
(1) 把FOLLOW(A)中的所有符号作为A的同步符号。跳过输入串中的一些符号直至遇到这些“同步符号”，把A从栈中弹出，可使分析继续。（跳过A）
(2) 把FIRST(A)中的符号加到A的同步符号集，当FIRST(A)中的符号在输入中出现时，可根据A恢复分析。 （不跳过A）
