编译原理

第四章 语法分析

2020-02-25 10:00 CST
2020-03-17 13:36 CST
CC BY-NC 4.0

语法分析器

程序设计语言构造的描述

程序设计语言构造的语法可使用上下文无关文法（CFG）或BNF表示法来描述

  • 给出精确易懂的语法规则
  • 自动构造出某种类型的文法的语法分析器
  • 指出了语言的结构，有助于进一步的语义处理/代码分析
  • 在这里按tab缩进
    • 按backspace回退
    • 按下回车结束列表
  • 缩进或结束列表操作较为麻烦

语法分析器的作用

基本作用：

  • 确认词法分析的序列是否由语言的文法生成
  • 对于语法错误的程序，报告错误信息
  • 对于语法正确的信息，生成语法分析树

语法分析器的分类

  • 通用语法分析器（更复杂，效率低下）
  • 自顶向下语法分析器（处理LL文法）：从根部开始构造语法分析树
  • 自底向上语法分析器（处理LR文法）：从叶子开始构造语法分析树

LL分析比LR分析略弱，LR分析能够处理更多文法；两种语法分析器总是从左到右、逐个扫描词法单元。

上下文无关文法

一个CFG包含四个部分：

  • 终结符号：组成串的基本符号（词法单元的名字）
  • 非终结符号：表示串的集合的语法变量（如程序语言中的语句$stmt$）
  • 开始符号：某个被指定的非终结符号
  • 产生式：描述将终结符号和非终结符号组成串的方法
    • 形式：头部$\rightarrow$体部
    • 头部是一个非终结符号，体部是一个符号串

E.g. 简单算术表达式的文法：

  • 终结符号：id、+、-、*、/、(、)
  • 非终结符号：$exp$、$term$、$factor$
  • 开始符号：$exp$
  • 产生式：
    • $exp \rightarrow exp + term$
    • $exp \rightarrow exp - term$
    • $exp \rightarrow term$
    • $term \rightarrow term * factor$（乘除法的优先级更高）
    • $term \rightarrow term / factor$
    • $term \rightarrow factor$
    • $factor \rightarrow (expression)$（支持括号嵌套）
    • $factor \rightarrow id$

推导

将待处理的串中的某个非终结符号替换为这个非终结符号的某个产生式的体；从开始符号出发，不断进行上面的替换，就可以得到文法的不同句型。

E.g. $exp \Rightarrow exp + term \Rightarrow term + factor \Rightarrow \dots \Rightarrow (id * id) + id$

推导的正式定义：

  • 如果$A \rightarrow \gamma$是一个产生式，那么$\alpha A \gamma \Rightarrow \alpha \gamma \beta$
  • 最左推导：$\alpha$中不包含非终结符号，记作$\overset{*}{\underset{lm}{\Longrightarrow}}$
  • 最右推导：$\beta$中不包含非终结符号，记作$\overset{*}{\underset{rm}{\Longrightarrow}}$
  • 经过零步或多步推导出：$\overset{*}{\Longrightarrow}$
  • 经过一步或多步推导出：$\overset{+}{\Longrightarrow}$

句型/句子/语言

句型（Sentential form）：

  • 如果$S \overset{*}{\Longrightarrow} \alpha$，则$\alpha$就是文法$S$的句型
  • 可能既包含非终结符号，又包含终结符号，也可以是空串

句子（Sentence）：不包含非终结符号的句型

语言：

  • 文法$G$的语言就是$G$的句子的结合，记为$L(G)$
  • $w$在$L(G)$中当且仅当$w$是$G$的句子，即$S \overset{*}{\Longrightarrow} w$

语法分析树

  • 推导的图形表示形式
    • 根结点的标号是文法的开始符号
    • 每个叶子结点的标号是非终结符号、终结符号或$\varepsilon$
    • 每个内部结点的标号是非终结符号
    • 每个内部结点表示某个产生式的一次应用
  • 树的叶子组成的序列是跟的文法符号的一个句型
  • 一棵语法分析树可对应多个推导序列，但只有唯一的最左推导和最右推导

二义性（Ambiguity）：如果一个文法可以为某个句子生成多棵语法分析树，这个文法就是二义的。

E.g. $exp \Rightarrow \text{id} + \text{id} * \text{id}$有多棵语法分析树

程序设计语言的文法通常是无二义的，否则就会导致一个程序有多种“正确”的解释。

词法分析和语法分析的比较

阶段 输入 输出 描述体系
词法分析 源程序符号串 词法单元序列 正则表达式
语法分析 词法单元序列 语法分析树 上下文无关语法

上下文无关文法和正则表达式

上下文无关文法比正则表达式的能力更强

  • 所有的正则语言都可以使用文法描述
  • 但有一些用文法描述的语言不能用正则表达式描述
    • 存在无法使用正则表达式（等价于DFA）描述的语言（反例）
    • 任何正则语言（等价于NFA）都可以用文法描述（构造）

E.g. $S \rightarrow aSb$，即$a^nb^n$，对于$k$个状态的DFA，可令$n=k+1$，则该DFA无法识别该语言（有穷DFA不能计数）

设计文法

在进行高效的语法分析之前，需要对文法做一下处理：

  • 消除二义性
  • 消除左递归：$A \overset{+}{\Longrightarrow} A\alpha$
  • 提取左公因子

二义性的消除

一些二义性文法可被改成等价的无二义性的文法

E.g. $\textbf{if } stmt \textbf{ then } stmt \textbf{ else } stmt$可以要求$\textbf{else}$和最近未匹配的$\textbf{then}$匹配，即要求$\textbf{then}$和$\textbf{else}$之间出现的语句是匹配好的。

左递归的消除

左递归的的定义：如果一个文法中有非终结符号$A$使得$A \overset{+}{\Longrightarrow} A\alpha$，那么这个文法就是左递归的。

自顶向下的语法分析技术不能处理左递归的情况，因此需要消除左递归；但是自底向上的技术可以处理左递归。

立即左递归（规则左递归）：文法中存在$A \overset{+}{\Longrightarrow} A\alpha$的产生式。

立即左递归的消除：$A \rightarrow A\alpha_1|\ \dots\ |\ A\alpha_m\ |\ \beta_1\ |\ \dots\ |\ \beta_n$变为

$$\begin{cases}A \rightarrow \beta A' \\ A' \rightarrow \alpha A'\ |\ \varepsilon \end{cases}$$

消除多步左递归：

  • 输入：没有环和$\varepsilon$产生式的文法$G$
  • 输出：等价的无左递归的文法
  • 步骤：
    • 将非终结符号排序为$A_1, A_2, \dots$，满足前面的产生式中不包含后面的非终结符号
    • $i := 1 \rightarrow n$
      • $j := 1 \rightarrow i-1$
        • 将$A_i \rightarrow A_j \gamma$替换为$A_i \rightarrow \delta_1 \gamma\ |\ \delta_2 \gamma\ |\ \dots$
      • 消除$A_i$中的立即左递归

预测分析法

  • 试图从开始符号推导出输入符号串
  • 每次为最左边的非终结符号选择适当的产生式
    • 通过查看下一个输入符号来选择
    • 有多个可能的产生式时则无能为力

自顶向下的语法分析

  • 为输入串构造语法分析树
    • 从分析树的根节点开始，按照先根顺序，深度优先地创建各个节点（最左推导）
  • 基本步骤
    • 确定句型中最左边的非终结符号应用哪个产生式
    • 对该产生式和输入符号进行匹配

递归下降的语法分析

  • 每个非终结符号对应于一个过程，该过程负责扫描此非终结符号对应的结构
  • 程序执行从开始符号对应的过程开始，当扫描整个输入串时成功完成
  • 步骤：
    • 选择一个$A$产生式$A \rightarrow X_1 X_2 \dots X_k$
    • 对于每一个$X_i$：
      • 如果$X_i$是非终结符号，则调用对应的过程；
      • 如果$X_i$等于当前的输入符号，则读入下一个输入符号；
      • 否则（不匹配）抛出错误。

如果没有足够的信息来唯一确定可能的产生式，那么分析过程就会产生回溯。

  • 回溯需要来回扫描，甚至撤销已完成的语义动作（如代码生成）
  • 是否有可能是合法的句子但却无法分析？（Completeness？）

FIRST和FOLLOW

  • 如果当前句型是$x A \beta$，而输入是$xa \dots$，那么选择产生式$A \rightarrow a$的必要条件是下列之一：
    • $\alpha \overset{*}{\Rightarrow} a \dots$
    • $\alpha \overset{*}{\Rightarrow} \varepsilon$，且$\beta$以$a$开头
  • 如果按照这两个条件选择时能够保证唯一性，那么就可以避免回溯。

$\texttt{FIRST}(\alpha)$：

  • 可以从$\alpha$推导得到的串的首符号的集合
  • 如果$\alpha \overset{*}{\Longrightarrow} \varepsilon$，那么$\varepsilon$也在$\texttt{FIRST}(\alpha)$中

如何计算$\texttt{FIRST}(X_1 X_2 \dots X_n)$？

  • 加入$\texttt{FIRST}(X_1)$中所有非$\varepsilon$符号
  • 若$\varepsilon \in \texttt{FIRST}(X_i)$，加入$\texttt{FIRST}(X_{i+1})$中所有非$\varepsilon$符号
  • 若$\forall i, \varepsilon \in \texttt{FIRST}(X_i)$，则也加入$\varepsilon$

$\texttt{FOLLOW}(A)$：

  • 可能在某些句型中紧跟在$A$右边的终结符号的集合
  • 如$S \rightarrow \alpha A a \beta$，终结符号$a \in \texttt{FOLLOW}(A)$

$\texttt{FOLLOW}$函数的意义：如果$A \rightarrow \alpha$，当$\alpha \overset{*}{\Longrightarrow} \varepsilon$时，$\texttt{FOLLOW}(A)$可以帮助我们选择恰当的表达式。

如何计算$\texttt{FOLLOW}(S)$？

  • 将右端结束标记 $ \$ $ 加入 $\texttt{FOLLOW}(S)$中
  • 按下面规则不断迭代，直到所有的$\texttt{FOLLOW}$集合都不再增长为止：
    • 如果存在产生式$A \rightarrow \alpha B \beta$，那么$\texttt{FIRST}(\beta)$中所有非$\varepsilon$的符号都加入$\texttt{FOLLOW}(B)$中
    • 如果存在产生式$A \rightarrow \alpha B$，或者$A \rightarrow \alpha B \beta$且$\varepsilon \in \texttt{FIRST}(\beta)$，那么$\texttt{FOLLOW}(A)$中所有符号都加入$\texttt{FOLLOW}(B)$中

LL(1)文法

  • 第一个L：从左到右分析
  • 第二个L：最左推导
  • (1)：往前看1个符号决定产生式

定义：对文法的任意两个产生式$A \rightarrow \alpha\ |\ \beta$

  • 不存在终结符号$a$使得$\alpha$和$\beta$都可推导出以$a$开头的串
  • $\alpha$和$\beta$最多只有一个可推导出空串
  • 如果$\beta$可推导出空串，那么$\alpha$不能推导出以$\texttt{FOLLOW}(A)$中任何终结符号开头的串

以上定义等价于：

  • $\texttt{FIRST}(\alpha) \cap \texttt{FIRST}(\beta) = \emptyset$
  • 如果$\varepsilon \in \texttt{FIRST}(\beta)$，那么$\texttt{FIRST}(\alpha) \cap \texttt{FOLLOW}(A) = \emptyset$，反之亦然

预测分析表构造算法

  • 输入：文法$G$
  • 输出：预测分析表$M$
  • 方法：
    • 对于文法$G$中的每个产生式$A \rightarrow \alpha$
      • 对于$\texttt{FIRST}(\alpha)$中的每个终结符号$a$，将$A \rightarrow \alpha$加入到$M[A, a]$中
      • 如果$\varepsilon \in \texttt{FIRST}(\alpha)$，那么对于$\texttt{FOLLOW}(A)$中的每个符号$b$，将$A \rightarrow \alpha$也加入到$M[A, b]$中
    • 最后在所有的空白条目中填入$\texttt{error}$

非递归的预测分析

在自顶向下分析的过程中，我们总是

  • 匹配句型中左边的所有终结符号
  • 对于最左边的非终结符号，选择适当的产生式展开
  • 匹配成功的终结符号不会再被考虑
  • 只在最左端进行分析，可以使用栈保存符号

分析时的处理过程：

  • 初始化时，栈中仅包含开始符号$S$$
  • 如果栈顶元素是终结符号，那么产生匹配
  • 如果栈顶元素是非终结符号
    • 使用预测分析表选择合适的产生式
    • 在栈顶用产生式右部替换产生式左部（倒序压入）

自底向上的语法分析

  • 为一个输入串构造语法分析树的过程
  • 从叶子开始，向上到达根节点
  • 重要的自底向上语法分析的通用框架：移入-规约（shift-reduce）
  • 简单LR技术（SLR）、LR技术

规约

  • 自底向上的语法分析过程可以看成是从串$w$规约为文法开始符号$S$的过程
  • 一个与某产生式体相匹配的特定子串被替换为该产生式头部的非终结符号

句柄

对输入从左到右扫描，并进行自底向上的语法分析，实际可以反向构造出一个最右推导

句柄：

  • 最右句型中和某个产生式体相匹配的子串，对它的规约代表了该最右句型的最右推导的最后一步
  • 正式定义：如果$S \overset{*}{\underset{rm}{\Longrightarrow}} \alpha A w \underset{rm}{\Longrightarrow} \alpha \beta w$，那么紧跟$\alpha$之后的$\beta$是$A \rightarrow \beta$的一个句柄

在一个最右句型中，句柄右边只有终结符号；如果文法是无二义性的，那么每个句型有且只有一个句柄。

移入-规约分析技术

  • 使用一个栈来保存规约/扫描移入的文法符号
  • 栈中符号（自底向上）和待扫描的符号组成了一个最右句型
  • 开始时刻：栈中只包含$ \$ $，而输入为$w \$ $
  • 结束时刻：栈中为$ S\$ $，而输入为$ \$ $
  • 在分析过程中，不断移入符号，并在识别到句柄时进行规约

主要分析动作：

  • 移入：将下一个输入符号移入到栈项
  • 规约：将句柄规约为相应的非终结符号
    • 句柄总是在栈顶
    • 具体操作时弹出句柄，压入被规约到的非终结符号
  • 接受：宣布分析过程成功完成
  • 报错：发现语法错误，调用错误恢复子程序

移入-规约分析中的冲突：

  • 移入-规约冲突：不知道是否该进行规约还是移入更多符号
  • 规约-规约冲突：不知道按照什么产生式进行规约

LR语法分析技术

LR(k)的语法分析概念

  • L表示最左扫描，R表示反向构造出最右推导
  • $k$表示最多向前看$k$个符号

LR语法分析器的优点：

  • 由表格驱动
  • 对于几乎所有的程序设计语言，只要写出CFG，就能够构造出识别该语言的LR语法分析器
  • 最通用的无回溯移入-规约分析技术
  • 能分析的文法比LL(k)文法更多

项：文法的一个产生式加上在其中某处的一个点

  • $A \rightarrow \alpha \cdot \beta$表示已经扫描/规约到了$\alpha$，并期望在接下来的输入中经过扫描/规约得到$\beta$，然后把$\alpha \beta$规约到$A$
  • 如果$\beta$为空，表示我们可以把$\alpha$规约到$A$

LR(0)项集规范族的构造

三个相关定义：

  • 增广文法
  • 项集闭包$\texttt{CLOSURE}$
  • $\texttt{GOTO}$函数

增广文法：

  • $G$的增广文法$G'$是在$G$中增加新开始符号$S'$，并加入产生式$S' \rightarrow S$而得到的
  • 显然$G'$和$G$接受相同的语言，且按照$S' \rightarrow S$进行规约实际上就表示已经将输入的符号串规约成开始符号

项集闭包$\texttt{CLOSURE}$：

  • 如果$I$是文法$G$的一个项集，$\texttt{CLOSURE}(I)$就是根据下列两条规则从$I$构造得到的项集：
    • 将$I$的各项加入到$\texttt{CLOSURE}(I)$中
    • 如果$A \rightarrow \alpha \cdot B \beta$在$\texttt{CLOSURE}(I)$中，而$B \rightarrow \gamma$是一个产生式，且项$B \rightarrow \cdot \gamma$不在$\texttt{CLOSURE}(I)$中，就讲该项加入其中
    • 不断应用以上规则直到没有新项可加入

项集闭包的含义：希望看到由$B \beta$推导出的串，要先看到由$B$推导出的串，因此加上$B$的各个产生式对应的串

$\texttt{GOTO}$函数：$I$是一个项集，$X$是一个文法符号，则$\texttt{GOTO}(I, X)$定义为$I$中所有形如$[A \rightarrow \alpha \cdot X \beta]$的项所对应的$[A \rightarrow \alpha X \cdot \beta]$的项的集合的闭包

求LR(0)项集规范族的方法：从初始项集$\texttt{CLOSURE}(\lbrace S' \rightarrow \cdot S \rbrace)$开始，不断计算各种可能的后继，直到生成所有的项集。

LR(0)自动机的构造

  • 规范LR(0)项集族中的每个项集对应于LR(0)自动机的一个状态
  • 如果$\texttt{GOTO}(I, X) = J$，则从$I$到$J$有一个标号为$X$的转换
  • 开始状态为$\texttt{CLOSURE}(\lbrace S' \rightarrow \cdot S \rbrace)$对应的项集

LR(0)自动机的作用

假设文法符号串$\gamma$使LR(0)自动机从开始状态运行到状态$j$

  • 如果$j$中存在项$A \rightarrow \alpha \cdot$，那么
    • 在$\gamma$之后添加一些终结符号可以得到一个最右句型
    • $\alpha$是$\gamma$的后缀，且是该句型的句柄（对应于$A \rightarrow \alpha$）
    • 表示可能找到了当前最右句型的句柄，可以规约
  • 如果$j$中存在项$B \rightarrow \alpha \cdot X \beta$，那么
    • 在$\gamma$之后添加$X \beta$和一些终结符号可以得到一个最右句型
    • 该句型中$\alpha X \beta$是句柄，但还没有找到，需要继续移入

LR语法分析器的结构

  • 栈中存放状态序列，可求出对应的符号序列
  • 分析程序根据栈顶状态和当前输入，通过分析表确定下一步动作

LR语法分析表的结构：

  • 动作$\texttt{ACTION}[i][a]$：$i$是状态，$a$是下一个符号
    • 移入$j$：将新状态$j$压入栈，同时移入$a$
    • 规约$A \rightarrow \beta$：把栈顶的$\beta$规约为$A$（并根据$\texttt{GOTO}$表项压入新状态）
    • 接受：接受输入，完成分析
    • 报错：在输入中发现语法错误
  • 转换$\texttt{GOTO}[i][A]$：
    • 如果$\texttt{GOTO}(I_i, A) = I_j$，那么表项$\texttt{GOTO}[i][A] = j$

LR语法分析器的格局包含了栈中内容和余下输入：

  • $s_0 s_1 \dots s_m$：栈中的内容（除$s_0$的每一个状态对应一个文法符号）
  • $a_i a_{i+1} \dots a_n \$$：余下的输入

在任何时候栈对应的符号串和剩下的输入组成一个最右句型。

LR语法分析器的行为：对于当前格局，查询当前栈顶状态和下一个符号对应的动作：移入、规约、接受或拒绝。

SLR语法分析表的构造

以LR(0)自动机为基础的SLR语法分析表构造算法：

  • 构造增广文法$G'$的LR(0)项集规范族
  • 状态$i$对应项集$I_i$，相关的$\texttt{ACTION}/\texttt{GOTO}$表条目如下：
    • $[A \rightarrow \alpha \cdot a \beta] \in I_i$且$\texttt{GOTO}(I_i, a) = I_j$则$\texttt{ACTION}[i][a] = sj$（移入）
    • $[A \rightarrow a \cdot] \in I_i$，则对$\texttt{FOLLOW}(a)$中的所有$a$，$\texttt{ACTION}[i][a] = r\alpha$（规约）
    • 如果$[S' \rightarrow S \cdot] \in I_i$，则$\texttt{ACTION}[i][\$] = acc$（接受）
    • 如果$\texttt{GOTO}(I_i, A) = I_j$，则$\texttt{GOTO}[i][A] = j$
  • 空白的条目设置为 error

如果SLR分析表没有冲突，该文法就是SLR的。

SLR语法分析器的弱点

SLR技术解决冲突的办法：

  • 项集中包含$[A \rightarrow \alpha \cdot]$时，按照$A \rightarrow \alpha$进行规约的条件是下一个符号$\alpha$可以在某个句型中跟在$A$之后
  • 假设此时栈中的符号串为$\beta\alpha$
    • 如果$\beta A a$不是任何最右句型的前缀，那么即使$a$在某个句型中跟在$A$之后，仍不应该按照$A \rightarrow a$规约
    • 进行规约的条件更加严格可以降低冲突的可能性
  • $[A \rightarrow \alpha \cdot]$出现在项集中的条件
    • 首先$[A \rightarrow \cdot \alpha]$出现在某个项集中，然后逐步读入/规约到$\alpha$中的符号，点不断后移，到达末端
    • 而$[A \rightarrow \cdot \alpha]$出现的条件是$B \rightarrow \beta \cdot A \gamma$出现在项中
    • 期望首先按照$A \rightarrow \alpha$规约，然后将$B \rightarrow \beta \cdot A \gamma$中的点移动到$A$之后
    • 而按照$A \rightarrow \alpha$规约时要求下一个输入符号是$\gamma$的第一个符号，但是从LR(0)项集中不能确定这个信息

更强大的LR语法分析器

  • 规范LR方法（SLR方法）
    • 添加项时把期望的向前看符号也加入项中（LR(1)项集）
    • 可以充分利用向前看符号，但是状态很多
  • 向前看LR（LALR方法）
    • 基于LR(0)项集族，每个LR(0)项都带有向前看符号
    • 分析能力强于SLR方法，且分析表和SLR表一样大
    • LALR已经可以处理大部分的程序设计语言

LR(1)项

形式：$[A \rightarrow \alpha \cdot \beta, a]$

  • $a$称为向前看符号，可以是终结符号或结束符号
  • $a$表示如果将来要按照$A \rightarrow \alpha \beta$进行规约，规约时的下一个输入符号必须是$a$
  • 当$\beta$非空时，移入动作不考虑$a$，$a$传递到下一状态

LR(1)项集的构造

与LR(0)项集族类似，但

  • 在$\texttt{CLOSURE}$中，当由项$[A \rightarrow \alpha \cdot B \beta, a]$生成新项$[B \rightarrow \cdot \theta, b]$时，$b$必须在$\texttt{FIRST}(\beta a)$中
  • 对LR(1)项集中的任何项$[A \rightarrow \alpha \cdot B \beta, a]$，总有：$a \in \texttt{FOLLOW}(A)$

LALR分析技术

核心思想：

  • 寻找具有相同核心的LR(1)项集，并把它们合并成为一个项集
  • 一个LR(1)项集的核心是一个LR(0)项集
  • $\texttt{GOTO}(I,X)$的核心只由$I$的核心决定，因此被合并项集的$\texttt{GOTO}$目标也可以合并

合并LR(1)分析表时不会产生移入/规约冲突，只会产生规约/规约冲突。

技术本质：通过对同核心项集进行合并

  • 使得分析表保持了LR(1)项中的向前看符号信息
  • 使状态数减少到了与SLR分析表一样多

二义性文法

  • 二义性文法都不是LR的
  • 某些二义性文法是有用的
    • 简洁地描述某些结构
    • 隔离某些语法结构，对其进行特殊处理
  • 对于某些二义性文法
    • 通过消除二义性保证每个句子只有一棵语法分析树
    • 在LR分析器中实现分析规则

二义性文法的优点：

  • 容易修改运算符的优先级和结合性
  • 简洁：如果有多个优先级，无二义性的文法会引入太多的非终结符号
  • 高效：无需处理引入新符号导致的过多的规约

语法错误的处理

程序中可能存在不同层次的错误：

  • 词法错误：终结符拼写错误
  • 语法错误：终结符的顺序不符合文法规约
  • 语义错误：变量在使用中出现使用错误
  • 逻辑错误

语法分析器中错误处理程序的设计目标：

  • 准确的报告出现的错误并指出错误的位置
  • 能从当前错误中恢复，以继续检测后面的错误

语法分析中的错误恢复

  • 当预测分析器报错时，表示输入的串不是句子
  • 希望预测分析器能够进行恢复处理后继续语法分析过程，以便一次找到更多的语法错误
  • 可能恢复的并不成功，之后找到的语法错误是假的

两类错误恢复方法：

  • 恐慌模式：跳过当前的语法结构
  • 短语层次的恢复：对错误写特别的恢复程序

恐慌模式

基本思想：语法分析器忽略输入中的一些符号，直到出现由设计者选定的某个同步词法单元。

  • 假装已经找到了正确的句型，继续进行语法分析；
  • 同步词法单元就是出错的程序结构结束的标志。

同步词法单元的确定

文法符号$A$的同步集合的启发式规则：

$A$是非终结符号：

  • 将$\texttt{FOLLOW}(A)$中的所有符号放入$A$的同步集合中
  • 将高层次非终结符号对应串的开始符号加入到较低层次非终结符号的同步集合（如每个语句的开始符号，直接丢弃整个语句）
  • 将$\texttt{FIRST}(A)$中的符号加入到$A$的同步集合中（代表前面的符号可能是多余的符号）

$A$是终结符号：

  • 直接弹出该符号，并发出消息称已经插入了这个终结符号

LR语法分析中的错误恢复

  • 查询$\texttt{ACTION}$表时可能发现报错条目：不可能存在终结符号串使得读入后变成一个最右句型
  • 错误恢复策略：
    • 从栈顶向下扫描，找到状态$s$，$s$有一个对应于某个非终结符号$A$的$\texttt{GOTO}$目标（$s$之上的状态被丢弃）
    • 从输入中丢弃一些符号，直到一个可以跟在$A$之后的符号$b$（不丢弃$b$），并将$\texttt{GOTO}[s][A]$压栈，继续进行分析