Recursive Descent and LL Grammar
A Reminder
LL (1):
•Left-to-right token processing
•Leftmost derivation
•Top-down parsing
•One lookahead token
LL(1) 文法解析详细解读
LL(1) 的基本概念
- L (第一个 L)：
• 表示从左到右对输入的token进行扫描和处理。
• Left-to-right：解析器会按照输入字符串从左到右依次读取每个字符或 token。
- L (第二个 L)：
• 表示生成最左推导（Leftmost Derivation）。
• Leftmost Derivation：在解析过程中，每次优先替换推导出最左侧的非终结符。
- (1)：
• 表示一个符号的前瞻（Lookahead）。
• One Lookahead Token：在决定选择哪个产生式时，解析器只需要查看下一个输入的 token，而不需要回溯或查看多个符号。
LL(1) 的特征
- 左到右解析（Left-to-right）
• 输入流被从左到右逐个符号进行扫描。
• 这种顺序确保了解析过程的连续性和有序性。
- 最左推导（Leftmost Derivation）
• 推导过程中，优先替换最左侧的非终结符。
• 例如，给定文法：$S \rightarrow A \ B, \quad A \rightarrow a, \quad B \rightarrow b$
对于输入字符串 ab ，推导过程如下：
• Step 1: $S \Rightarrow A B$
• Step 2: $A \Rightarrow a$ （替换最左侧的 A ）
• Step 3: $B \Rightarrow b$
• 完成推导： $S \Rightarrow a b$
- 自顶向下解析（Top-down Parsing）
• Top-down 表示从起始符号（Start Symbol）开始，根据文法规则逐步推导出目标字符串。
• 构建语法树时，从树的根节点开始逐层向下扩展到叶子节点。
• 每一步都使用输入符号和预测选择的产生式进行匹配，直到所有的符号匹配完毕。
- 单符号前瞻（One Lookahead Token）
• 在选择产生式时，解析器只需要查看下一个输入符号（lookahead token）。
• 如果每个非终结符的产生式满足 LL(1) 文法的要求（无二义性、FIRST 和 FOLLOW 集合冲突消除），则只需通过下一个 token 唯一确定解析路径。
总结
LL(1) 解析器的特点：
• L1：输入字符串从左到右扫描。
• L2：推导生成最左推导。
• 1：每次选择产生式时，最多前瞻一个 token（One Lookahead）。
• 自顶向下解析（Top-down Parsing）：从起始符号开始逐步向下展开文法规则。
优势：
• 简单高效，不需要回溯。
• 使用 FIRST 和 FOLLOW 集合预测下一步选择的产生式。
适用场景：
• 适用于无二义性的上下文无关文法，且文法规则满足 LL(1) 条件。
Aims
o What is a recursive descent parser
o How does it work？Why does it work？
o How to process a non-terminal
o Work out examples
Top-down parsing
o Constructing the parsing tree from top (root) to bottom(leaves)
o From the start S derives strings (w)
Top-Down Parsing 详细解读
概述
Top-down parsing 是一种从语法树的根节点（起始符号 ）开始，逐步向下扩展到叶子节点的解析方法。
工作原理
- 从根节点开始：
• 根节点对应文法的起始符号 $S$ 。
• 目标是通过一系列推导，生成符合输入字符串 $w$ 的语法树。
- 逐步展开：
• 选择当前非终结符的合适产生式进行替换。
• 每一步解析时，检查输入流中的符号，匹配合适的文法规则。
- 从左到右扫描：
• Top-down parsing 按照输入字符串从左到右的顺序进行匹配，逐个处理输入的符号。
- 递归展开：
• 在处理非终结符时，递归调用，展开对应的产生式，逐步构建解析树。
• 例如对于产生式 $S \rightarrow A B$ ：
• 先展开 $A$
• 然后展开 $B$
过程示例
给定文法 $G$ 和输入字符串 $w$ ：
• 文法规则：$S \rightarrow A B, \quad A \rightarrow a, \quad B \rightarrow b$
• 输入字符串 $w = “ab”$ 。
步骤解析
Step 1: 从起始符号 S 开始：$S \Rightarrow A B$
Step 2: 替换 A ：
• 根据 $A \rightarrow a$ ，得到：$A \Rightarrow a$
所以， S 推导为：$S \Rightarrow a B$
- Step 3: 替换 B ：
• 根据 $B \rightarrow b$ ，得到：$B \Rightarrow b$
所以，最终推导完成：$S \Rightarrow a b$
Top-down Parsing 特点
- 自顶向下（Top-down）：
• 从文法的起始符号开始，逐步展开产生式，构建语法树。
- 逐步匹配：
• 每次只处理当前的非终结符和输入符号，选择合适的产生式进行替换。
- 递归调用：
• 对非终结符的展开通过递归实现，直到所有非终结符被终结符替代为止。
- 无回溯（LL(1)）：
• 如果文法满足 LL(1) 条件，每一步替换都是确定的，不需要回溯。
Top-down Parsing 优势
- 直观易懂：
• 解析过程直接对应语法树的生成过程，自顶向下构建树结构。
- 简单实现：
• 通过递归函数或预测表（如 LL(1) 解析器）可以实现。
- 适用于 LL(1) 文法：
• 在满足 LL(1) 条件的文法中，Top-down parsing 可以高效、准确地解析输入字符串。
总结
Top-down parsing 的核心思想是自顶向下逐步展开文法规则：
• 根节点：起始符号 $S$ 。
• 中间节点：非终结符，通过产生式替换展开。
• 叶子节点：终结符，最终匹配输入字符串中的符号。
这种方法适用于结构清晰、无二义性的上下文无关文法，尤其是 LL(1) 文法。
We have a grammar: G (E)