自上而下分析法
语法树的从左到右叶结点=#，则 #∈L(G)。
1. 文法的逐级优化
- 消除左递归
- 含有A→Aa形式产生式的文法：直接左递归
- 两步或两步以上：间接左递归
- 写正规式→转化为右递归
- 间接：先代入
- 提取左公因子
通过改写产生式来推迟决定
预测分析法的工作过程：
从文法开始符号出发，在每一步推导过程中根据当前句型的最左非终结符A和当前输入符号a，选择正确的A-产生式。为保证分析的确定性，选出的候选式必须是唯一的。
- S_文法（简单的确定性文法）
- 每个产生式的右部都以终结符开始
- 同一非终结符的各个候选式的首终结符都不同
- 注意：S_文法不含\( \varepsilon \)产生式
【[编译原理与设计] 4-1 自上而下分析法】新定义：
- 非终结符A的后继符号集
- 可能在某个句型中紧跟在A后边的终结符a的集合，记为FOLLOW(A)
- 产生式的可选集
- 产生式A→B的可选集是指可以选用该产生式进行推导时，对应的输入符号的集合，记为SELECT(A→B)
SELECT(A→aB) = {a}
SELECT(A→\( \varepsilon \)) = FOLLOW(A)
- 产生式A→B的可选集是指可以选用该产生式进行推导时，对应的输入符号的集合，记为SELECT(A→B)
- q_文法
- 每个产生式的右部或为\( \varepsilon \)，或以终结符开始
- 具有相同左部的产生式有不相交的可选集
新定义：
- 串首终结符集
- 给定一个文法符号串a，a的串首终结符集FIRST(a)被定义为，可以从a推导出的所有串首终结符构成的集合，包括\( \varepsilon \)
- 新 · 产生式的可选集
- 产生式A→B的可选集是指可以选用该产生式进行推导时，对应的输入符号的集合，记为SELECT(A→B)
如果\( \varepsilon \notin FIRST(a) \)，那么SELECT(A→a) = FIRST(a)
如果\( \varepsilon \in FIRST(a) \)，那么\( SELECT(A→a) = (FIRST(a)-\varepsilon) \cup FOLLOW(A) \)
- 产生式A→B的可选集是指可以选用该产生式进行推导时，对应的输入符号的集合，记为SELECT(A→B)
- LL(1)文法
![[编译原理与设计] 4-1 自上而下分析法](http://img.readke.com/220430/14212J555-0.jpg)
文章图片
- 第一个“L”表示从左向右扫描输入
- 第二个“L”表示产生最左推导
- “1”表示在每一步中只需要向前看一个输入符号来决定语法分析动作
每一个都是循环使用，直到不再增大
- FIRST集
a. 找右侧第一个为终结符或空串
b. 找右侧，从左至右，非终结符的FIRST集 - FOLLOW集
![[编译原理与设计] 4-1 自上而下分析法](http://img.readke.com/220430/14212H139-1.jpg)
文章图片
