预测分析

• 递归的预测分析
• 非递归的预测分析

递归的预测分析

在编译原理中，预测分析（Predictive Parsing）或预测分析表是一种自底向上的语法分析方法。递归预测分析通常指的是利用递归下降（Recursive Descent）方法来进行预测分析。递归下降解析器是基于递归的解析算法，它为文法的每个非终结符（non-terminal）编写一个过程（或函数），并且这些过程会相互调用以解析整个输入。

递归下降分析法的核心思想是为每个非终结符编写一个递归函数（也称为分析函数或解析函数）。这些函数检查输入字符串的前缀，如果前缀匹配该非终结符的产生式，则函数会消耗这个前缀，并返回成功；否则，函数会失败，并可能返回一个错误消息。

以下是递归下降预测分析的基本步骤：

1. 定义非终结符的解析函数：对于文法中的每个非终结符A，定义一个函数parseA()。

2. 匹配输入：在每个解析函数中，首先检查输入字符串是否以非终结符A的某个产生式开始。

3. 递归调用：如果匹配成功，则根据产生式的右侧，递归调用相应的解析函数。

4. 错误处理：如果输入不匹配任何产生式，则报告语法错误。

5. 回溯：在递归下降分析中，由于输入字符串可能匹配多个产生式，因此解析函数可能需要“回溯”，即撤销之前的匹配决定，并尝试不同的产生式。

6. 终止条件：当解析到达输入字符串的末尾，且成功匹配了文法的起始非终结符时，解析成功。

下面是一个简单的例子，假设我们有以下文法：

E -> E + T | T
T -> T * F | F
F -> (E) | id

我们可以为每个非终结符编写解析函数，例如：

parseE() {
    if (parseE() && lookahead == '+' && match('+')) {
        parseT();
        return true;
    }
    return parseT();
}

parseT() {
    if (parseT() && lookahead == '*' && match('*')) {
        parseF();
        return true;
    }
    return parseF();
}

parseF() {
    if (lookahead == '(' && match('(') && parseE() && lookahead == ')' && match(')')) {
        return true;
    }
    if (isIdentifier(lookahead)) {
        matchIdentifier();
        return true;
    }
    return false;
}

在这个例子中，lookahead是查看下一个输入符号的函数，match是消耗当前输入符号并返回是否成功的函数，matchIdentifier是消耗一个标识符并返回是否成功的函数。

需要注意的是，递归下降分析法要求文法是LL(1)的，这意味着每个非终结符的每个产生式的第一个符号都是不同的，且每个非终结符的每个产生式都不包含左递归。

递归下降分析法的优点是简单直观，易于实现和理解。然而，它也有一些缺点，比如不容易处理左递归和空产生式，以及难以构造高效的错误恢复机制。此外，由于递归下降分析器通常不是基于表驱动的，因此它可能不如某些其他分析方法（如LR分析）高效。

非递归的预测分析

非递归的预测分析法通常指的是使用预测分析表（也称为分析表或解析表）来进行语法分析的方法。这种方法与递归下降分析法不同，因为它不需要为每个非终结符编写递归过程。相反，它构造一个自动机（通常是一个有穷状态机）来根据预测分析表进行决策。

非递归预测分析法的步骤如下：

1. 构建预测分析表：这是非递归预测分析法的核心。预测分析表是一个二维数组，通常表示为M[A, a]，其中A是非终结符的集合，a是终结符或$（表示输入结束符）。表的每个条目包含一个产生式的集合，这些产生式描述了当前非终结符A面对终结符a时应该如何进行推导。

2. 构造有穷状态机：使用预测分析表和有穷状态机的概念，可以构造一个能够识别文法产生的语言的自动机。这个自动机通常包括一个状态栈和一个输入符号栈。

3. 初始化状态机和栈：将初始状态（通常是状态0）压入状态栈，将输入字符串的第一个符号压入输入符号栈。

4. 进行状态转换：从状态栈的顶部取出当前状态，从输入符号栈的顶部取出当前输入符号，然后在预测分析表中查找对应的条目。根据找到的条目，执行相应的动作，这可能包括改变状态、消耗输入符号、压入新的非终结符到状态栈或输入符号栈等。

5. 接受或拒绝：当输入符号栈为空时，如果状态栈的顶部是接受状态，则接受输入字符串；否则，拒绝输入字符串并报告语法错误。

非递归预测分析法的一个关键优点是它不需要递归调用，因此可以更加高效地使用内存。此外，由于它是基于表的，所以更容易实现错误恢复机制。然而，构建预测分析表可能相对复杂，特别是对于包含空产生式或左递归的文法。

需要注意的是，非递归预测分析法要求文法是LL(1)的，这意味着文法必须满足某些条件，以便能够构建无二义性的预测分析表。这些条件包括每个非终结符的每个产生式的第一个符号必须是不同的，以及不存在左递归等。