3 Parsing¶

说明

本文档仅涉及部分内容，仅可用于复习重点知识

1 Context-Free Grammars¶

1.1 Ambiguity¶

一个 grammar 如果分析一个字符串能得到两个 parse trees，就说明它是 ambiguous

2 Top-Down Parsing¶

通用的 CFG 解析算法虽然能处理所有文法，但效率很低，甚至占编译时间的 ⅓，因此实际编译器中会使用针对特定文法的专用算法来提高效率

递归下降分析：从起始符号开始，尝试根据输入内容选择相应的产生式展开，递归地匹配输入。它是预测性的，意味着在每一步，只需看当前输入的一个符号就能决定用哪条产生式。虽然实现简单，但它只能处理 LL(1)（Left-to-right parse; Leftmost-derivation; 1 symbol lookahead）文法（即一种确定性的、无需回溯的文法）

但是存在一个问题：

这就需要 predictive parsing

3 Predictive Parsing¶

预测性分析的基本要求：在自顶向下分析中，解析器需要根据当前输入的第一个符号来决定使用哪条产生式。这就要求，对于同一个非终结符的不同产生式，它们的首终结符集合（FIRST 集）必须互不相交。否则解析器就无法确定该选哪一条

为了让文法适用于预测性分析，需要先计算每条产生式的 FIRST 集（即该产生式可能推导出的第一个终结符）。如果冲突存在，就需要改写文法，通常的做法是消除左递归并进行左公因子提取，使得每个非终结符的各个产生式的 FIRST 集互不相交

3.1 FIRST and FOLLOW Sets¶

FIRST 集：对于任意文法符号串 \(γ\)，FIRST(\(γ\)) 是所有可能从 \(γ\) 推导出的字符串的第一个终结符的集合
FOLLOW 集：对于非终结符 \(X\)，FOLLOW(\(X\)) 是所有可能紧跟在 \(X\) 后面出现的终结符的集合
NULLABLE 集：如果一个非终结符能推出空字符串，那么它就属于 NULLABLE 集

那么对于非终结符 \(X\)，产生式 \(X → γ\)，可能的首终结符可以是：

来自 FIRST(\(γ\)) 的终结符
如果 \(γ\) 可以推导出空串，那么 FOLLOW(\(X\)) 中的任何记号也可以作为首终结符

\[ FIRST(X)= \begin{cases} \lbrace X \rbrace & \text{如果} X \text{是终结符}\\ FIRST(X) \cup FIRST(Y_1Y_2\cdots Y_k) & \text{如果} X \text{是非终结符并且} X \rightarrow Y_1Y_2\cdots Y_k \end{cases} \]

\[ FOLLOW(X)= \begin{cases} FOLLOW(X) \cup FIRST(\beta) & \text{if } Y \rightarrow \alpha X\beta\\ FOLLOW(X) \cup FOLLOW(Y)& \text{if } Y \rightarrow \alpha X \beta \text{ and } \beta \rightarrow \epsilon \end{cases} \]