语法分析

• 文法
  • 定义
    • 文法 $G = (V_N, V_T, S, P)$，其中：
      • $V_N$：非空有限非终结符号集合。
      • $V_T$：非空有限终结符号集合。
      • $S$：开始符号。
      • $P$：有限产生式集合。
    • $V_N \cup V_T = V$，$V_N \cap V_T = \varnothing$。
    • 语言 $L(G)$：从 $G$ 的 $S$ 开始，不断用产生式替换非终结符号，得到的只有终结符号的串集合。
  • 推导和规约
    • 直接推导：当且仅当 $A \to \gamma$ 时，$V = \alpha A \beta \to W = \alpha \gamma \beta$。$V$ 直接推导出 $W$，$W$ 直接规约到 $V$。
    • 多步推导：$V$ 经过 $\alpha_0 \Rightarrow \alpha_1, \alpha_1 \Rightarrow \alpha_2, \cdots, \alpha_{n - 1} \Rightarrow \alpha_n$，$n$ 个推导得到 $W$，则 $V \xRightarrow{*} W$。如果 $V = W$ 或 $V \xRightarrow{*} W$，则 $V \xRightarrow{*} W$。
    • 最左/右推导：从 $V$ 推导到 $W$，总是替换最左/右边的非终结符号。
    • 规范推导：最右推导又称规范推导，逆序为规范规约。
  • 句型与句子
    • 句型：$S \xRightarrow{*} \alpha, \alpha \in (V_N \cup V_T)^*, \alpha$ 为 $G(S)$ 的句型。
    • 句子：$S \xRightarrow{*} \alpha, \alpha \in V_T^*, \alpha$ 为 $G(S)$ 的句子。
    • 规范句型/句子：仅用规范推导得到的句型/句子。
  • 递归
    • 直接递归：$G$ 存在产生式 $A \to \alpha A \beta$ 时，$G$ 为直接递归文法。
    • 间接递归：$G$ 可以有 $A \to \gamma$ 和推导 $\gamma \xRightarrow{+} \alpha A \beta$ 时，$G$ 为间接递归文法。
    • 递归文法：直接与间接递归文法统称递归文法。
    • 左递归：$A \to \gamma$ 且 $\gamma \xRightarrow{+} A \beta$。
    • 右递归：$A \to \gamma$ 且 $\gamma \xRightarrow{+} \alpha A$。
  • 表示
    • BNF
      • 产生式格式：$A \to B \mid c$。
    • EBNF
      • 与 BNF 类似，并包括扩展语法：
        • $\{ A \}_n^m$：$n$ 到 $m$ 个 $A$。
        • $[A]$：$0$ 或 $1$ 个 $A$。
        • $A(B|C)$：可以使用分配律。
    • 语法图
      • 椭圆：非终结符。
      • 矩形：终结符。
      • 箭头：匹配字符串的路径。
  • 二义性
    • 定义：存在一个字符串，一个文法可以推导得到两个不同的语法树，则文法是二义的。
    • 常见原因：
      • 运算符优先级不明确。
      • 运算符结合性不明确。
• 自上而下分析
  • 文法变换
    • 直接左递归消除
      • 对于 $A \to A \alpha | \beta$，则变换为 $A \to \beta A'$，$A' \to \alpha A' | \varepsilon$。
      • 对于 $A \to A \alpha_1 | \cdots | A \alpha_n | \beta_1 | \cdots | \beta_m$，则变换为 $A \to \beta_1 A' | \cdots | \beta_m A'$，$A' \to \alpha_1 A' | \cdots | \alpha_2 A' | \varepsilon$。
    • 间接左递归消除
      • 按顺序枚举所有非终结符 $A_1, \dots, A_n$，对于 $A_i$：
        • 对于 $A_j\ (j < i)$，如果 $A_i \to A_j \alpha$，则带入 $A_j$ 的产生式到 $A_i$ 中。
        • 消除带入后的 $A_i$ 产生式的直接左递归。
    • 回溯消除
      • FIRST
        • $\mathrm{FIRST}(\alpha) = \{ a \mid \alpha \Rightarrow a \beta, a \in V_T \}$。即 $\alpha$ 推导的所有句子的开头。
          • 如果 $a \Rightarrow \varepsilon$，则 $\varepsilon \in \mathrm{FIRST}(\alpha)$，反之也成立。
        • 文法不带回溯的条件：对于 $G$ 中任意非终结符 $A \to \alpha_1 | \cdots | \alpha_n$，$\mathrm{FIRST}(\alpha1), \dots, \mathrm{FIRST}(\alpha_n)$ 两两无交集。
        • 文法不带回溯的候选式选择：对于 $A \to \alpha_1 | \cdots | \alpha_n$ 和当前符号 $a$，选择满足 $a \in \mathrm{FIRST}(\alpha_i)$ 的 $\alpha_i$。
        • $\mathrm{FIRST}$ 的构造是自下而上的。
      • 消除方法
        • 如果 $\mathrm{FIRST}(\alpha_i)$ 和 $\mathrm{FIRST}(\alpha_j)$ 有交集，则交集部分就是左公因子。
        • 将两个候选式分别拆分出交集部分 $\beta$ 和剩余部分 $\alpha_i', \alpha_j'$，$A \to \beta (\alpha_i' | \alpha_j') | \cdots$。
  • 递归下降
    • 按照文法编写函数，每个非终结符对应一个函数，对候选式的推导就是调用函数。
  • LL(1)
    • 算法过程
      • LL(1) 算法包括：
        • 总控程序：算法本身。
        • 分析栈：存放待分析单词。
        • 分析表 $M(A, a)$：$A$ 为非终结符，$a$ 为单词，$M(A, a)$ 表示识别 $a$ 需要的产生式 $A \to \alpha$。如果是空则表示出错。
      • 初始时，分析栈从底部存放结束标志和 $S$。
      • 设栈顶为 $X$，当前单词为 $a$，循环：
        • 若 $X$ 是非终结符：
          • 若 $M(X, a)$ 非空，则根据 $M(X, a)$ 选取产生式，把 $X$ 出栈，把 $M(X, a)$ 倒序入栈。
          • 若 $M(X, a)$ 为空，出错。
        • 若 $X$ 是终结符：
          • 若 $X = a$ 为结束标志，则完全识别成功。
          • 若 $X = a$ 且不为结束标志，则识别 $a$ 成功，出栈 $X$，读取下一个输入。
          • 若 $X \ne a$，则出错。
    • FOLLOW
      • $\mathrm{FOLLOW}(A) = \{ a \mid \dots A a \dots \in L(G(S)), a \in V_T \}$，即语言中在 $A$ 后的所有可能的非终结符 $a$。
      • 计算方法：
        • $\mathrm{FOLLOW}(S) = \#$
        • 对于 $A \to \alpha B \beta$，$\mathrm{FIRST}(\beta) \subseteq \mathrm{FOLLOW}(B)$。
        • 对于 $A \to \alpha B$ 或 $A \to \alpha B \beta$ 且 $\varepsilon \in \mathrm{FIRST}(\beta)$，则 $\mathrm{FOLLOW}(A) \subseteq \mathrm{FOLLOW}(B)$。
        • 自上而下计算。
    • 分析表构造
      • 对于 $A \to \alpha_1 | \cdots | \alpha_n$：
        • 若 $a \in \mathrm{FIRST}(\alpha_i)$，则 $M(A, a) = A \to \alpha_i$。
        • 若 $\varepsilon \in \mathrm{FIRST}(\alpha_i)$ 且 $a \in \mathrm{FOLLOW}(A)$，则 $M(A, a) = A \to \alpha_i$。
• 自下而上分析
  • 基本概念
    • 短语：若 $S \xRightarrow{*} \alpha A \delta$ 且 $A \xRightarrow{+} \beta$，则 $\beta$ 是句型 $\alpha \beta \delta$ 相对于 $A$ 的短语。
      • 从语法树上理解，即选取非终结符节点 $A$，则其子树所有叶子节点按顺序排列是短语。
      • 一般省略句型，使用整个输入串作为分析的句型。
    • 直接短语：$A \to \beta$，即在短语基础上，只需要一步推导。
      • 从语法树上理解，即 $A$ 的子节点都是叶子节点。
    • 句柄：最左边的直接短语。
    • 活前缀：规范句型的前缀，且此前缀的末端不超过句柄的末端。
    • 可行前缀：最长的活前缀，后缀就是句柄。
  • LR 分析
    • LR 分析类方法使用 LR 分析器，分析器算法都相同，区别在于分析表的构造方法。
    • LR 分析器结构：
      • 输入串
      • 分析栈：元素为符号和状态的二元组。
      • 分析表：
        • 每一行对应一个状态，每一列对应一个符号。终结符的列是 ACTION 表，非终结符的列是 GOTO 表。
        • $\mathrm{ACTION}(Q_i, x_j)$ 的取值：
          • $S_{Q_k}$：移进操作，输入串指针向前移动一位，转换到状态 $Q_k$。
          • $r_{k}$：规约操作，选取第 $k$ 个产生式 $A \to \dots x_{j - 1} x_j$，弹出所有匹配的符号和状态，插入产生式左部和 $\mathrm{GOTO}(Q_l, A)$，其中 $Q_l$ 是弹出后的栈顶。
            • 规约操作不会消费输入符号，不同解析器只会基于输入符号决策。
          • 接受：分析成功。
          • 错误：遇到无法识别的符号。
        • $\mathrm{GOTO}(Q_i, A_j)$ 的取值：
          • $Q_k$：规约操作中要转移的下一个状态。
          • 空：$Q_i$ 状态下不可能规约 $A_j$，分析表构造正确时不可能到达这里。
    • 分析的基本方法：不断规约句柄，无法规约时则移进，最终规约到开始符号。
  • LR(0)
    • LR(0) 项目
      • 把所有产生式的候选式插入圆点，则为 LR(0) 项目。
        • 对于开始符号 $S$，额外增加 $S' \to \bullet S$ 和 $S' \to S \bullet$。
        • 对于 $A \to \varepsilon$，改为 $A \to \bullet$。
        • 对于 $A \to a b$，改为 $A \to \bullet a b$、$A \to a \bullet b$、$A \to a b \bullet$。
        • 对于 $A \to B | C$，则分别改 $A \to B$ 和 $A \to C$。
      • $\bullet$ 用于表示这个候选式中，$\bullet$ 前面的部分已经在分析栈中，后面的部分还没有。
      • 项目的分类：
        • 接受项目：$S' \to S \bullet$，表示整体分析成功。
        • 规约项目：$A \to \alpha \bullet$，其中 $\alpha \ne S$。
          • 分析栈中是可归前缀，后缀就是句柄 $\alpha$，表示可以规约。
        • 移进项目：$A \to \alpha \bullet a \beta$，其中 $a \in V_T$。
          • 分析栈中是活前缀，后缀不是句柄，可以继续读 $a$，表示可以移进。
        • 待约项目：$A \to \alpha \bullet B \beta$，其中 $B \in V_N$。
          • 需要先规约后面的输入到 $B$，才能获得可归前缀 $\alpha B \beta$。
    • 构造 LR(0) 状态
      • 方法 1
        • 找出所有的项目后，给每个项目分配编号。
        • 构造 NFA，NFA 识别所有的活前缀：
          • 起始状态为 $S' \to \bullet S$，表示没有扫描和匹配任意的符号。
          • 接受状态为所有的规约项目对应的状态。
          • 如果存在 $A_i \to \alpha \bullet X \beta$ 和 $A_j \to \alpha X \bullet \beta$，则连边 $A_j \in \delta(A_i, X)$。
            • 这表示扫描符号 $X$ 可以转移状态。
          • 如果存在 $A_i \to \alpha \bullet X \beta$ 和 $X \to \bullet \delta$，则连边 $X \in \delta(A_i, \varepsilon)$。
            • 这表示不消费符号而先进入规约 $X$ 的状态。
        • 使用子集法确定化 NFA：
          • 得到的 DFA 的每个节点则为 LR(0) 项目的集合，称为项目集。
          • DFA 的节点集合称为项目集规范族。
      • 方法 2
        • 定义项目集闭包 $\operatorname{closure}(I)$：
          • $I \subseteq \operatorname{closure}(I)$。
          • 如果存在 $A_i \to \alpha \bullet X \beta \in \operatorname{closure}(I)$ 和 $X \to \bullet \delta$，则 $X \to \bullet \delta \in \operatorname{closure}(I)$。
            • 这与方法一 $X \in \delta(A_i, \varepsilon)$ 含义类似。
          • 项目集闭包也是项目集，$I$ 中的状态可以不需要消费符号而转移到 $\operatorname{closure}(I)$，类似于单向的“等价”。
        • 定义 $\operatorname{GO}(I, X)$ 为从 $I$ 中的项目消费 $X$ 可以到达的其他项目组成的项目集。
          • $\operatorname{GO}(I, X) = \operatorname{closure}(I')$。
          • 如果存在 $A_i \to \alpha \bullet X \beta \in I$ 和 $A_j \to \alpha X \bullet \beta$，则 $A_j \to \alpha X \bullet \beta \in I'$。
            • 类似方法 1 中的 $A_j \in \delta(A_i, X)$。
          • 把 $I$ 看作 DFA 的状态，则 $\operatorname{GO}(I, X)$ 就是 DFA 的状态转移函数。
        • 构造整个项目集规范族：
          • 从 $I = \{S' \to \bullet S\}$ 开始，计算 $\operatorname{closure}(I)$。
          • 对于所有的 $X$，计算 $\operatorname{GO}(I, X)$。
          • 重复上一步，用上一步得出的 $I$ 继续计算。
    • 构造 LR(0) 分析表
      • 对于当前状态/项目集 $I_i$：
        • 如果项目集为一个接受项目，则填写 $\operatorname{ACTION}(i, \#) = \text{accept}$。
        • 如果项目集为一个规约项目，则填写整行 $\operatorname{ACTION}(i, *) = r_t$，其中 $t$ 为对应的候选式编号。
        • 复制 $\operatorname{GO}$ 到 $\operatorname{ACTION}$ 和 $\operatorname{GOTO}$。
          • 对于终结符 $a$ 的状态转移 $\operatorname{GO}(I_i, a) = I_j$，填写 $\operatorname{ACTION}(i, a) = S_j$。
          • 对于非终结符 $X$ 的状态转移 $\operatorname{GO}(I_i, X) = I_j$，填写 $\operatorname{GOTO}(i, X) = j$。
      • LR(0) 中，规约项目、接受项目是互斥性的，可能存在以下冲突：
        • 移进-规约冲突
        • 规约-规约冲突
        • 接受-规约冲突
      • 如果存在冲突，则无法按照上面的过程构造分析表，文法也就不是 LR(0) 文法。
  • SLR(1)
    • 与 LR(0) 大致类似，但是在构造分析表时，对于规约项目的处理：
      • 设规约项目为 $A \to \alpha \bullet \in I_i$，仅对所有的 $c \in \operatorname{FOLLOW}(A)$ 填写 $\operatorname{ACTION}(i, c) = r_t$。
      • 项目集中可以存在多个规约项目，只要各自对应的 $\operatorname{FOLLOW}(*)$ 不交。
    • 项目冲突类别与 LR(0) 相同，冲突条件为 $\operatorname{FOLLOW}(*)$ 相交。
  • LR(1)
    • LR(1) 项目
      • LR(1) 项目由 LR(0) 项目和一个搜索符组成，记作 $[A \to \alpha, a]$。
        • $a \in \{ \# \} \cup V_T$。
        • 对于规约项目，只能在当前读入符号是 $a$ 时才可以规约。
      • 有效项目：若 $[A \to \alpha \bullet \beta, a]$ 对活前缀 $\gamma$ 有效，当且仅当：
        • 存在规范推导 $S \xRightarrow{*} \delta A \omega \xRightarrow{*} \delta \alpha \beta \omega$，其中 $\gamma = \delta \alpha$，
        • $a \in \operatorname{FIRST}(\omega)$ 或 $\omega = \varepsilon$ 时 $a = \#$。
      • LR(1) 项目包括了搜索符，在规约时更加精确，可以完全避免规约冲突。
    • 构造 LR(1) 状态机
      • 定义项目集闭包 $\operatorname{closure}(I)$ 为：
        • $I \subseteq \operatorname{closure}(I)$。
        • 如果存在 $[A_i \to \alpha \bullet X \beta, a] \in \operatorname{closure}(I)$ 和 $[X \to \bullet \delta, b]$ 且 $b \in \operatorname{FIRST}(X \beta)$，则 $[X \to \bullet \delta, b] \in \operatorname{closure}(I)$。
          • $A_i \to \alpha \bullet X \beta$ 依赖 $X \to \bullet \delta$ 的规约，所以后者的搜索符需要在 $X \beta$ 的最前面。
      • 定义 $\operatorname{GO}(I, X) = \operatorname{closure}(I')$
        • 如果存在 $[A_i \to \alpha \bullet X \beta, a] \in I$ 和 $[A_j \to \alpha X \bullet \beta, a]$，则 $[A_j \to \alpha X \bullet \beta, a] \in I'$。
          • $\operatorname{GO}$ 不涉及规约，所以搜索符不变。
      • 构造 LR(1) 状态机的方法与 LR(0) 一样，区别只有 $\operatorname{closure}(I)$ 和 $\operatorname{GO}(I, X)$。
    • 构造 LR(1) 分析表
      • 考虑每个项目集 $I_i$ 中的每一个项目：
        • 如果是接受项目，同 LR(0)。
        • 如果是规约项目 $[A_j \to \alpha \bullet, a]$，填写 $\operatorname{ACTION}(I_i, a) = r_t$。
          • 仅根据搜索符 $a$ 精确填写第 $a$ 列。
        • 同 LR(0) 复制 $\operatorname{GO}$ 到 $\operatorname{ACTION}$ 和 $\operatorname{GOTO}$。
      • LR(1) 不存在冲突。
  • LALR(1)
    • LR(1) 中的两个项目集如果核心项目相同，则为同心项目集。
    • LALR(1) 合并所有的同心项目集，搜索符取所有的并集。
    • LALR(1) 仅可能存在规约-规约冲突，其他特性继承 LR(1)。