解析器主要分为自顶向下和自底向上两种。这一节主要介绍自顶向下解析器和LL(1)语法。

自顶向下解析器

• 是一种自顶向下的解析器，它从开始符号开始，逐步将输入串分解为更小的子串，直到整个输入串被解析为一个语法树。自顶向下解析器通常使用递归下降法来实现。
• 分析树的构造方法，从根部开始

自底向上解析器

• 是一种自底向上的解析器，它从输入串的底部开始，逐步将输入串分解为更大的子串，直到整个输入串被解析为一个语法树。自底向上解析器通常使用自底向上的语法分析方法来实现。
• 分析树的构造方法，从叶子开始。

递归下降的语法分析

这一节主要介绍递归下降的语法分析方法。 递归下降的语法分析是一种自顶向下的语法分析方法，它使用递归函数来解析输入串。递归下降的语法分析方法通常使用递归函数来实现。

数据结构上需要用到一个输出缓冲区和一个预测的指针(lookahead) 分析过程

• 自左向右扫描输入串
• 设计一个辅助过程match（，将lookahead指向的位置与产生式迭代生
• 成的终结符进行匹配，如匹配，将lookahead挪到下一个位置
• 为每一个非终结符写一个分析过程
• 该过程可以调用其他非终结符的过程及match
• 这些过程可能是递归的。

给出伪代码:

function parseExpression() {
    parseTerm();
    while (lookahead in ['+', '-']) {
        match(lookahead);
        parseTerm();
    }
}

function parseTerm() {
    parseFactor();
    while (lookahead in ['*', '/']) {
        match(lookahead);
        parseFactor();
    }
}

function parseFactor() {
    if (lookahead == '(') {
        match('(');
        parseExpression();
        match(')');
    } else if (isNumber(lookahead)) {
        matchNumber();
    } else {
        error();
    }
}

消除直接左递归

考虑一个简单文法$S \to Sa|b$，我们使用递归下降的语法分析方法来解析该文法。我们注意到，该文法是左递归的，自顶向下分析方法无法处理左递归。

可能的推导过程如下：

1. $S \to Sa$ （应用第一个产生式）
2. $\to Saa$ （再次应用第一个产生式）
3. $\to Saaa$ （继续应用第一个产生式）
4. $\to ...$ （无限循环）

这种左递归会导致递归下降解析器陷入无限递归，因为每次尝试解析S时都会再次调用解析S的过程。要解决这个问题，我们需要消除左递归，原字符串的特定是 $baaaa......$。我们可以修改成下面的文法，就可以正常工作了：

$S \to bS'$
$S' \to aS' | \epsilon$

这样修改后，解析器就可以正常工作了。

下面我们给出消除直接左递归的一般方法

对于单个左递归产生式：

$$A \to A\alpha|\beta$$

我们可以将其改写为：

$$A \to \beta A^{'}$$

$$A^{'} \to \alpha A^{'} | \epsilon$$

对于多个左递归产生式的情况：

$$A \to A\alpha_1 | A\alpha_2 | ... | A\alpha_n | \beta_1 | \beta_2 | ... | \beta_m$$

改写后的文法为：

$$A \to \beta_1 A' | \beta_2 A' | ... | \beta_m A'$$

$$A' \to \alpha_1 A' | \alpha_2 A' | ... | \alpha_n A' | \epsilon$$

示例： 给定文法： $A \to Aa | Ab | c | d$

1. 识别左递归产生式：$A \to Aa$ 和 $A \to Ab$
2. 提取非左递归产生式：$c$ 和 $d$
3. 引入新非终结符$A'$
4. 改写文法： $A \to cA' | dA'$
   $A' \to aA' | bA' | \epsilon$

改写后的文法消除了直接左递归，同时保持了原语言的表达能力。

上面是消除直接左递归的例子，下面给出如何消除间接左递归，间接左递归相比直接左递归不是十分明显，但消除起来也不是很困难。

消除间接左递归

间接左递归是指通过多个产生式间接形成的左递归。例如：

$A \to Ba$
$B \to Ab | c$

消除间接左递归的步骤如下：

1. 对非终结符进行排序：$A_1, A_2, ..., A_n$
2. 对于每个$A_i$，从$A_1$到$A_{i-1}$，将$A_j \to A_i\alpha$替换为$A_j \to \beta_1\alpha | \beta_2\alpha | ... | \beta_k\alpha$，其中$A_i \to \beta_1 | \beta_2 | ... | \beta_k$是$A_i$的所有产生式
3. 消除$A_i$的直接左递归

示例： 给定文法： $A \to Ba | a$
$B \to Ab | c$

1. 排序非终结符：$A, B$
2. 处理 $A$：没有间接左递归
3. 处理 $B$：
   • 将 $B \to Ab$替换为$B \to Baa | aa$（因为 $A \to Ba | a$）
   • 现在 $B$有直接左递归：$B \to Baa | aa | c$
4. 消除 $B$ 的直接左递归： $B \to aaB' | cB'$
   $B' \to aaB' | \epsilon$

最终消除间接左递归后的文法：
$A \to Ba | a$
$B \to aaB' | cB'$
$B' \to aaB' | \epsilon$

左公共因子

左公共因子是指多个产生式具有相同的前缀。例如：

$A \to aB | aC | d$

其中$a$是左公共因子。左公共因子会导致预测分析时出现不确定性，因为无法确定选择哪个产生式。

提取左公共因子的步骤如下：

1. 找出具有相同前缀的产生式
2. 提取公共前缀，引入新的非终结符
3. 将剩余部分作为新产生式的右部

示例： 给定文法： $A \to aB | aC | d$

1. 找出左公共因子：$a$出现在前两个产生式中
2. 提取公共前缀，引入新非终结符$A'$
3. 改写文法： $A \to aA' | d$, $A' \to B | C$

改写后的文法消除了左公共因子，使得预测分析更加明确。

左公共因子提取的通用形式： 对于产生式： $A \to \alpha\beta_1 | \alpha\beta_2 | ... | \alpha\beta_n | \gamma_1 | ... | \gamma_m$

提取左公共因子$\alpha$后： $A \to \alpha A' | \gamma_1 | ... | \gamma_m$, $A' \to \beta_1 | \beta_2 | ... | \beta_n$

更新日志

2025/1/12 02:51

查看所有更新日志

• 578c3-更新自底向上和LR(1)语法于 2025/1/12