共计 989 个字符，预计需要花费 3 分钟才能阅读完成。
自上而下分析法
语法树的从左到右叶结点 =#，则 #∈L(G)。
1. 文法的逐级优化
打消左递归
- 含有 A→Aa 模式产生式的文法：间接左递归
- 两步或两步以上：间接左递归
打消形式：
- 写正规式→转化为右递归
- 间接：先代入
- 提取左公因子
通过改写产生式来推延决定
预测分析法的工作过程：
从文法开始符号登程，在每一步推导过程中依据以后句型的最左非终结符 A 和以后输出符号 a，抉择正确的 A - 产生式。为保障剖析的确定性，选出的候选式必须是惟一的。
S_文法（简略的确定性文法）
- 每个产生式的右部都以 终结符 开始
- 同一非终结符的各个候选式的 首终结符 都不同
- 留神：S_文法 不含 \(\varepsilon \)产生式
为了退出 \(\varepsilon \)产生式，须要看非终结符前面能跟什么终结符：FOLLOW 集
新定义：
非终结符 A 的后继符号集
- 可能在某个句型中紧跟在 A 后边的终结符 a 的汇合，记为 FOLLOW(A)
产生式的可全集
产生式 A→B 的可全集是指能够选用该产生式进行推导时，对应的输出符号的汇合，记为 SELECT(A→B)
SELECT(A→aB) = {a}
SELECT(A→\( \varepsilon \)) = FOLLOW(A)
q_文法
- 每个产生式的右部或 为 \(\varepsilon \)，或 以终结符开始
- 具备雷同左部的产生式有 不相交的可全集
q_文法不含右部以 非终结符 打头的产生式
新定义：
串首终结符集
- 给定一个文法符号串 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) \)
- LL(1)文法
名称含意
- 第一个“L”示意从左向右扫描输出
- 第二个“L”示意产生最左推导
- “1”示意在每一步中只须要向前看一个输出符号来决定语法分析动作
2. FIRST 集和 FOLLOW 集的计算
每一个都是循环应用，直到不再增大
- FIRST 集
a. 找右侧第一个为终结符或空串
b. 找右侧，从左至右，非终结符的 FIRST 集 - FOLLOW 集
正文完
