自顶向下分析

文章目录

（1）.确定分析的条件1.定义：2.例子：（2）.开始符号集FIRST(α)2.例子：(重要！！！)（3）.后跟符号集FOLLOW(A)2.例子：(重要！！！)（4）.选择集合SELECT(A->α)1.定义（重要的公式！！）：2.例子：(重要！！！)（5）LL(1)文法1.定义：2.LL(1)的含义(重要！！！！重要！！！！)①第一个L表示从左到右扫描输入串。②第二个L表示分析过程用最左推导。③ 1 表明只需要向前看一个符号便可以决定选哪个产生式进行推导。类似地，LL(K)文法需要向前看K个符号才可以确定选用哪个产生式。3.例子：4.非LL(1)文法5.将非LL(1)文法转成LL(1)文法         (必考！)提取左公因子例子：消除左递归例子：6.递归子程序法和预测分析法

（1）.确定分析的条件

1.定义：

从文法的开始符出发，如能根据当前输入符号（单词符号）唯一地确定选用哪个产生式进行推导，则分析是确定的。

2.例子：

（2）.开始符号集FIRST(α)

1.定义：（直接看例子就好了）

2.例子：(重要！！！)

（3）.后跟符号集FOLLOW(A)

1.定义：（直接看例子就好了）

2.例子：(重要！！！)

（看一下框框那里，和划线那里） （FIRST集∩FOLLOW集为空则可确定）

（4）.选择集合SELECT(A->α)

1.定义（重要的公式！！）：

（这个的定义是有用的，可以看看，不是空串的话是FIRST，是空串的话是FOLLOW）

2.例子：(重要！！！)

（5）LL(1)文法

1.定义：

       一个上下文无关文法是LL(1)文法的充分必要条件是，对每个非终结符A的两个不同产生式A->α与A->β，满足SELECT(A->α)∩SELECT(A->β)=空集     （简要概括：充分必要条件为同一非终结符产生式的select集各不相交）

可以看下面例子（select集相交就不符合LL(1)文法）

2.LL(1)的含义(重要！！！！重要！！！！)

①第一个L表示从左到右扫描输入串。

②第二个L表示分析过程用最左推导。

③ 1 表明只需要向前看一个符号便可以决定选哪个产生式进行推导。类似地，LL(K)文法需要向前看K个符号才可以确定选用哪个产生式。

3.例子：

4.非LL(1)文法

①非LL(1)文法：含有左公因子的文法（因为有公因子的话，就有交集了） ②非LL(1)文法：含有左递归的文法（select集也相交）

5.将非LL(1)文法转成LL(1)文法         (必考！)

①提取左公因子 定义：（定义不太重要，直接看例子吧）

提取左公因子例子：

②消除左递归 定义：（定义不重要，直接看例子吧）

消除左递归例子：

消除左递归                   重要！！！ （6）不确定的自顶向下分析（带回溯的自顶向下分析） （应该不考，但是这个不难，可以看看） 不符合LL(1)文法的时候可以用回溯的方法来推导: （例2可以不用看，因为和例1是一个意思）

6.递归子程序法和预测分析法

（下面这个例题可以拿来复消除左递归和求select集，挺好的）