自顶向下语法分析方法
# 0x1.介绍
语法分析方法是编译程序的核心部分。
语法分析的作用是识别由词法分析给出的单词符号串是否是给定文法的正确句子（程序）。
语法分析的方法分为两大类：
- 自顶向下分析
- 自底向上分析
语法分析的实现可分为两类：
- 确定分析
- 不确定分析，实际编译器构造中几乎都是采用确定的分析方式，不确定分析仅具有理论价值
# 0x2.分块讲解
# 1.自顶向下分析
分类：
- 不确定的分析方法称为带回溯的分析方法，这种方法实际上是一种穷举的试探方法
- 确定的分析方法不用回溯，需对文法有一定的限制，要求文法不能含有左递归,如LL(1)文法。
不确定的自定向下分析可能遇到的问题：
回溯
如下例子：
左递归（无限循环）
如下例子：
所以只需要修改文法，就可以使推导确定性。
# 1.1.确定的自顶向下分析
举例说明：
# 两个特点：
- 每个产生式的右部都由终结符号开始。
- 如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。
# 分析方法：
- 从推导的角度看，从开始符号出发，使用最左推导，试图推导出与输入符号串相同的句子。
- 从语法树的角度看，从根节点出发，反复使用所有可能的产生式，谋求输入串的匹配，试图向下构造一棵语法树，其末端节点正好与输入符号串相同。
# 不确定到确定的方法：
消除左递归：
例子：
消除回溯问题（LL(1)文法的判别）
方法就是将文法改为LL(1)文法。
# 1.2.LL(1)文法的判别方法：
找出能推出ε的所有非终结符，计算FOLLOW时能用到。
计算FIRST集
定义：FIRST (α)是由符号串α推导出的所有新 符号串的第一个终结符号组成的集合，即：
例子：
计算FOLLOW集
定义：FOLLOW(A)是由所有句型中紧跟在A后面的终结符a组成的集合(A∈VN)，即：
计算算法如下：
其中第2步和第3步需要反复进行，因为需要判断非终结符是否能推出ε。
例子：
计算SELECT集
定义：
根据定义判别
定义：对于文法中每个非终结符的任意两个不同的产生式A→α，A→β，满
SELECT(A→α)∩SELECT(A→β)= 空。判断方法：
# 例题：
题解：
# 1.3.某些非LL(1)文法到LL(1)文法的等价变化
步骤：
提取左公共因子
例子：
消除左递归
0.判断左递归
1.消除直接左递归：
2.消除间接左递归：
3.消除文法中一切左递归的算法
# 1.4.预测分析表
预测分析表用来分析字符串是否能被某文法接受，也是程序中的实现过程。
构造预测分析表很简单，就是将select的值填到对应的地方，如下：
然后计算机在接受一个字符串时都会通过这个预测分析表来一步步接受字符串，步骤如下：
- 先将所有字符串全部入字符串栈，开始符号S入符号栈。
- 然后通过预测分析表来输出语句，然后符号栈就会根据语句来出栈栈顶符号和逆序入栈输出的符号，字符串栈和符号栈的栈顶终结符号会同时出栈消去。
- 重复2步骤，直至字符串栈为空，代表该字符串被该语法接受了。
如图所示：
符号栈每次逆序入栈。
另外，在做题时老师要求在每次写完分析过程之后画语法分析树。