Parsing⚓︎

• 语法(syntax)：词语组合成短语、从句或句子的方式
• 语法分析(syntax analysis)：分析程序短语结构
  • 分析器(parser) 基于语法构建，并从记号流中提取出抽象语法

为何需要语法分析？

问题 1 问题 2

如图所示，这段程序虽然词法上没错，但有很多语法错误。

该表达式可以根据分析树而非记号流来正确求值。

Context-Free Grammar⚓︎

并非所有记号串都是程序。分析器必须区分有效和无效的记号串。所以我们需要一种能描述有效记号串的语言和一种区分有效和无效的记号串的方法。

上一章介绍的正则语言是一种最弱的形式语言，它无法表达递归等复杂结构（但它们又是编程语言中常见的结构）。因此我们引入一种更强大的形式语言，即上下文无关文法(context-free grammar, CFG)。它由以下部分构成：

• 一组终结符(terminals) \(T\)：来自字母表的符号（词法记号）
• 一组非终结符(non-terminals) \(N\)
• 一个起始符号 \(S \in N\)
• 一组产生式(productions)（规则(rules)）：\(X \rightarrow Y_1 Y_2 \dots Y_k\)（表示用 \(Y_1 Y_2 \dots Y_k\) 替换 \(X\)），其中 \(X \in N, Y_i \in N \cup T \cup \{\varepsilon\}\)

基于 CFG 推导字符串的步骤：

1. 从一个仅包含起始符号 \(S\) 的字符串开始
2. 将字符串中的任意非终结符 \(X\) 替换为某产生式 \(X \rightarrow Y_1 \dots Y_k\) 的右侧部分
3. 重复步骤 2，直到字符串中只包含终结符

更形式化地，对于每一步：

令 \(G\) 为一个上下文无关文法，起始符号为 \(S\)。那么 \(G\) 的语言 \(L(G)\) 定义为：

• \(\color{cornflowerblue}{*}\) 表示 0 步或多步推导：

  \[ \begin{aligned} S \to \dots \to \dots \to \alpha_0 \to \color{cornflowerblue}{\alpha_1 \to} & \color{cornflowerblue}{\alpha_2 \to \dots \to \alpha_n} \\ & \color{cornflowerblue}{\downarrow} \\ \color{cornflowerblue}{\alpha_0} & \color{cornflowerblue}{\xrightarrow{*} \alpha_n} \end{aligned} \]

• 一旦生成，终结符将持续存在

• 在分析过程中，终结符是语言的词法记号

例子

Derivations⚓︎

现在，「寻找一种区分有效和无效记号串的方法」这一问题被转换为「确定字符串是否属于 CFG 的语言」。这里我们就要用到推导(derivation)：从起始符号 \(S\) 开始，然后反复将任意非终结符替换为其右侧的任一产生式。因此，一个字符串属于 \(L(G)\)，当且仅当可以从起始符号 \(S\) 推导出该字符串。

例子

可以通过树来表示推导：

• 起始符号对应根节点
• 对于产生式 \(X \rightarrow Y_1 \dots Y_k\)，为节点 \(X\) 添加子节点 \(Y_1, \dots, Y_k\)

上述例子是一种最左推导(left-most derivation)，即每一步都替换最左侧非终结符的推导。对应地也有最右推导(right-most derivation) 的概念。（在不考虑二义性问题的情况下，）两种推导能得到相同的分析树。

也存在某些推导既不是最左推导，也不是最右推导，比如 E * E + E（展开划线的非终结符）。

Parse Tree⚓︎

上面画的树被称为分析树(parse tree)。

• 叶节点为终结符
• 中间节点为非终结符
• 叶节点的中序遍历便是原输入
• 但分析树能展示操作的关联性（这一关联性无法通过输入字符串看出）

要知道字符串 \(s\) 是否属于 \(L(G)\)，需为 \(s\) 构建一个分析树，这样便能自动证明 \(s \in L(G)\)。

推导过程定义了分析树，但同一棵分析树可能对应多种推导方式。因此最左推导和最右推导在语法分析器实现中至关重要。

Ambiguity⚓︎

例子

如果一个语法能够通过两种不同的分析树推导出同一个字符串，那么它就是有二义的(ambiguous)。由于编译器是利用分析树来推导语义的，因此二义语法会阻碍编译的顺利进行（即导致程序的不良定义）。我们需要解决二义性问题！

最直接的方法是将二义语法转换为非二义语法。还是以上面的例子为例，我们需要：

• 优先级(precedence)：* 比 + 的优先级更高
• 左结合(left-association)：每个运算符和左侧结合，比如 1 - 2 - 3 应视为 (1 - 2) - 3 而非 1 - (2 - 3)

具体来说，我们需引入新的非终结符，以强制某些产生式晚于其他产生式被使用。

例子

有些语言具有二义语法，但没有无二义语法，这类语言作为编程语言时可能会存在问题。

EOF Maker⚓︎

我们用符号 \(\$\) 表示 EOF（文件结束 (end of file)）。为了表明 \(\$\) 必须出现在一个完整的 \(S\)- 短语之后，我们添加一个新的起始符号 \(S'\) 和一个新的产生式 \(S' \rightarrow S\$\)。

Top-Down Parsing⚓︎

在编译器中分析所有 CFG 的成本很高，因为用于分析所有 CFG 的算法开销很大（有时编译时间的三分之一就耗费在分析阶段上）。不过编译器开发者们已针对构建高效编程语言所需的特定类型的 CFG，开发出专门的分析算法：递归下降分析(recursive descent parsing)。

• 自顶向下分析，预测分析
• 简单易实现，可手动编码完成
• 能处理多数但非全部 CFG 类型
  • 适用于 LL(1) 文法（从左到右扫描（L），最左推导（L），单符号前瞻匹配（1））

其中自顶向下分析(top-down parsing) 中，分析树是自顶向下（从左到右）构建的。

例子

接下来为该语法编写一个递归下降分析器。关键思路是：

• 每个非终结符对应一个递归函数 -> 调用此函数以匹配该非终结符
• 每条产生式成为函数中的一个子句

enum token {IF, THEN, ELSE, BEGIN, END, PRINT, SEMI, NUM, EQ};

// lexer
extern enum token getToken(void);

// get a token by calling the lexer
enum token tok;
void advance() { tok = getToken(); } 

// consume the token and get the next one
void eat(enum token t) {
    if (tok == t) 
        advance();
    else
        error();
}

void S(void) {
    switch (tok) { 
        case IF: 
            eat(IF); 
            E(); 
            eat(THEN); 
            S(); 
            eat(ELSE); 
            S(); 
            break; 
        case BEGIN: 
            eat(BEGIN); 
            S(); 
            L(); 
            break; 
        case PRINT: 
            eat(PRINT); 
            E(); 
            break; 
        default: 
            error(); 
    }
}
void L(void) {
    switch(tok) {
        case END: 
            eat(END); 
            break;
        case SEMI: 
            eat(SEMI); 
            S(); 
            L(); 
            break;
        default: 
            error(); 
    }
} 
void E(void) {
    eat(NUM); 
    eat(EQ); 
    eat(NUM); 
}

问题

这只能处理特殊情况：对于语法中的每个非终结符，其产生式右侧的首符号 \(Y_1\) 是不同的终结符。对于下面这种语法，上面的方法就不管用了。

Predictive Parsing⚓︎

预测解析(predictive parsing) 仅适用于那些每个子表达式的第一个终结符能提供足够信息来选择使用哪个产生式的文法。

First and Follow Sets⚓︎

我们先来定义两个集合：

• \(\text{FIRST}(\gamma)\)：若 \(\gamma \rightarrow^* t \beta\)，则 \(t \in \text{First}(\gamma)\)（即 \(\gamma\) 可以在推导的首位生成一个终结符 \(t\)）

  • 含义：作为由 \(\gamma\) 推导出的字符串的开头的所有终结符的集合

• \(\text{FOLLOW}(X)\)：若 \(S \rightarrow^* \beta Xt \delta\)，则 \(t \in \text{Follow}(X)\)

  • 含义：紧跟在 \(X\) 后的终结符的集合
    • 如果存在包含 \(Xt\) 的任何推导，那么 \(t \in \text{FOLLOW}(X)\)
    • 这种情况可能在推导包含 \(XYZt\)（其中 \(Y\) 和 \(Z\) 都推导出空串 \(\varepsilon\)）时发生

考虑非终结符 \(X\) 和产生式 \(X \rightarrow \gamma\)，第一个可能的终结符 \(t\) 为：

• 任何来自 \(\text{First}(\gamma)\) 的记号
• 任何来自 \(\text{Follow}(X)\) 的记号若 \(\gamma \rightarrow^* \varepsilon\)

现在给出 \(\text{FIRST}(X)\) 和 \(\text{FOLLOW}(X)\) 的归纳定义：

另外再定义一个可空集合(nullable sets)：\(\text{Nullable}(X) = \text{True if } X \rightarrow^* \varepsilon\)。可通过类似 \(\varepsilon\)- 闭包的迭代方法计算：

for each symbol X:
    Nullable(X) = False
repeat
    for each production X -> Y1 Y2 ... Yk:
        if Nullable(Yi) = True for all 1 <= i <= k:
            Nullable(X) = True
until Nullable did not change in this iteration

例子

为了解每个产生式的第一个可能的终结符，我们需要计算 Nullable, First 和 Follow 这三个集合。

注：\(Y \rightarrow\) 其实是 \(Y \rightarrow \varepsilon\)，但好像没打印出来。

NullableFirstFollow

完整的算法如下：

Predictive Parsing Tables⚓︎

下一步就来构建分析表。其中 \(X\) 行 \(T\) 列表示分析器在函数 \(X\) 中根据下一个记号 \(T\) 应执行哪个子句，规则为：若 \(T \in \text{First}(\gamma)\)，或者 \(\gamma\) 是可空的且 \(T \in \text{Follow}(X)\)，那么将 \((X \rightarrow \gamma)\) 放在 \(X\) 行 \(T\) 列。

例子

• 如果预测表中存在空的单元格，说明出现了语法错误
• 同一单元格不允许对应两个产生式

LL(1) 文法便是按上述方法得到的不包含重复条目的预测分析表。L, L 和 1 分别指代：从左到右解析(left-to-right parse)，最左推导(left-most derivation)，向前查看一个符号(1 symbold lookahead)。

在 LL(k) 分析表中，每列包括了长度为 k 的终结符序列：

\(\forall\) n >= 0，每个 LL(k) 文法都是 LL(k+n) 文法。

Stack-Based Implementation⚓︎

我们用栈这一数据结构来实现预测分析：

Eliminate Left-Recursion⚓︎

假如同时存在形如这样的产生式 \(E \rightarrow E + T, E \rightarrow T\)，即出现了左递归(left recursion) 的现象，那么必然会导致 LL(1) 分析表中出现重复条目，因为：

• 若 \(t \in \text{First}(T)\)，那么 \(t \in \text{First}(E + T)\)
• 对于这样的 \(t\)，我们能选择任意两个产生式

消除左递归的方法是重写文法，使其分析相同的语言，但使用不同的产生式。

本质是利用右递归来生成重复项。

例子

Left Factoring⚓︎

如果同一非终结符的两个产生式以相同符号开头，LL(1) 分析表将包含重复条目。

Error Recovery⚓︎

遇到语法错误时的应对方法有：

• 抛出异常并停止解析

  void T() { 
      switch (tok) { 
          case ID: 
          case NUM: 
          case LPAREN: F(); Tprime(); break; 
          default: error! 
      }
  } 
  

• 打印错误信息并从错误中恢复（删除、替换或插入记号）

  • 插入：

    • 假设拥有该记号并正常返回
    • 问题：可能无法终止

    void T() {
        switch (tok) { 
            case ID: 
            case NUM: 
            case LPAREN: F(); Tprime(); break; 
            default: 
                print("expected id, num, or left-paren"); 
        }
    }
    

  • 删除：

    • 更安全，因为当到达文件末尾时循环最终必须终止
    • 跳过一些记号，直到遇到 FOLLOW 集合中的某个记号

    int Tprime_follow[] = { PLUS, RPAREN, EOF }; 
    void Tprime() { 
        switch (tok) { 
            case PLUS: break; 
            case TIMES: eat(TIMES); F(); Tprime(); break; 
            case RPAREN: break; 
            case EOF: break; 
            default: 
                print("expected +, *, right-paren, or end-of-file"); 
            skipto(Tprime_follow); 
        }
    } 
    

Bottom-Up Parsing⚓︎

虽然 LL(k) 分析计算高效，且容易编写，但它的问题是：仅在能看到右侧的前 k 个记号的时候就必须预测使用哪个产生式。

因此我们采用自底向上的分析(bottom-up parsing)，具体有以下几类：

• LR(k) 分析（最主流的类型）

  • 移进 - 归约分析 (shift-reduce parsing)
  • 比 LL(k ) 分析更强大，能够将决策推迟到看到与所讨论的产生式整个右侧对应的输入记号之后
  • LR(k) 分别对应：从左到右的解析、最右推导、k 个记号的超前查看

• LALR（超前 (look-ahead) LR）分析：大多数现代编程语言编译器的基础工具，通过 Yacc 等工具实现

自底向上分析的思路是：将字符串归约为起始符号

• 自底向上：从语法分析树的底部向根部进行
• 归约：用产生式的左边替换右边
• 从左到右读取输入
• 通过逆推最右推导，将字符串归约为起始符号，若成功归约则表明分析成功

例子

约定 \(\alpha.\beta\) 表示：

• \(\alpha\)：带有终结符和非终结符的左子串
• \(\beta\)：仅有终结符的右子串

分析器将持续追踪：

• 当前输入的位置（接下来要读取什么输入）
• 一个存放“已分析部分”的终结符与非终结符的栈

且分析器能执行多种操作：

• 移进(shift)：将下一个输入压入栈顶

• 规约(reduce) \(R\)：

  • 栈顶应与规则 \(R\) 的右侧匹配（比如 \(X \rightarrow A B C\)）
  • 从栈顶弹出右侧符号（比如弹出 \(C\ B\ A\)）
  • 将左侧符号压入栈中（比如压入 \(X\)）

• 错误(error)

• 接受(accept)：移进 \(\$\)，并可以规约栈上的剩余内容

例子

LR(0) Parsing⚓︎

先从最简单的 LR 分析，即 LR(0) 分析开始讲解。

• LR(0) 文法是指仅通过查看栈就能进行分析的文法，无需任何超前查看即可做出移进 / 归约的决策
• 使用 DFA 做决策：总结分析状态，并根据文法枚举所有有效的解析状态及其之间的转换

具体过程如下：

• \(.\)：分析器的当前位置
• 起始于 \(S' \rightarrow . S \$\)：栈应为空，且输入预期为一个完整的 \(S\) 句子后接 \(\$\)
• \(A \rightarrow \alpha . \beta\)：LR(0) 项，表示解析器已处理完 \(\alpha\)，并期望接下来看到 \(\beta\)
• 这样能得到一个 NFA，接下来可通过子集构造将其转换为 DFA
  • DFA 的状态是项集合
  • 可基于叫做闭包的过程来直接构造 DFA

例子

算法如下：

例子

LR(k) Parsing Algorithm⚓︎

LR 分析的通用算法如下：

• 查看栈顶状态和输入符号，获取行动

• 若行动为：

  • shift(n)：输入向前推进一个记号，将 n 压入栈中

  • reduce(r)：

    • 根据规则 r 右侧的符号数量，弹出栈相应次数
    • 令 X 为 r 左侧符号
    • 在栈顶当前状态下，查找 X 以获取 goto n
    • 将 n 压入栈中

  • accept：停止分析并报告成功

  • error：停止分析并报告失败

• 只用到状态栈

• 对于 LR(0) 分析，无需查看输入符号即可决定是进行移进还是归约操作

SLR Parsing⚓︎

如图所示出现了移进和归约的冲突，这表明该文法不属于 LR(0)，因而无法被 LR(0) 分析器分析。

解决方法是采用简单 LR 分析（SLR 分析）：仅当在 FOLLOW 集合中存在时，将归约行动放入表中。

修复后的结果

LR(1) Parsing⚓︎

但即便是 SLR 分析，也会遇到无法解决的冲突。

例子

于是我们采用更强大的 LR(1) 分析

• 核心思想：在 DFA 的状态中增加更多信息，从而解决冲突
• 一个 LR(1) 项由一条产生式、一个右侧位置（用点表示）和一个向前看符号(lookahead symbol) 组成
  • \((A \rightarrow \alpha.\beta, x)\) 表示序列 \(\alpha\) 位于（符号）栈顶，且输入头部是一个可从 \(\beta x\) 推导出的字符串
  • 记录在当前上下文中该产生式整个右侧之后的记号
  • 下一个输入记号应属于 \(\text{First}(\beta x)\)（\(\beta\) 可以为空）

算法如下：

• Closure：

  
  • 改变记号 (notation)
  • 执行 \(\varepsilon\)- 转换时，记录右侧的上下文（即 \(w\)）

• Goto：

  
  • 改变项的记号

• 归约行动：

  
  • 在项中添加 \(z\) 并减少操作
  • 行动 \((I, z, A \rightarrow \alpha)\) 表示在状态 \(I\) 下，当向前看符号为 \(z\) 时，分析器将根据规则 \(A \rightarrow \alpha\) 进行归约
  • \(\text{Follow}(A)\) 中的某些标记在具有 \(A \rightarrow \alpha\) 的状态中可能并不总是有效的
  • LR(1) 的展望标记比 SLR 更为精确

例子

LALR(1) Parsing⚓︎

LR(1) 分析的问题是表的大小可能会变得很大，状态数太多。改进方法是采用 LALR(1) 分析：通过合并 LR(1) 分析表中除向前看集合外，项相同的任意两个状态来构建分析表。

• 对于某些文法，LALR(1) 分析表可能包含归约 - 归约冲突，而 LR(1) 表中则没有此类问题

  • 然而在实际应用中，这种差异的影响微乎其微

• 相较于 LR(1) 分析表，LALR(1) 分析表占用更少的内存

LR Parsing of Ambiguous Grammars⚓︎

文法类层级

大多数编程语言有以下语法：

对于 if a then if b then s1 else s2 可能有以下几种解释：

1. if a then { if b then s1 else s2 }
2. if a then { if b then s1 } else s2

在大多数编程语言中，else 必须与最近可能的 then 匹配，因此第一种解释是首选。但会遇到移进 - 归约冲突问题：

我们通过引入辅助非终结符 \(M\)（匹配）和 \(U\)（不匹配）来消除这种歧义。

或者保持语法不变。在构建分析表时，应通过移进操作来解决此冲突（优先采用解释 1）。

Using Parsing Generators⚓︎

我们可以使用分析器生成器(parser generator) 来自动生成分析器：

• 通用且稳健
• 但有时不如手写的解析器来的高效
• 尽管如此，对于懒惰的编译器编写者来说还是不错的选择 hh

而 Yacc（yet another compiler-compiler，又一个编译器 - 编译器）是一个经典的 LALR 语法分析器生成器

• 输入：一个规范文件（通常带有后缀 .y），基本格式为：

  {definitions}
  %%
  {rules}
  %%
  {auxiliary routines} 
  

• 输出：一个包含分析器 C 源代码的输出文件（通常带有后缀 tab.c（LALR 分析表））

%{
#include <stdio.h>
#include <ctype.h>
int yylex(void);
int yyerror (char * s);
%}
%token NUMBER
%%
command: exp {printf("%d\n", $1);};
exp: exp '+' term {$$ = $1 + $3;}
| exp '-' term {$$ = $1 - $3;}
| term {$$ = $1}
;
term: term '*' factor {$$ = $1 * $3;}
    | factor {$$ = $1;}
;
factor: NUMBER {$$ = $1;}
    | ‘(’ exp ‘)' {$$ = $2;}
;
%%
int main() {
return yyparse();
}

int yylex(void){
int c;
// eliminate blanks
while ( (c=getchar()) == ' '); 
if (isdigit(c)) {
    ungetc(c, stdin);
    scanf("%d", &yylval);
    return (NUMBER);
}
if (c == '\n')
    return 0; // stop the parse 
return c;
}

int yyerror (char * s){ 
fprintf (stderr, "%s\n",s ) ; 
return 0;
}

Auxilary Routines⚓︎

• yyparse 被声明为返回一个整数值，分析成功时返回 0，失败则返回 1
• yyparse 过程会调用词法分析器过程（yylex）
• Yacc 期望通过 yylex 返回空值 0 来标记输入结束
• yylex 返回一个记号类型或 0，而 yylval 存储语义值
• 当分析过程中遇到错误时，yyerror 会打印出错误信息

Definition⚓︎

识别记号的两种方式：

• 在语法规则中，单引号内的任何字符将被识别为自身，比如 '+'
• 符号标记可以在 Yacc 的 %token 声明中声明
  • %token NUMBER
  • %start symbol（定义起始符号）

Rules⚓︎

• 语法：Rule { Action Code }
• 在分析器使用该规则执行归约操作后，将执行行动代码
• 尽管动作代码通常位于每个语法规则选项的末尾，但也可以在选项内部编写嵌入式的行动

• 伪变量 (pseudo variables)：$$、$1、$3

  • yylex 可以将记号的语义值存储在 yylval（全局变量）中；默认情况下，yylval = 0

  • 当识别出一个语法规则时，该规则中的每个符号都拥有一个语义值：

    • $$：表示规则左侧的值
    • `\(i\)：表示规则右侧的第 i 个符号的值

  • 这些值由 Yacc 保存在值栈的顶部

• YYSTYPE

  • 数据类型始终由 C 预处理器符号 YYSTYPE 在 Yacc 中定义，默认为：#define YYSTYPE int

  • 不同语法规则 / 符号对应不同的值，处理方法为：

    • 直接在 Yacc 规范中使用 %union 声明联合体

      %union { double val;
                char op;} 
      

    • 在定义中或单独的包含文件中定义一个新的数据类型，并将 YYSTYPE 定义为该类型；必须在相关的操作代码中手动构建适当的值

      #define YYSTYPE ASTNode
      

%union & %type⚓︎

• 所有非终结符通过用户提供的此类操作获取其值
• 记号也可以被赋值，这是在词法分析器中使用 yylval 完成的
• 使用 %union 定义值类型
• 使用 %type 指定每个符号的值类型

%token NUMBER
%union { double val;
         char op;}
%type <val> exp term NUMBER 
%type <op> op
%%
command : exp { printf("%f\n",$1);}
;
exp : exp op term { 
      switch ($2){
          case '+' : $$=$1+$3; break;
          case '-' : $$=$1-$3; break; 
      }
    }
    | term {$$ = $1;}
;
op : '+' {$$ = $1;}
   | '-' {$$ = $1;}
;

Embedded Actions⚓︎

在分析过程中，有必要在完全识别语法规则选择之前执行一些代码，比如：

所以需要记录每个 id 的“类型”，解决方法如下：

decl: type {current_type=$1} var-list
    ;
type: INT {$$=INT_TYPE;}
    | FLOAT {$$=FLOAT_TYPE;}
    ;
var_list: var_list ',' ID {setType(tokenString, current_type);}
        | ID {setType(tokenString, current_type);}
        ;

语法：list: item1 { do_item1($1); } item2 { do_item2($3); } item3（注意是 $3）

Conflicts⚓︎

Yacc 通过以下方式解决两类冲突：

• 移进 - 归约冲突：采用移进操作
• 归约 - 归约冲突：采用语法中较早出现的规则

大多数移进 - 归约冲突以及所有归约 - 归约冲突都是严重问题，应通过重写语法来消除。

Precedence Directives⚓︎

如上所示：左侧的语法自然但存在歧义（未定义优先级或左结合性），而右侧的语法无歧义却难以理解。那么是否存在既能保持语法的自然性，又能强制规定运算符优先级与结合性的方法呢？

对此，Yacc 提供了内置的优先级指令(precedence directives)（消歧规则）。

先来看左侧的语法：虽然自然但高度歧义，其 LR(1) 分析表中存在大量移进 - 归约冲突。我们根据运算符优先级和结合性来解决歧义：

• 选择移进（运算符优先级）

  \[ \begin{aligned} \text{E} & \to \text{E} + \text{E} . & * \\ \text{E} & \to \text{E} . * \text{E} & (\text{any}) \end{aligned} \]

• 选择归约（左结合性）

  \[ \begin{aligned} \text{E} & \to \text{E} + \text{E} . & * \\ \text{E} & \to \text{E} . + \text{E} & (\text{any}) \end{aligned} \]

若不允许 a != b != c，则 != 是非结合的(non-associative)。

在 Yacc 中是这样指定此类消歧规则的：

• 运算符 PLUS 和 MINUS 具有相同的优先级且为左结合
• 运算符 TIMES 和 DIV 的优先级高于 PLUS 和 MINUS，同样为左结合
• 运算符 EXP 为右结合
• 运算符 EQ 和 NEQ 的优先级最低，且无结合性

%nonassoc EQ NEQ 
%left PLUS MINUS 
%left TIMES DIV 
%right EXP

• 优先级声明（%left 等）为记号赋予优先级
• 移位记号的优先级由该记号给出
• 规则的优先级由该规则右侧出现的最后一个记号（终结符）给出
  1. 如果规则具有更高的优先级，则选择归约
  2. 如果标记和规则具有相同的优先级，则：
     • %left 优先归约
     • %right 优先移位
     • %nonassoc 产生错误行动

例子

对于算术表达式 -6 * 8，我们希望被分析为 (-6) * 8。为此，需使用 %prec 指令为规则分配特定的优先级：

%{ // declarations of yylex and yyerror 
%} 
%token INT PLUS MINUS TIMES UMINUS 
%start exp 
%left PLUS MINUS 
%left TIMES 
%left UMINUS 
%% 
exp : INT
| exp PLUS exp 
| exp MINUS exp
| exp TIMES exp
| MINUS exp %prec UMINUS 

• 标记 UMINUS 不会由词法分析器返回，它仅作为一个占位符存在
• 指令 %prec UMINUS 赋予规则 exp : MINUS exp 最高的优先级

Syntax v.s. Semantics⚓︎

考虑一种编程语言，其包含算术表达式如 x + y，以及布尔表达式如 a&(b = c)：

%{ //declarations of yylex and yyerror 
%} 
%token ID ASSIGN PLUS MINUS AND EQUAL 
%start stm 
%left OR 
%left AND 
%left PLUS 
%%
stm : ID ASSIGN ae
| ID ASSIGN be
be : be OR be
| be AND be
| ae EQUAL ae
| ID 
ae : ae PLUS ae
| ID 

• 算术运算符的优先级高于布尔运算符
• 布尔表达式不能与算术表达式相加
• 存在算术变量和布尔变量

其中 be : ID. 和 ae : ID. 之间存在归约 - 归约冲突。解决方案是将此分析推迟到编译器的“语义阶段”，比如a + 5&b => 语法正确

Error Recovery⚓︎

开发者希望程序能报告所有错误，而非仅首个错误。于是下面介绍一些错误恢复相关的技术：

• 局部错误恢复(local error recovery)
• 全局错误修复(global error repair)

Local Error Recovery⚓︎

局部错误恢复机制通过在被检测到错误的点调整分析栈和输入，使得分析能够继续进行。其中 Yacc 使用的一种局部恢复机制是利用特殊记号 error 来控制恢复过程。

如果在表达式中间遇到语法错误，分析器应跳至下一个分号或右括号（同步记号 (synchronizing tokens)）并继续解析。

例子

分析器生成器对错误符号的处理：

• 错误被视为终结符，分析表中会为其录入移进动作，就像处理普通记号一样
• 当 LR 分析器遇到错误状态时，会采取以下行动：
  1. 弹出栈（如有必要），直到达到一个可以对错误记号执行移进动作的状态
  2. 移进该错误记号
  3. 丢弃输入符号（如有必要），直到当前超前看标记在某个状态下能触发非错误的行动
  4. 恢复正常分析流程

statements: statements exp SEMICOLON
        | statements error SEMICOLON
        | /* empty */
exp : increment exp decrement
    | ID
increment: LPAREN {nest=nest+1;}
decrement: RPAREN {nest=nest-1;}

Global Error Repair⚓︎

若采用局部错误恢复技术来修复上述错误，一种可能是会发现一个语法错误，其向前看符号为 :=

• 删除从类型到 0 的短语（允许其中包含错误）
• 或者将 := 替换为 =，但会在 '[' 标记处遇到另一个语法错误

全局错误修复则会寻找最小的插入和删除集合，即使这些操作不在 LL 或 LR 分析器首次报告错误的点上，也能将源字符串转变为语法正确的字符串。

其中一种经典技术是 Burke-Fisher 错误修复：在分析器报告错误的点之前不少于 K 个记号的每个位置，尝试所有可能的单记号插入、删除或替换。虽然有限，但较实用。

如何选择最佳的错误修复：

• 允许分析器在原报告错误点之后继续分析最远的修正
• 通常，如果某个修复能让分析器比最初卡住的位置多前进 R=4 个记号，就认为是足够好的

因此分析引擎必须能够回退 K 个标记并重新解析。

具体实现如下：

• 维护两个分析栈：当前栈与旧栈
• 保留一个包含 K 个记号的队列

• 每当移入新记号时：

  • 将其推入当前栈，并置于队列尾部
  • 移除队列头部元素，并将其移入旧栈

• 每次向旧栈或当前栈执行移入操作时，同时执行相应的规约动作

• 假设在当前记号处检测到语法错误：
  • 对于队列中任意位置可能进行的每个记号插入、删除或替换操作，Burke-Fisher 错误修复器会在（队列副本的）相应位置实施修改，随后尝试从原有栈状态重新分析
  • 通常而言，若能成功解析当前记号之后三至四个记号的内容，即可视为完全成功的修复

• 语义动作

  • 移进和归约操作会反复尝试并被丢弃
  • 若程序员指定的与归约操作相关的语义动作具有副作用时的解决方案：在当前栈上执行归约时，不执行任何语义动作，而是等到相同的归约在旧栈上（永久性地）被执行时才执行

• 插入行动的语义值

  • 当需要插入诸如数字或标识符等标记时，它们的语义值从何而来

  • ML-Yacc 分析器生成器提供了一个 %value 指令

    %value ID ("bogus") 
    %value INT (1) 
    %value STRING ("")
    

• 程序员指定的替换

  • 有时，特定的单记号插入或替换非常常用，应首先尝试（为分析器提供提示）

  • ML-Yacc 解析器生成器具有 %change 指令

    %change EQ -> ASSIGN 
        | ASSIGN -> EQ 
        | SEMICOLON ELSE -> ELSE 
        | -> IN INT END
    

  • IN INT END -> 作用域结束符：自动关闭 let 的作用域

例子

评论区