Modern Compiler Implementation in C

Chapter 0. Concepts & Principles

0.1 Modules and Interface

对于任何大型软件系统，如果设计者注意到了该系统的基本抽象和接口，那么对这个系统的理解和实现就要容易得多。

编译器就被分解成不同的部分（分别称为 “阶段” 和 “接口”）：

1. 词法分析（Lexicon Analysis）：将源文件分解为一个独立的单词符号（token）；

2. 语法分析（Grammar Analysis）：分析程序的短语结构；

3. 语义动作（Semantic Action）：建立每个短语对应的抽象语法树（AST）；

4. 语义分析（Semantic Analysis）：确定每个短语的含义，建立变量和其声明的关联（表），检查表达式的类型，翻译每个短语；

5. 栈帧布局（Frame Layout）：按机器要求的方式将变量、函数参数等分配于活跃记录（即栈帧）内；

6. 翻译（Translation）：生成中间表示树（IR Tree）；

   这是一种与任何特定程序设计语言和目标机体系结构无关的表示；

7. 规范化（Normalization）：提取表达式中的 side effects，并且整理条件分支，方便下一阶段处理；

8. 指令选择（Instruction Selection）：将 IR Tree 结点组合成与目标机指令的动作相对应的块；

9. 控制流分析（Control Flow Analysis）：分析指令的顺序并建立控制流图（Control Flow Graph）。此图表示程序执行时可能流经的所有控制流；

   控制流分析可以帮助流程优化，例如死代码删除；

10. 数据流分析（Data Flow Analysis）：收集程序变量的数据流信息。例如，活跃分析（Liveness Analysis），计算每一个变量仍需使用其值的地点（即它的活跃点）；

    活跃分析可以帮助变量的优化；

11. 寄存器分配（Registers Allocation）：为程序中的每一个变量和临时数据选择一个寄存器，不在同一时间活跃的两个变量可以共享同一个寄存器；

    在 ICS 中提到，这是编译器需要做的非常重要的事；

12. 代码流出（Code Output）：用机器寄存器替代每一条机器指令中出现的临时变量名；

这样分解成多个阶段对编译器的好处是，能够尽可能重用它的组件。

例如，想要编译器生成针对于不同平台的 output，只需要更改栈帧布局（Frame Layout）和指令选择（Instruction Selection）这两个部分就行。

再例如，想要编译器编译不同的源语言，则只需要改变 “翻译” 模块以及之前的部分就行。

至于这些接口的用处：

• 抽象语法（Abstract Syntax）、IR 树、汇编（Assem）之类的接口，是以数据结构的形式做规约，方便下一阶段的实现；

• 另一些像 翻译接口、单词符号（token），是以数据类型的形式做规约；

其中，现代编译器两种最有效的抽象分别是：

• 上下文无关文法（Context-Free Grammar）：用在语法分析，理解为 “形式化描述一个编程语言的语法规则，不涉及任何具体过程”；

• 正则表达式（Regular Expression）：用在词法分析，理解为 “形式化描述一个编程语言合法的单词符号（token）”，现在已经被广泛应用到多个领域，例如 Web 前端的输入校验、文字匹配、IDE 高亮和提示等等；

0.2 Example: Straight-line Program Language

在正式学习编译理论前，我们简单地热个身。

先讨论一类最简单的语言：直线式程序语言。这类语言只有一般语句和表达式，没有循环和分支判断语句。

我们用形式化的文法规则来描述它的语法（理解成广义的上下文无关文法）：

语句文法（statement）：

• Stm -> Stm; Stm，即：一个语句可以是另外两个语句以 semicon（结束符）分隔组成（执行顺序从左到右），称 CompoundStm；

• Stm -> id := Exp，即：一个语句可以是一个赋值语句（作用域内唯一合法标识符 id、一个表达式，执行顺序先 Exp 后赋值），称 AssignStm；

• Stm -> print( ExpList )，即：一个语句可以是输出语句（print 关键字 token、一个表达式列表，输出顺序从左到右），称 PrintStm；

表达式文法（expression）：

• Exp -> id，即：一个表达式可以是仅仅一个标识符的陈列，称 IdExp；

• Exp -> num，即：一个表达式可以是仅仅一个合法数字 token，称 NumExp；

• Exp -> Exp Bionp Exp，即：一个表达式可以是两个表达式间用二元运算符连接（执行顺序先左后右），称 OpExp；

• Exp -> (Stm, Exp)，即：一个表达式可以是一个语句和一个表达式的组合的序列（以逗号分隔，先执行左边的语句，再执行右边表达式），称 EseqExp；

表达式列表文法（Expression List）：

• ExpList -> Exp, ExpList，即一个表达式列表可以由一个表达式和另一个表达式列表组成（逗号分隔），称 PairExpList（递归定义）；

• ExpList -> Exp，即一个表达式可以仅由一个表达式构成，称 LastExpList（递归定义终止）；

二元运算符文法（Binary Operator）：

• Binop -> + or - or * or /，即一个二元运算符只可以是 +，-，*，/ 其中一个；

Chapter 1. Lexical Analysis

1.1 Tokens & Lexemes

一种语言（language）是字符串（string）组成的集合。而字符串是 符号（symbol）的有限序列。而符号则来源于这个语言所定义的有限字母表（alphabet）；

Lexeme：它是一种语言的字符串子串，由一串字符构成（抽象概念），是语言的基本单元。例如在一段代码中，if、10、+ 等等，都是 lexeme；

Token：一种语言对于 lexeme 的抽象的分类表示，可以将其看作程序设计语言的文法单位。token 可以归类为有限的几组单词类型（称 token type），例如 ID、KEYWORD、RELATION、NUM、REAL 等。它通常使用 (token-type, token-value) 对表示。

• 点符号、操作符、分隔符等也算 token；

• 例外：注释、预处理指令、宏、空格符/指标符/换行符等空白字符不是 token；

其中，IF / RETURN 等由字母字符组成的单词称为保留字（reserved word），在多数语言中，它们不能作为标识符（ID）使用。

二者的比较如下：

而实现一个词法分析器（Lexical Analyzer）就是在完成以下的工作：

1. 扫描输入的内容，识别其中某些子串（lexeme）为 token；

2. 返回一组 (token type, token value) 对；

这个过程被称为 Tokenization；

举例：对于下面的一个语句：

int num = 10;

int、num、=、10、; 都是 C 语言的 lexeme；

tokenization 的过程：

• Lexeme int -> Token (KEYWORD, "int")；

• Lexeme num -> Token (IDENTIFIER, "num")；

• Lexeme = -> Token (OPERATOR, "=")；

• Lexeme 10 -> Token (NUMBER, "10")；

• Lexeme ; -> Token (SEPERATOR, ";")；

这个过程就是词法分析器需要做的事。

为了定义一类 token 的规则，我们引入正则表达式来描述这套词法规则。

1.2 正则表达式

一种形式语言，formal language，被广泛使用的最弱的形式语言（the weakest formal language）；

Atomic RE:

• Single Character: L('c') = ["c"];

• Epsilon: $L(\epsilon )$$L(\varepsilon)$ = [""];

• Concentration: L(AB) = $\{ab|a\in L(A),b\in L(B)\}$$\{ab | a\in L(A),b\in L(B)\}$；

• Union: L(A | B) = $\{s|s\in L(A)\text{ or }s\in L(B)\}$$\{s|s\in L(A)\text{ or }s\in L(B)\}$；

• Repitation: $L(A^{\ast })=L(\epsilon )|L(A)|L(AA)|\cdots$$L(A^*)=L(\varepsilon)\space|\space L(A)\space|\space L(AA)\space|\space\cdots$；

1.3 正则 与 词法表示

从现在开始，我们以一种新定义的语言 Tiger 为例。我们使用正则表达式来定义 Tiger 的词法。

例如 Tiger 的 Token 就可以这么定义：

• KEYWORD："else" | "if" | "let" | "var" | "type" | "for" | "function" | "do" | "while" | "then" | "end" | ...；

• NUMBER：[0-9]+（某些编程语言的 re 库中表示为 \d+）；

• ID：[a-zA-Z_][a-zA-Z_0-9]*；

• WHITESPACE：(' ' | '\t' | '\n')+（re: \s）；

• LEFTPAR / RIGHTPAR：'(' / ')'；

• OPERATORS：'+' | '-' | '*' | '/'；

• ……

可能有些 Lexeme 符合多种 token 的定义，因此会规定 token 优先级。

规定了一种语言的词法，接下来要考虑的是如何实现。那么如何实现正则表达式？答案是采用一种特殊的数据结构：有限自动机（FA）。

总体路径如下：

RegExp -> NFA -> DFA -> Tables；

1.4 Finite Automata

1.4.1 Concepts

定义：有限状态机（FA）是一个包含有限个元素（作为 “状态节点”），以及元素间转移的有向边的 图数据结构。

特征：有限自动机有一个有限状态集合和一些从一个状态通向另一个状态的边，每条边上标记有一个符号；其中一个状态是初态，某些状态是终态。

其中，确定有限自动机（Deterministic Finite Automata，DFA）是有限自动机的特殊情况，它不会有从同一状态出发的、两条或以上标记为同样符号的 边，这种有限自动机称为 “确定有限自动机”，意为：“根据输入情况和当前状态一定能确定下一状态” 的有限自动机。

相反地，有不确定有限自动机（Nondeterministic Finite Automata，NFA）；

运行逻辑：从初始状态出发，对于输入字符串中的每个字符，自动机都将沿着一条确定的边到达另一状态，这条边必须是标有输入字符的边。

对 n 个字符的字符串进行了n 次状态转换后，如果自动机到达了终态，自动机将接收该字符串。若到达的不是终态，或者找不到与输人字符相匹配的边，那么自动机将拒绝接收这个字符串。

对于 NFA，针对同一个输入可以对应多个状态（同时位于多个状态），在输入结束后，只要存在一个状态位于终态，那么就会接受这个输入。

根据自动机的运行逻辑，我们可以将一个正则表达式转换为一个 DFA / NFA，以此实现正则表达式的行为。

如果转换为 NFA，则虽然转换过程简单，但运行过程可能出现状态爆炸的问题；

1.4.2 Regular Expression to NFA

可以按照下面的算法将 RE 转换为一个有头有尾的 NFA；其中 “头” 为末端状态，“尾” 为开始边。

思考：$M|N$$M\space|\space N$ 表示中的两个 $\epsilon$$\varepsilon$ 和最后一个状态是否必要？

答案是，如果表达式只有 $M|N$$M\space|\space N$ 的话，是不必要的。但是为了将一段表达式看作一个有一个头、一个尾的整体，可以等价的加上去（这样方便了像 $(M|N)\cdot A$$(M|N)\cdot A$ 一样的表达式的转换）；

1.4.3 NFA to DFA

转换算法的主要规则如下：

• 实际上转换的过程就是模拟 NFA 的过程，DFA 中每个状态都是 NFA 状态节点的非空真子集；

• 创建 DFA start state：从 NFA 入口通过 $\epsilon$$\varepsilon$-move 能到达的所有状态的集合；

• 创建转换过程（transition）$S{\to }^a{S}^{\prime }$$S\rightarrow^a S^\prime$：其中 $a$$a$ 为 NFA 中对应 状态 S 通过一个 $a$$a$-move 和若干个 $\epsilon$$\varepsilon$-move 所能到达的所有状态的集合；

值得注意的是，转换的时候可能存在优先级关系，因此引入 Priority Rule：

假设正则表达式为 $a|abb|a^{\ast }{b}^{+}$$a\space|\space abb\space|\space a^{*}b^{+}$，那么 NFA 为：

注意到优先级应该是 2 优于 7 优于 6（根据在正则式中的先后顺序）；

只要我们再加入下面的转换技巧，就能保证优先级：

• 在创建转换过程中，建议逐一考虑 $S$$S$ 中的每个状态编号的输入可能性，逐一的顺序由 NFA 中体现的优先级决定（例如 $M|N$$M|N$ 的 $M$$M$ 优先级更高一点）；

• 建议使用 BFS 的方法创建转换过程；

• 在创建转换过程中，如果某个状态是终态，则在它的状态号下方标记下划线（方便识别），$S^{\prime }$$S^{\prime}$ 集合中元素以逗号隔开；

• 一个 $S^{\prime }$$S^{\prime}$ 状态集合中只要有一个状态编号有下划线（是终态），则这个 DFA 状态为终态；不满足则不是终态；

• 如果 $S$$S$ 到 $S^{\prime }$$S^{\prime}$ 中有一个状态编号是相同的，但不完全相同，就不能用自环表示。例如上面的 $\{7,6\}{\to }^a\left\{6\right\}$$\left\{7,6\right\}\rightarrow^a\left\{6\right\}$，因为状态 7 没有任何非空输入能让它转换状态，所以用自环是不恰当的；

• 最终 DFA 执行是停在非终态 / ERROR 终态，则解析错误；停在正确的终态中，从左到右（遵循优先级）考虑有下划线的状态编号，作为解析的结果。

1.4.4 DFA to Table

一个 DFA 可以被表示为一张 2D 的表格。其中一维存放所有 states，另一位存放所有可能的 Symbols，数学表达为 $T[{\text{state}}_t,\text{ input}]={\text{state}}_{t+1}$$T[\text{state}_t,\text{ input}]=\text{state}_{t+1}$；

这样能方便计算机执行一个 DFA：通过查找 ${\text{state}}_t$$\text{state}_t$ 和下一个输入符号，就可以跳转到确定的 ${\text{state}}_{t+1}$$\text{state}_{t+1}$；

例如：

1.4.5 The Execution Rule of a DFA

首先明确三种标记：

给定几个规则：

• 初态时，三种标记（分别记为 IPLF、CIP、BCL）都位于第一个位置；

• 接受输入时，current input position（记为 CIP）向前移动、更新当前状态（一般使用 state ID 数字）；如果移动后的状态是终态，那么也将 “input position at the last final”（记为 IPLF）移动到该位置；

• 当输入符号不在 DFA 的当前状态的出路径中 / EOF，总之是无路可走时，则立即检查 IPLF 所处的最终状态（可以是有效，也可以是 Error）；

  • 如果正确，则取得 BCL 到 IPLF 间的字符为一个 Lexeme，并返回；

  • 如果错误，则输出错误信息；

  • 无论是正确还是错误，解析完这个 lexeme 后，立即更新 BCL、CIP 到 IPLF 的位置，将当前状态重新置为状态机的初始位置；

    如果在重置之后立即遇到 EOF，则文件解析完成，退出解析程序。

1.5 Lex: The tool to generate DFA C code from R.E.

本节以 Flexc++ 的使用方法为例讨论 Lex 如何从正则表达式生成实现 DFA 的 C++ 代码；当然，Flex 生成 C 代码道理是一样的。

Flexc++ 将输入的词法规则（正则式和 token type 的映射）文件称为 rule file；Flexc++ 在处理 rule file 后，会生成一系列文件：

• a class header file (Scanner.h)；

• internal header file (Scanner.ih)；

• a base class header file (Scannerbase.h)；

• lex.cc（词法分析器实现文件）；

其中 lex.cc 不应该被修改，因为每次运行 Flexc++ 是都会被覆盖，而其他的文件只会生成一次，可以通过使用、添加 Scanner 类型的成员来达到一些特殊效果（这也是 Flexc++ 和 Flex 不同点之一）；

1.5.1 Format of the Input File: *.lex

一般 Flexc++ 会将 rule file 看作两个部分，使用 %% 来间隔：

xxxxxxxxxx
definitions // contains option specifications and definitions
%%
rules   // contains the regular expressions (and their (optional) actions)

上半部分包含一些选项 / 规约，以及预先的定义，下半部分则包含正则表达式及其定义的行为；

Definitions Section

这一部分包含了：

命名的正则表达式（named regular expressions），方便正则式的复用，格式如下：

xxxxxxxxxx
name pattern    // 二者以空格隔开，正则式以该行的最后一个非空白字符为结尾
                // 这种命名的正则式不允许内部使用 comment（注释）
                // 其中 name 内部允许使用 '-'（hyphens）

Directives（控制指令）：Flexc++ 提供了 命令行 options 和 directives 这两种方法来控制 Flexc++ 的行为。这里详细介绍 directives：

​x
%baseclass-header = "filename"  // 定义生成的 ScannerBaseClass 头文件名。注意在 *.lex 中不接受目录分隔符（即 '/'）

%case-insensitive   // 定义在 Flexc++ 匹配正则式时忽略大小写（匹配时全部转成小写，但是 token value 仍然保持原来的样子）

%class-header = "filename"  // 定义生成的 ScannerClass 头文件名
%class-name = "MyScanner"   // 定义生成的词法解释器的类名

%debug  // 让生成的词法分析器在运行时打印详细信息，但在生成代码时不会使用 #ifdef DEBUG

%filenames = "basename" // 定义生成所有头文件的 prefix 名称

%input-implementation = "sourcefile"    // 指定用户自行实现的 Input 类的实现文件，自定义的方法在后面讨论
%input-interface = "interface"  // 指定用户自行实现的 Input 类的接口（头文件）

%interactive    // 指定生成的 Scanner 是否直接从命令行读取信息（std::cin）

%lex-function-name = "funname"
%lex-source = "filename"    // 定义 lex.cc 文件名

%namespace = "identifer"    // 将生成的 Scanner 类置于指定 namespace 中，默认不使用命名空间

%s namelist // 指定 start condition 的 ID，包括自身，使用空格隔开（什么是 start conditions？后面讨论）
%x namelist // 指定 start condition 的 ID，不包括自身，使用空格隔开

%skeleton-directory = "pathname"    // 指定 Flexc++ 查找模板文件的目录

%target-directory = "pathname"  // 指定 Flexc++ 的输出目录

Rules Section

本部分仅包含正则表达式和行为的映射：

xxxxxxxxxx
pattern action

• action 可选（如果空的话，这条规则会被匹配并且不报错，但不作任何动作），并且和正则式使用 tab / 空格隔开；

• action 中包含单行 C++ statement，或者一个占多行的 compound statement；

• 一个 action 可以是一个 |（vertical bar），表示和下一条规则使用同样的 action；

Comment in Rules File

*.lex rule file 的注释和 C++ 一样，/* */ 和 // 都行，缩进是无所谓的；有几点需要注意：

• 在 action 内的注释会被原封不动地生成到词法分析器中；

• 不能在 definitions section 的 named regular expression 中使用注释；

• 其他部分的注释不会保留到生成的词法分析器中；

Regular Expressions (Pattern) in Rules File

这里仅介绍和 Python/Perl/JavaScript 等常见应用中的正则表达式不同之处。

Flexc++ 不支持的：

• 分组、回溯引用；

Flexc++ 的需要注意的：

• 在字符集中，-、\、]、^ 仍然具有特殊含义，其他原本有特殊含义的字符全部失去特殊含义（除非有 \ 的作用）；

Flexc++ 的不同之处：

• . 不包括换行；

• 加上双引号后，pattern 会变成 literal string，例如 "[xyz]\"foo" 表示字符串本身，而 [xyz]"foo 则是能匹配 x"foo 的 pattern；

  因为双引号有特殊含义，所以想匹配 literal string 的 " 时，需要 \" 手动转义，或者使用 R 前缀；

• R 前缀：类似 Python 的 r""，表示 “转义字符串”，例如 R"[xyz]\"foo" 还是 literal string，不过包含中间的 backslash，等价于 "[xyz]\\\"foo"；

• 十六进制数 和 八进制数：\x2a（0x2a，十进制 42）、\123（0o123，十进制 83）；

• 使用命名的正则表达式：{name}；

• 正向先行断言（Lookahead Assertion）：r/s，等价于常见的 r(?=s)；

• 匹配 End Of File：<<EOF>>；

• 预定义字符集：Rules File 支持 [:predef:] 的方式定义字符集内容。而不是用 \w、\d、\s 这样的方式；具体对应关系如下：

  注意：作为整体使用时记得还要包裹一层 []，主要是为了拼接方便；

  • [:alpha:]，表示所有字母，[[:alpha:]] 等价于 [a-zA-Z]；

  • [:digit:]，表示所有数字（更多的不解释，同上）；

  • [:alnum:]，使用 [[:alnum:]] 等价于 [[:alpha:][:digit:]]，也等价于 [[:alpha:][0-9]]，还等价于 [a-zA-Z0-9]，等价于常见的 \w；

    现在知道为什么还要包裹一层 [] 了吧？

  • 更多的：

    xxxxxxxxxx
    [:alnum:] [:alpha:] [:blank:]
    [:cntrl:] [:digit:] [:graph:]
    [:lower:] [:print:] [:punct:]
    [:space:] [:upper:] [:xdigit:]
    

• 反选预定义字符集：和常见语言中的正则引擎不同（将 \w 换成大写的 \W 来反选），Flexc++ 直接用 [:^alnum:] 这种语法来反选；

• 字符集的并集、差集：[a-z]{+}[0-9] 等价于 [a-z0-9]，[[:alnum:]]{-}[0-9] 等价于 [[:alpha:]]；

• 一个 pattern 最多只能有一个 trailing context（也就是说 / 断言和 $ 文末标记只能同时有一个）；

• Start Condition: Flex/Flexc++ 和普通语言的正则引擎最大的不同就在这里！

  • <s>r：表示在 Start Condition ID 为 s 的子语言中，匹配 r；

  • <*>r：匹配所有 Start Condition 下的 r；

  • <s1,s2,s3>r：不多解释；

  • <sc-list><<EOF>>：在 指定的 Start Condition 的子语言下的 EOF；

  • <sc-list> {compound rules}：在指定的 Start Condition 的子语言下才会生效的 rules，这也是为什么说 “start condition 用来定义子语言”；

  详细信息参见 start conditions 一节；

Actions in Rules File

action 中可以使用 C++ 代码，并且调用预先约定的 member functions（详细请参见后文）来告诉 Flexc++ 生成的词法分析器会对这个 pattern 做何处理；

Start Conditions (Mini Scanners)

Start Conditions 可以用来定义子语言，最常用的用法是：识别字符串 / 注释（textural patterns），也就是告诉 Flexc++ 要生成的词法分析器应该如何描述字符串、如何描述注释、如何描述输入结构，等等。

我们之前在 definitions section 中提到两个指令 %s 和 %x 就是用来声明一个 start condition；

而在 rules section 中使用的 <id> pattern 则定义了词法分析器在子语言中的 actions；

当 actions 中调用 begin(StartCondtion_::?)（是 member functions 中的一种，参见）进入到一种子语言中的时候，不在这个子语言 start condition 定义（就是 <id> {compound rules}）之内的规则全部失效，在 start condition 内的规则才会生效。

反之，调用 begin(StartCondtion_::INITIAL) 就是退出当前子语言，回到原本的环境，该 start condition 内的规则又重新失效，外部的生效。

我们发现这就像嵌套了两套规则系统，互相切换，这就是为什么说 “start condition 用来定义子语言”；

举个例子：

xxxxxxxxxx
%x string   // 定义 start condition ID 为 ‘string’，不包括自身

// ... 其他定义 ...

%%

// ... 其他定义 ...

// 这里识别 " 双引号
\"              {   // action 是 compound statement
                      // 具体作用在 member functions 中讨论
                    more();
                    // 表示进入 Start Condition 定义的子语言中
                    begin(StartCondition_::string);
                }

// 这里定义了 ID 为 ‘string’ 的 start condition 的处理方法
<string>{
    // 表示如果再次遇到 " 符号，则退出当前子语言，回到原始的语言环境中（INITIAL）
    // 并返回 Token type，其中 token value 会被 matched() 返回
    // 更多信息参见 member functions 一节
    \"          {
                    begin(StartCondition_::INITIAL);
                    return Token::STRING;
                }
    \\.|.       more();
}

// ... 其他定义 ...

除了用前面提到的 <id> {compound rules} 定义规则，还可以用 <id>pattern（也是前面提到的）来完成，读者可以自行动手试一试。

进阶：（建议看完 Member Functions 一节后，再来回顾）

假设我想在子语言中嵌套另一种子语言，或者想要实现嵌套注释，应该怎么办？

我们可以修改生成的 Scanner 头文件，添加成员 std::stack<StartCondition_> d_scStack，让这个子语言的 start condition 能放到栈中，再定义方法：

xxxxxxxxxx
// 和已有的 begin() 访问权限一样，都放在 private 中
private:

void Scanner::push(StartCondition_ next) {
 d_scStack.push(startCondition()); // push the current SC.
 begin(next);                      // switch to the next
}
void Scanner::popStartCondition() {
 begin(d_scStack.top());
 d_scStack.pop();
}

这样我们在 actions 中就能用 push 和 popStartCondition 了！

Member Functions in Flexc++'s Output Class Scanner

到目前为止，Flexc++ 生成词法分析器的运作原理就清楚了。通过 CLI options & Directives 控制 Flexc++ 生成物的名称以及其他定义，再给定 “pattern-action” 对，让生成应对 pattern 的 DFA 后将 action 直接复制到模板 Scanner 类的实现文件中，最终得到实现完整的词法编译器源文件。

本节就来看看 “模板 Scanner 类” 中已有的成员，哪些可以在 action 中使用，来实现词法分析器。

首先看 Scanner 类的核心方法 lex_()，它是进行词法解析的 main routine，也是各个 action 装载的位置：

xxxxxxxxxx
int Scanner::lex_()
{
    // ...
    preCode();  // 这是空函数体，inline 在 Scanner.h 中，可以由用户自行定义行为

    while (true)
    {
        size_t ch = get_();            // 获取下个字符
        // ...                           // 执行 DFA 状态变换
        switch (actionType_(range))    // 根据状态（对应的 pattern）选择 action
        {
            // ... maybe return         // 这里面复制了 rules file 中定义的 actions
        }
        // ... no return, continue scanning
        preCode();                       // 我们发现，空函数 preCode 的作用是让用户在每轮 action 没有返回 token type 时自定义行为
    }
}

而我们能在 action 中使用的，就是类 Scanner 的如下成员函数：

注：为了方便理解，笔者调整了介绍的顺序，最好从上向下阅读，不建议跳着读。

在最后笔者会补充总结一下实现细节，帮助读者理解。

xxxxxxxxxx
/**
 * 之前就提过的，用于切换 Start Condition 指定的子语言的函数。
 * 不难发现 Flexc++ 会利用你在 definitions section 中定义的 start condition id
 * 生成一个 StartCondition_ 枚举类型，这样我们在 action 中就能使用了；
 */
void begin(StartCondition_ startCondition);
/**
 * 获取当前的 start condition（也就是处于哪个子语言中，还是原始环境中）
 */
StartCondition_ startCondition() const;

/**
 * 仅当 directives section 中设置了 %debug 时，永远返回 true，否则永远返回 false
 * 这就是不使用 #ifdef DEBUG 宏的 Flexc++ 的替代做法
 * 还可以由 setDebug(bool) 运行时设置（下面就不再介绍这个函数了）。
 */
bool debug() const;

/**
 * 将当前已匹配的文本（可以被 matched() 返回）
 * 插入到 Scanner 类的 output stream 中。
 */
void echo() const;

/**
 * 返回当前被 Flexc++ 处理的 rule file 文件名。
 * 可以由 setFilename(string) 设置返回信息（不会重命名原文件）（下面也不再介绍这个函数）。
 */
std::string const &filename() const;

/**
 * 返回当前被匹配的文本的长度。
 */
size_t length() const;

/**
 * 返回当前正在解析行的行号。
 * 注：如果在 directives 中定义 %lineno，则还会生成功能相同的 lineno() 方法。
 */
size_t lineNr() const;

/**
 * 返回当前已匹配的文本
 * 这里能看出，Scanner 的模板实现中，对于已匹配的文本有单独的 text buffer 来维护。
 * 可以由 setMatched(string) 来设置当前已匹配的文本（下面不再介绍这个函数）。
 *
 * 重要提示：setMatched 可能很有用，例如在解析字符串时，源代码中的 "hello\n"，
 * 可能需要词法分析器在解析后、返回这个 token 前，将两个字符 \n 转换成一个真正的换行符。
 */
std::string const &matched() const;

/**
 * 表示接受当前正在匹配的字符，并且已匹配的文本将作为下一个接受的文本的前缀。
 * 相当于向已匹配文本的 text buffer 中 append 当前匹配的字符。
 * 
 * 注意：这在告诉我们，Scanner 对于已匹配的 text buffer，如果匹配到的 action 中什么都不做，
 * 则会清空 text buffer，只有使用 more() 才能向已匹配的内容追加。
 */
void more();

/**
 * Scanner 类的 output stream 的引用。
 */
std::ostream &out();

/**
 * 关闭当前的处理的 input stream，并从 stream 栈中弹出一个 input stream 作为当前的处理对象。
 * 这就是 Flexc++ 可以同时处理多个输入文件/流的功能。与 pushStream 相对。
 * 
 * @return 当 stream 栈中没有任何 input stream 时弹出失败，返回 false，反之返回 true；
 */
bool popStream();
/**
 * 与上面操作相对。会将当前 input stream 压栈，并指定输入流/文件作为当前 input stream
 */
void pushStream(std::istream &curStream);   // interactive 词法分析器无法使用
void pushStream(std::string const &curName);
/* 除了 pop 和 push，还有 switch（不是栈操作），用的不多，不再介绍。 */

/**
 * 在上文已经介绍过了，让用户在每轮 action 没有返回 token type 时自定义行为
 * 注意修改 Scanner.h 而不是修改 lex.cc
 */
void preCode();
/**
 * 和 preCode 一样是个空函数，可以在 Scanner.h 中由用户自定义 inline 实现。
 * 这个函数会在一个 rule 刚刚被匹配并处理结束前被 lex_() 调用，传入的是当前匹配的 rule 的属性：
 * - PostEnum_::END: 一般是匹配了 input EOF，在 postCode 结束后 lex_ 会立即返回 0（EOF）；
 * - PostEnum_::POP: 一般是匹配了 input EOF，但是 stream 栈里还有其他的 input stream，所以 lex_ 不会立即返回，而是继续处理其他 stream；
 * - PostEnum_::RETURN: 一般是匹配的 action 中含有 return（DFA 终态），会返回下个 token type，lex_ 在结束后会返回这个 type；
 * - PostEnum_::WIP: 一般是匹配的 action 中没有 return，会继续循环处理（不是 DFA 终态）；
 * 
 * 仍然不清楚流程的话建议回顾前文的 lex_() 的基本结构。
 */
void postCode(PostEnum_ type);

/**
 * 将字符 ch / 字符串 txt 重新放回 input stream 中（相当于压入栈顶，下一次就会读到）。
 * 注意字符串 txt 压回会保证读取顺序（比如 txt 是 "hello"，那么会从 o 向 h 依次压栈，确保读出的还是 hello）。
 */
void push(size_t ch);
void push(std::string const &txt);

/**
 * 在当前已匹配的文本中，只接受前 nChars 个字符作为 token value（保留在已匹配的 text buffer 中等待 return 时传递出去）
 * 其余的退回 input stream（相当于 push），等待下一轮解析。
 *
 * 用前面执行 DFA 的说法就是：
 * 将 input position at the last final 向前移动 nChars
 * 并且将 current input position 定位到相同位置（接受 token 时的规则）。
 */
void accept(size_t nChars = 0);

/**
 * 和 accept 作用类似，不过是 “只接受后 nChars 个字符作为 token value”
 */
void redo(size_t nChars = 0);

通过这些方法，我们反过来进一步了解了 Flexc++ 生成的 Scanner 解析词法的实现细节。下面补充总结一下：

• Scanner 中有个临时存放已匹配文本的 text buffer；

• 在每轮匹配（解析）前，执行 preCode()、更新当前的状态（例如 current input position / input position at the last final）；

• 使用 pattern （DFA）匹配后，会现将刚刚匹配到的 string 设置到 text buffer 中（如果上次调用了 more() 就追加），并且进入对应的 action 中；

  因此我们可以在 action 中：

  • 使用 matched() 查看当前匹配到的文本；

  • 使用 length() 查看当前匹配到的文本长度；

  • 使用 more() 请求 Scanner 不要清空这一轮的 text buffer，让下一轮识别的内容直接追加上去；

  • 使用 accept(n) / redo(n) 来截取想要的文本、并把其余部分放回去；

  • 使用 push(str) 直接向 input stream 放入指定下次要读的文本；

  • 使用 begin(SC) 在下一轮解析开始时激活指定语言规则、冻结当前语言规则；

  • 使用 startCondition() 获取当前子语言环境；

  • 使用 lineNr() 获取当前解析的内容在源文件的行数；

  • ……

• 如果 action 会 return Token Type，那么 Scanner 会调用 postCode(PostEnum_::RETURN)，并且作为 DFA 终态，输出 token；

• 如果 action 没有 return，则 Scanner 会按情况调用 postCode(PostEnum_::END/POP/WIP)，继续循环（不认为是终态）/ EOF 主动返回 0；

• 只要没有调用 more()，那么 Scanner 会在下一轮解析前清空上一轮已匹配文本的 text buffer。有模板源码为证：

  

1.6 Lexical in Tiger Language

关注几点：

• How you handle comments；

• How you handle strings；

• Error handling；

• End-of-file handling；

• Other interesting features of your lexer；

Tiger 语言的词法分析器需要识别：

• 保留字（RESERVED）：

  • 用于循环/分支：do, while, if, then, else, for, of, in, to, end, break;

  • 用于定义/赋值：let, var, type, array, function, nil；

• 符号：, : ; ( ) [ ] { } . + - * / = <> < <= > >= & | :=

• 标识符（IDENTIFIER）：A sequence of letters, digits, and underscores；Starting with a letter；

• 符合条件的注释：

  • May appear between any two tokens；

  • Start with /* and end with */；

  • May be nested；

  • detect unclosed comments (at end of file)；

• 整型常量 integer literal（NUMBER）：词法分析阶段不考虑负数；

• 字符串常量 string literal：在 ""（quotes）之间的零个或多个 printable character（包括空白字符）的序列，以及 escape character。解析字符串常量需要能识别 unclosed quote。其中 escape character 包含以下情况：

  • \n, \t：linefeed, tab;

  • \ddd：ddd is a 3-decimal number (not octal);

  • \", \\;

  • \f___f\：this sequence is ignored, where f___f stands for sequence of one or more formatted characters including at least space, tab, or newline, form feed；

  • \^c：

    • ^@ (0, null, NUL, \0), mark the end of a string（在 Tiger 中支持 \0 在字符串中，不作为字符串结尾）；

    • ^G (7, bell, BEL, \a), emit a warning of some kind;

    • ^H (8, backspace, BS, \b), may overprint the previous character;

    • ^I (9, horizontal tab, HT, \t), moves the printing position right to the next tab stop;

    • ^J (10, line feed, LF, \n), moves the print head down one line;

    • ^K (11, vertical tab, VT, \v), vertical tabulation;

    • ^L (12, form feed, FF, \f), to cause a printer to eject paper to the top of the next page, or a video terminal to clear the screen;

    • ^M (13, carriage return, CR, \r), moves the printing position to the start of the line, allowing overprinting;

    • ^Z (26, Control-Z, SUB, EOF). Acts as an end-of-file for the Windows text-mode file i/o;

    • ^[ (27, escape, ESC, \e (GCC only)). Introduces an escape sequence；

Chapter 2. Grammar Analysis

目标：

• 识别从词法分析器传入的 token sequence 是否合法；

• 将识别合法的 token sequence 转为 parse tree（语法分析树）输出给 compiler 的下一环节；

为什么选择 parse tree 作为语法分析阶段输出的数据结构？

因为要生成一种方便机器识别的、方便后续解析工作的数据结构。人们恰好发现这种结构能很好地描述语法结构并且容易处理，主要基于以下观察：

• 程序的语言是递归定义的（需要有层次结构 Hierarchy）；

• Context-Free Grammar 能描述程序语法的组成（下面介绍）；

因此 parse tree 这种树形数据结构可以用来表示程序的内部结构。

2.1 Background

事实上，如果只有正则表达式和词法分析，我们是无法解析复杂的程序语句和表达式的。

考虑这个表达式：$1+2+3$$1+2+3$；我们定义正则式就能解决这个问题：

• digits = [0-9]+；

• sum = (digits"+")*digits；

如果是这个表达式呢？$(1+(250+3/(2+1)))$$(1+(250+3/(2+1)))$，我们定义：

• digits = [0-9]+；

• sum = expr"+"expr；

• expr = "("sum")" | digits；

问题是，这没法使用状态数小于 3 的自动机解析的。如果这样的嵌套更多，有 N 层呢？那么自动机的状态不能少于 N 个状态。

因为状态数为 N 的自动机没法记忆嵌套深度大于 N 的括号。这就是正则语言的局限性。

因此，像这样的 sum 和 expr，就不能仅仅用词法分析来解决。它们的规则就没法用正则表达式描述清楚；

所以我们需要在词法的 token 基础上，利用一种递归表示的方法来描述这种规则。

人们于是创造出一种简单的新的表示方法：上下文无关文法（Context-Free Grammar，CFG）；

CFG 的表示方法就是 Context-Free Language，它和正则表达式一样，也是一种形式语言；

2.2 Context-Free Grammar

2.2.1 Production

我们之前提到过，一种语言（language）是字符串（string）组成的集合。而字符串是 符号（symbol）的有限序列。而符号则来源于这个语言所定义的有限字母表（alphabet）；

对于语法分析而言，“string” 就是源代码，“symbol” 就是 lexical tokens（词法分析器的输出），“alphabet” 就是词法分析器输出的全部 token type 的集合；

一段上下文无关文法相当于一条语法规则，它是一组产生式（production）的集合。其中 production 的书写方式如下：

一个 production 满足以下规则：

• 其右侧包含 0 或者多个符号，每个符号要么是终结符（terminal，就是该语言中的 alphabet 中的一个 token，例如 INDENTIFIER），要么是非终结符（nonterminal）；

  token value 被称为这个 terminal 的语义值（semantic value）；

• 左侧是被定义的符号（又称非终结符），不能是一个 token。其中有种 nonterminal 比较特殊，被称为开始符号（start symbol）；

另外我们规定，未明确给出一个 CFG 的 start symbol 时，其第一个 production 左侧的非终结符为 start symbol；

我们规定严谨的 production 的形式：

• 定义终结符 $T$$T$，非终结符 $N$$N$，开始符号 $S$$S$；

• 设 $X\in N$$X\in N$、$y_i\subseteq N\cup T$$y_i\subseteq N\cup T$、$\epsilon$$\varepsilon$ 为空符号）：

所以一个 CFG 所能代表的语言就可以用一个集合表示：$\{a_1{a}_2\dots a_n|S{\to }^{\ast }{a}_1{a}_2\dots a_n\}$$\{a_1a_2\ldots a_n|S\rightarrow^{*}a_1a_2\ldots a_n\}$；其中 $S{\to }^{\ast }{a}_1{a}_2\dots a_n$$S\rightarrow^{*}a_1a_2\ldots a_n$ 表示开始符号 $S$$S$ 经过 0 或多步的推导得到 $a_1{a}_2\dots a_n$$a_1a_2\ldots a_n$（终结符组成的语句）；

比如我们用 CFG 定义某种语言的语法：

其中 terminal 有：;、id、:=、print、(、)、num、+、,，

nonterminal 有 S（start symbol）、E、L;

Sidebar: 定义语言 CFG production 的技巧；

• 要定义一个左右括号匹配的语言：$S\to (S)|\epsilon$$S\rightarrow(S)\space|\space\varepsilon$；

2.2.2 Derivation

如果要分析一段代码中的语句是不是这个语言的语法、如何解析这个语句为语法树的结构，我们就需要借助 CFG 进行 “推导”（Derivation）。推导的执行过程如下：

1. 从 CFG 的开始符号（特殊 nonterminal）出发，按照某条上下文无关文法展开每一个 nonterminal；

2. 每步的展开，既可以展开当前 CFG 中最左边的 nonterminal，也可以展开最右边的，目标是向那段指定的代码推导；

3. 重复展开的步骤，直至式中再无 nonterminal。如果能匹配，则该代码符合语法规范，并且语法解析成功，反之失败；

其中，上面每步展开 CFG 最左边 nonterminal 的做法称为 “最左推导”（leftmost derivation），每步展开最右边 nonterminal 的做法称为 “最右推导”（rightmost derivation）；

当然如果每步展开的 nonterminal 位置不固定，那么既不是最左也不是最右推导，这种推导没有那么特殊。

另外还可以发现，一个 CFG 的推导的数量是无限多的，最终推导到同一个代码语句的方式也不唯一。

2.2.3 Parse Tree, Ambiguous Grammar, EOF

这里有几个零散的概念。

在语法分析器读入 terminals 时，也会读入 EOF（文件结束符，由词法分析器给定）。我们在 CFG 的书面表达中一般用 $ 来表示文件结束。所以，为了让 CFG 更完整，描述 EOF 只会出现在完整的 S-phase（S 为开始符号）之后，我们可以在 CFG 前添加一条规则 S' -> S$；

再讨论另一个概念。我们根据 derivation 的过程，将其中各个符号连接到从它推导出的符号（即：父符号做父结点，子符号做子结点），最终会形成一棵树形结构。这就是语法分析树（Parse Tree）；两种推导过程可以拥有同样的 Parse Tree。Parse Tree 具有以下特点：

• 所有 nonterminals 都是中间结点、所有 terminals 都是叶结点；

• Parse Tree 的中序遍历就是词法分析器的原输出（input of parser）；

• Parse Tree 包含了各操作符间的关系、优先级等信息；

• 一个无二义性的（Ambiguous）语句通过 CFG 推导后，一定能得到相同的 Parse Tree；

上面最后一条特点就是二义性的等价定义。当一种文法（CFG）在推导同一个语句时，能推出不同的 Parse Tree，则说明这个文法有二义性（Ambiguous Grammar）。比如我们之前看的文法 3-1：

用它来推导 id := id + id + id 能得到两个不同的 Parse Tree：

类似地，这种文法直觉上是没问题的，但也有二义性（解析 1 + 2 * 3）：

而二义性文法会给后续的语法分析带来困难，主要是因为我们（作为编译器一方）无法准确理解代码的准确含义，进而没法翻译成准确的汇编代码。

2.2.4 Disambiguation

如何去除这些二义性？

第一种方法是重构 CFG，因为大部分二义性文法都能转换为非二义性的。例如上面的文法可以通过修改 CFG 来体现各个运算间的优先级来去除二义性：

修改后的 CFG 添加了两种 nonterminal：$T$$T$（Term，项，可以相加的语法实体）、$F$$F$（Factor，因数，可以相乘的语法实体）。

这样在无形中定义了乘法和加法的运算优先级、结合性，例如 T -> T * F 规定了 * 是左结合的。如果希望 * 右结合，就改为 T -> F * T；

现在这种语法就能消除二义性，让每条语句只能被 CFG 推导为唯一的 Parse Tree；

注：存在一些语言只有二义性文法，且无法转换。这种语言不能作为程序设计语言。

练习：以下的 CFG 表示的语言是否有二义性？如果有能否举个例子？应该如何修复二义性？

$$\begin{array}{rl}E& \to \text{if }E\text{ then }E\\ & |\text{if }E\text{ then }E\text{ else }E\\ & |\dots \end{array}$$

这么定义显然是有二义性的。例如 if E1 then if E2 then E3 else E4，可以解析为两种 Parse Tree：

• if [E1] then [if E2 then E3 else E4]；

• if [E1] then [if E2 then E3] else E4；

注意到这个问题是由于 else 的结合规则规定不清导致的。我们需要修改 CFG，使其能够指明 else 需要和前方最近的 then 结合。于是我们需要区分 then 的匹配情况。定义：

• MIF（match if）表示 then 和 else 是齐全的；

• UIF（unmatch if）表示 if 后仅有 then；

于是 CFG 改为：

$$\begin{array}{rl}E& \to MIF|UIF\\ MIF& \to \text{if }E\text{ then }MIF\text{ else }MIF|\dots \\ UIF& \to \text{if }E\text{ then }E\\ & |\text{if }E\text{ then }MIF\text{ else }UIF\\ & |\dots \end{array}$$

或者更清晰地：

$$\begin{array}{rl}E& \to \text{if }E\text{ then }E\\ & |\text{ if }E\text{ then WithElse else }E\\ & |\dots \\ \\ \text{WithElse}& \to \text{if }E\text{ then WithElse else WithElse}\\ & |\dots \end{array}$$

这种方法相当不直观，而且没有自动化的工具帮助我们，只能靠直接思考来解决；

第二种方法是添加约束/声明。我们使用原来的 CFG 有一个好处是可读性好。在这个基础上，我们要把一些事说清楚就可以加上一些约束/声明，例如上面提到的 “else 需要和前方最近的 then 匹配”、“加法、乘法都是左结合的，并且乘法优先级更高”，等等。

这种方法就能支持一些自动化工具了。例如 bison（一种处理 CFG 的语法分析器）就支持利用添加声明来消除二义性。

以 bison 为例，其内置了常见的用于规定二元操作符的语法：

• %left +：表示 + 符号是左结合的；

• 先定义 %left + 再定义 %left *：表示 +、* 都是左结合的，但 + 优先级高于 *；

2.3 Top-down Parsing

现在我们正式讨论如何根据语言的 CFG 来解析一个语句是否为该语言的语句。

本节主要讨论一类 “自上而下” 构造 Parse Tree（将 nonterminal 替换 terminal，比较直观）的语法分析算法，称为 Top-Down Parsing；

2.3.1 Recursive Decent Parsing

Example

Top-down parsing 中，有一种比较简单直观的方法，称为 “递归下降”（Recursive Decent）算法。它的原理就是把一个 production 变成递归函数的一个子句，因此一些简单的文法使用它就能轻松解析。

我们先考虑简单的情况，假如一个只有右结合运算的 CFG（为什么必须只有右结合？因为目前还处理不了左结合）：

然后 input tokens sequence 为：$(\text{int},5),(\text{operator},\ast )(\text{int},2)$$(\text{int},5),(\text{operator},*)\space(\text{int},2)$；

第一步应该选哪个 production？答案是都可以，因为对递归下降算法而言，先选谁最终都能得到唯一正确的 Parse Tree（如果无二义性的话）；

1. 选择 $E_0\to T_1+E_2$$E_0\rightarrow T_1+E_2$（注意要从开始符号开始）；

   • 再向下继续选择 $T_1\to (E_3)$$T_1\rightarrow(E_3)$，左括号无法匹配，失败回溯到上一级选择；

   • 选择 $T_1\to \text{int}$$T_1\rightarrow\text{int}$，匹配成功；

     • 继续匹配发现 $T_1$$T_1$ 后的 $+$$+$ 与当前 $\ast$$*$ 不匹配，失败，回溯到上一级选择；

   • 选择 $T_1\to \text{int}\ast T$$T_1\rightarrow\text{int}*T$，匹配成功；

     • 继续匹配发现 $T_1$$T_1$ 后的 $+$$+$ 与当前 EOF 不匹配，失败，回溯到上一级选择；

   • 这个选择整体失败，回溯到上一级；

2. 选择 $E_0\to T_1$$E_0\rightarrow T_1$；

   • 向下继续选择 $T_1\to (E_2)$$T_1\rightarrow(E_2)$，左括号无法匹配，失败回溯；

   • ……

   • 选择 $T_1\to \text{int}\ast T_2$$T_1\rightarrow\text{int}*T_2$，成功；

     • 继续匹配 $T_2\to \text{int}$$T_2\rightarrow\text{int}$，也成功。匹配结束（$E_0\to T_1\to \text{int}\ast T_2\to \text{int}\ast \text{int}$$E_0\rightarrow T_1\rightarrow\text{int}*T_2\rightarrow\text{int}*\text{int}$），顺势构建 Parse Tree；

Left-Recursive Grammar

现在回过头讨论一下，我们之前说 “现在还处理不了左结合”，这是因为一旦遇到了形如 $S\to Sa$$S\rightarrow S\space a$ 的 production，递归下降算法会出现无限递归的情况。这种情况也被称为 “左递归语法”（left-recursive grammar）；

不过我们可以通过一些手段消除左递归：

形如 $S\to S\alpha |\beta$$S\rightarrow S\space\alpha\space\space|\space\space\beta$ 的 grammar 可以转换为：

同理，更一般的情况 $S\to S{\alpha }_1|S{\alpha }_2|\dots |S{\alpha }_n|{\beta }_1|\dots |{\beta }_m$$S\rightarrow S\space\alpha_1\space|\space S\space\alpha_2\space|\space\ldots\space|\space S\space\alpha_n\space|\space\beta_1\space|\space\ldots\space|\space\beta_m$（多个 $S{\alpha }_k$$S\space\alpha_k$ 和 ${\beta }_j$$\beta_j$）可以转换为：

这样我们可以在递归下降之前消除一次左递归，就能正常使用了！

Conclusion

总而言之，递归下降方法的优点明显：方便理解、方便实现；

不过缺点也很显著：多层的递归、回溯，造成了比较大的性能问题；

2.3.2 Predictive Parsing

LL(k) Grammars

Recursive Decent Parsing 的缺点是执行较慢、递归层数较多。为了改进这个问题，人们引入了另一种方法，称为预测式分析（predictive paring）；

预测式分析和递归下降很像，但是前者会预测现在应该使用什么 production 来解析当前的 sequence；

预测式分析的原理是通过向后多看几个 tokens 再做决定，规避了失败回溯的情况。

其中，预测式分析支持 LL(k) Grammars。所谓 LL(k)：

• 第一个 L：从左到右扫描输入，left-to-right scan of input；

• 第二个 L：最左推导，leftmost-derivation；

• k：向后看 k 个 token(s) 来做预测；

另外我们定义，能够采用 LL(k) 的预测式分析来正确解析的语言，被称为 LL(k) Language，其 CFG 称为 LL(k) Grammar；

Example

本节我们以 LL(1) 为例介绍。现在来看最简单的 LL(1) Language 的例子：

这个例子中，每个 production 前面都有唯一一种 terminal/non-terminal。这样 LL(1) 就不会出现错误。

回想 Mini-Basic 语法，它就是一种 LL(1) Language，因为它也是利用语句的第一个关键字来识别语句的种类，然后 expression 则采用的是逆波兰表达式转为后缀式来解析，不过这个例子中没有复杂的 operators，所以更简单。

对应的 LL(1) Parser 代码如下：

xxxxxxxxxx
enum token { IF, THEN, ELSE, BEGIN, END, PRINT, SEMI, NUM, EQ };
/* Input */
extern enum token getToken(void);
/* Custom Exception Handler */
extern void error(void);

/* Current Token */
enum Token tok;
/* Get next token */
void advance() {tok = getToken();}
/* try to parse */
void eat(enum Token t) { if (tok == t) advance(); else error(); }

// 为每个 non-terminal 定义一个互递归函数
// 使用最开始用递归的方法来解析。如果出错就返回上一步
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); }

Left-Factored & LL(1) Languages

另外，我们能发现：LL(1) Language 中，对于一个任何 nonterminal（向后看一个 token），总有且仅有一个 production 能正确解析；

因此一个 LL(1) Language 的 CFG 可以由一个 2D Table 等价替代：

• 一个维度存放当前需要展开的 nonterminal；

• 另一个维度存放下一个 token 的情况；

• 一个 table entry 存放对应的 production；

这样 LL(1) Language 的语法分析器是可以通过给定 CFG 而自动化生成的！

现在回忆上一节最开始的例子，看看我们能不能用 predictive parsing 的方式解决它：

我们发现这个 CFG 用 LL(1) 是没法预测的，因为：

• 对 nonterminal $T$$T$ 而言，后面有两个相同的 terminal $\text{int}$$\text{int}$ 作为开头；

• 对 nonterminal $E$$E$ 而言，有两个 productions 都以 $T$$T$ 开头；

对此，我们类比 NFA 和 DFA 的区别，我们要将相同的部分进行提取，这称为 left-factored，上面的 CFG 可以转变为：

• 将共同的 $T$$T$ 开头提出，后面的部分产生新的 nonterminal $X$$X$；

• 将相同的 $\text{int}$$\text{int}$ 开头提出，后面的部分产生新的 nonterminal $Y$$Y$；

恭喜！现在它成功变成了 LL(1) Language！我们可以继续使用 predictive parsing 来解析它了。

所以和梯度下降算法类似，预测式分析前，必须要进行 left-factored 的提取过程。

LL(1) Parsing Process: Example

我们现在以上面的 LL(1) Grammar 为例：

对于一个输入 $\text{int}\ast \text{int}\mathrm{\$}$$\text{int}*\text{int}\space\$$ 的 Token Type 串，有下列解析过程：

How to Construct a Predictive Parsing Table

考虑任意一个中间状态：$S{\to }^{\ast }\beta A\gamma$$S\rightarrow^{*}\beta A\gamma$（可能同时含有 non-terminal 和 terminal 的式子），并且正在匹配的 input：$\beta b\delta$$\beta b\delta$；此时讨论两种情况：

• $b$$b$ 是 non-terminal $A$$A$ 的某个/某些 production 的开头的 terminal（我们称这种情况为 $b\in \text{First}(A)$$b\in\text{First}(A)$）；

  或者说：$A$$A$ 可以使用以 $b$$b$ 开头的 所有 $A\to \alpha$$A\rightarrow\alpha$ production。

  更进一步地，我们应该如何找到 “$A$$A$ 中所有用 $b$$b$ 开头的 production”？这实际上就是在找 $\text{First}(A)$$\text{First}(A)$。

  定义：$\text{First}(X)=\{b|X{\to }^{\ast }b\alpha \}\cup \{\epsilon |X{\to }^{\ast }\epsilon \}$$\text{First}(X)=\{b|X\rightarrow^{*}b\alpha\}\cup\{\varepsilon|X\rightarrow^{*}\varepsilon\}$；

  计算 $\text{First}(X)$$\text{First}(X)$ 的方法是：

  对于所有（每个逐个） production：$X\to A_1{A}_2\dots A_n$$X\rightarrow A_1A_2\ldots A_n$，

  • 添加 $\text{First}(A_1)-\{\epsilon \}$$\text{First}(A_1)-\{\varepsilon\}$ 到 $\text{First}(X)$$\text{First}(X)$ 中，如果 $\epsilon \notin \text{First}(A_1)$$\varepsilon\not\in\text{First}(A_1)$，那就停止；

    （含义解释：所有 $A_1$$A_1$ 可以翻译出以 $b$$b$ （非空）开头的集合。如果当前不可能翻译出 $\epsilon$$\varepsilon$，那么情况就讨论全了，直接停止；反之需要继续讨论下一项开头为 $b$$b$ 的情况，也就是继续向集合内添加）

  • 重复上述步骤，直至 $\text{First}(A_n)-\{\epsilon \}$$\text{First}(A_n)-\{\varepsilon\}$；

  • 如果到最终一步还是存在 $\epsilon$$\varepsilon$，那么向 $\text{First}(X)$$\text{First}(X)$ 中添加 $\epsilon$$\varepsilon$；

    （含义解释：最终 $X$$X$ 确实可能被翻译为唯一的 $\epsilon$$\varepsilon$，表示 $b$$b$ 可能不在 $A$$A$ 中被翻译）

  其中：

  • $\text{First}(\text{terminal})=\text{terminal}$$\text{First}(\text{terminal})=\text{terminal}$；

  • $\text{First}(X|Y)=\text{First}(X)\cup \text{First}(Y)$$\text{First}(X|Y)=\text{First}(X)\cup\text{First}(Y)$，定义 $X|Y$$X|Y$：$Z\to A_1{A}_2\dots |B_1{B}_2\dots$$Z\rightarrow A_1A_2\ldots|B_1B_2\ldots$，$X\to A_1{A}_2\dots$$X\rightarrow A_1A_2\ldots$，$Y\to B_1{B}_2\dots$$Y\rightarrow B_1B_2\ldots$，则 $Z=X|Y$$Z=X|Y$；

• $b$$b$ 不是 non-terminal $A$$A$ 的任何 production 的开头的 terminal；此时新状态应该是 $S{\to }^{\ast }\beta Ab\omega$$S\rightarrow^{*}\beta A b\omega$（我们称这种情况为 $b\in \text{Follow}(A)$$b\in\text{Follow}(A)$）;

  这个时候只能使用 $A$$A$ 能翻译为 $\epsilon$$\varepsilon$ 的 $A\to \alpha$$A\rightarrow\alpha$ 的 productions，并且知道 $b$$b$ 一定翻译在 non-terminal $\gamma$$\gamma$ 中；

  同样，我们需要找 $\text{Follow}(A)$$\text{Follow}(A)$ 来得知所有可以展开为 $\epsilon$$\varepsilon$ 的 $A$$A$ 的 productions；

  定义：$\text{Follow}(X)=\{b|S{\to }^{\ast }\beta Xb\delta \}$$\text{Follow}(X)=\{b|S\rightarrow^{*}\beta X b\delta\}$；

  计算 $\text{Follow}(X)$$\text{Follow}(X)$ 的方法是：

  对所有（每个逐个） $X$$X$ 在右边的 production：$Y\to \dots X{A}_1{A}_2\dots A_n$$Y\rightarrow\ldots XA_1A_2\ldots A_n$，

  • 如果 $X$$X$ 是 start symbol，向 $\text{Follow}(X)$$\text{Follow}(X)$ 中添加 $\mathrm{\$}$$\$$；

  • 添加 $\text{First}(A_1)-\{\epsilon \}$$\text{First}(A_1)-\{\varepsilon\}$ 到 $\text{Follow}(X)$$\text{Follow}(X)$ 中，如果 $\epsilon \notin \text{First}(A_1)$$\varepsilon\not\in\text{First}(A_1)$，则停止；

    （含义解释：所有在 $X$$X$ 之后的 $A_1$$A_1$ 可以翻译成以 $b$$b$ 开头的集合。如果当前不可能翻译出 $\epsilon$$\varepsilon$，则情况讨论全了，停止；反之继续讨论下一项开头为 $b$$b$ 的情况）

  • 重复上述步骤，直至 $\text{First}(A_n)-\{\epsilon \}$$\text{First}(A_n)-\{\varepsilon\}$（请注意，不到最后一步前都加的是 $\text{First}$$\text{First}$）；

  • 如果到最终一步还是存在 $\epsilon$$\varepsilon$，那么将向 $\text{Follow}(X)$$\text{Follow}(X)$ 中添加 $\text{Follow}(Y)$$\text{Follow}(Y)$；

    （含义翻译：如果 $Y$$Y$ 所有含 $X$$X$ 的 production 中，$X$$X$ 以后的 non-terminal 都能翻译成 $\epsilon$$\varepsilon$，则说明 $b$$b$ 可能在 $Y$$Y$ 以后的 non-terminal 被翻译，因此加上 $Y$$Y$ 整体被翻译为 $\epsilon$$\varepsilon$ 的情况，也就是 $\text{Follow}(Y)$$\text{Follow}(Y)$）

因此，借助 $\text{First}(X)$$\text{First}(X)$ 和 $\text{Follow}(X)$$\text{Follow}(X)$，我们可以这么构建：

对 CFG 中的每一条 production $A\to \alpha$$A\rightarrow\alpha$：

1. 对每个非空 terminal $b\in \text{First}(\alpha )$$b\in\text{First}(\alpha)$：$T[A,b]=\alpha$$T[A,b]=\alpha$；

   注意不是 $\text{First}(A)$$\text{First}(A)$！

   解释：如果 $A$$A$ 开头可以被翻译出 $b$$b$，那么将这个可能的 production 的结果加入到 “当前 Token 是 $b$$b$、non-terminal 是 $A$$A$” 的格子中；

   这里讨论了所有 $A$$A$ 开头翻译出 $b$$b$ 的情况；

2. 如果 $\alpha {\to }^{\ast }\epsilon$$\alpha\rightarrow^{*}\varepsilon$，则对每个 terminal $b\in \text{Follow}(A)$$b\in\text{Follow}(A)$：$T[A,b]=\alpha$$T[A,b]=\alpha$；

   解释：如果 $A$$A$ 开头可以被翻译为空（$\epsilon$$\varepsilon$，多少步都行），那么考虑 $A$$A$ 翻译为 $\epsilon$$\varepsilon$ 后，production 的后面还能翻译成的 terminal $b$$b$ 都加入 “当前 Token 是 $b$$b$、non-terminal 是 $A$$A$” 的格子中；

   这里讨论了所有 $A$$A$ 开头翻译出 $\epsilon$$\varepsilon$ 且后面翻译出 $b$$b$ 的情况；

3. 如果 $\alpha {\to }^{\ast }\epsilon$$\alpha\rightarrow^{*}\varepsilon$ 且 $\mathrm{\$}\in \text{Follow}(A)$$\$\in\text{Follow}(A)$：$T[A,\mathrm{\$}]=\alpha$$T[A,\$]=\alpha$；

   解释：如果 $A$$A$ 开头可以翻译为空（$\epsilon$$\varepsilon$，多少步都行），那么考虑 $A$$A$ 翻译为 $\epsilon$$\varepsilon$ 后结束的情况，都加入 “当前 Token 输入结束了、non-terminal 是 $A$$A$” 的格子中；

   这里讨论了所有 $A$$A$ 可以 fallback 到 $\mathrm{\$}$$\$$（EOF） 的情况（其实蕴含在第二条中）；

上面的 3 条规则将 LL(1) production 的信息彻底转换为一个 2D Table 以供解析。

Error Handling

我们希望 Parser 在遇到错误后停下来，因此：

• Insert Token：在出错的地方根据 production 假装有个合法的 token 在那（相当于补了一个 token），并报错。但可能有 endless loop 的风险（如果补充的 token 还是错误了）；

• Delete Token：在出错的地方跳至下一个合理的 token 处，也就是 $\text{Follow}(A)$$\text{Follow}(A)$ 中任意一个元素；

Summary

虽然对于 LL(1) Language，上述的 parser 实现方案已经相当齐全了，但是值得注意的是，目前大多数实用的高级语言都不是 LL(1)，因此只了解 LL(1) Parsing （也就是 Top-Down Predictive Parsing）是不够的。我们需要更强力的解析策略。

2.4 Bottom-up Parsing

“自下而上”地构造 Parse Tree 实际上应用比 top-down parsing 更普遍。

人们是在基于 top-down parsing 的基础上讨论出了这种方法，效率可观、并且在实际应用中更为普遍。

由于这个方法的特性，人们也将这种 parsing method 称为 “LR Parsing”：

• L 表示从左向右阅读/解析 token；

• R 表示使用 最右推导（Rightmost Derivation）；

最后 LR Parsing 的特性是：

• 能支持左递归、也不需要 left-factored；

LR Parsing 的核心思路是：

将一个输入的 token 串（string），尝试使用 production $A\to \beta$$A\rightarrow\beta$ 将字符串中的 $\beta$$\beta$ 识别并替换（每次选最左边）；

重复识别、替换的步骤，直到 string 成为一个 start symbol；

2.4.1 Shift-Reduce Parsing

如何实现 LR Parsing 中 “将 string 中的 $\beta$$\beta$ 识别为 $A$$A$ 并最终替换为 Start Symbol” 呢？

我们需要一个实现思路：将 token string 看成两个 substring；

• 右边的 substring（$\gamma$$\gamma$）是 Parser 还没有解析的部分，全是 terminal；

• 左边的 substring（$\alpha A$$\alpha A$）是 Parser 正在识别的部分，有部分被替换成 non-terminal，也有部分目前还没有识别的 terminal；

注：为了方便分析的时候查看二者的分界情况，我们后面会用 “$▹$$\triangleright$” 来表示分界（实际在 token string 中不存在）；

在实现前，我们定义两个动作：

• Shift：将 $▹$$\triangleright$ 向右移 1 个 token 的位置；

• Reduce：在 $▹$$\triangleright$ 左边的 substring 中应用某条 production 规则替换为 non-terminal；

举个例子，LR Parsing 过程如下：

我们要识别 int + (int) + (int) $，那么：

• 第一步：$▹\text{int}+(\text{int})+(\text{int})\mathrm{\$}$$\triangleright\space \text{int}+(\text{int})+(\text{int})\space\$$，执行 shift；

• 第二步：$\text{int}▹+(\text{int})+(\text{int})\mathrm{\$}$$\text{int}\space\triangleright+(\text{int})+(\text{int})\space\$$，执行 reduce（$E\to \text{int}$$E\rightarrow\text{int}$）;

• 第三步：$E▹+(\text{int})+(\text{int})\mathrm{\$}$$E\space\triangleright+\space(\text{int})+(\text{int})\space\$$，执行 3 次 shift；

• 第四步：$E+(\text{int}▹)+(\text{int})\mathrm{\$}$$E+(\text{int}\space\triangleright)+(\text{int})\space\$$，执行 reduce（$E\to \text{int}$$E\rightarrow\text{int}$）；

• ……

现在我们考虑如何在代码层面实现它。

• 左边的 substring 可以放在栈数据结构中；

• shift 操作是将一个 terminal 推入栈中；

• reduce 操作是从栈中弹出 0 或多个 symbols（可能有 terminal，也可能有 non-terminal），根据 production 合成一个 non-terminal 后再推入栈中；

有点像表达式运算的过程；

2.4.2 LR(k) Parsing & DFA

好现在有个问题：怎么能准确地知道什么时候 shift、什么时候 reduce，才能保证最终转换成 start symbol / 抛出解析错误？

例如为什么 parser 知道在第二步的时候，不是继续 shift，而是先执行 reduce？

好办！我们借鉴 Top-Down Parsing 中的 predictive parsing 的思想，可以通过左边 substring（放在栈中）的已有的情况来判断应该使用什么 production。这个根据栈中状态决定行为的方法，还可以用 DFA 进行包装！也就是说：

• DFA 输入是当前 stack 中的内容，并且维护一个当前状态所在结点；

• DFA 执行方案就是：

  1. 如果 stack 中的内容不足以使 DFA 发生一次状态转换，那么执行 shift；

  2. 如果 stack 中的内容对应 DFA 中的一条可行转换，则在检查转换条件（关于转换条件，不是查看 stack，而是查看当前的输入 symbol。参见下面的例子）后，如果满足，则执行 reduce；否则继续 shift；

  3. 每次 reduce 会重置 DFA 的状态为最初状态；

如果 DFA 每次查看 stack 上前 k 个元素，则成这种解析方式为 LR(k) 的，如果有一种 language 只需要 LR(1) 就能正确解析，则称这类 language 为 LR(1) Language，称这种 language 的 CFG 为 LR(1) Grammar；

仍然举之前经典的例子，这就是一个 LR(1) Language：

也就是说这个语言构建出的 DFA 每次只需要看栈顶的 1 个元素就能正确解析。它对应的 DFA 如下：

那么好，我们如何构建这个 DFA？答案还是 2D Table，但是有 2 份：

第一份是 transition 表，描述根据栈顶的信息接下来可以转到的状态：

• 一个维度存放当前的栈顶的 symbol（可能有 terminal/non-terminal，可以画条线区分）的可能性；

• 另一个维度存放 DFA 的当前状态的可能；

• entry 存放 DFA 下一个状态结点；

第二份表是 action 表，描述在状态转换后可以进行的动作：

• 一个维度存放当前的输入 terminal（是输入，而不是栈顶，所以不包含 non-terminal） 的可能性；

• 另一个维度存放 DFA 转换后的状态的可能；

• Table Entry 存放 parser 可以进行的动作（shift / 哪一类 reduce）；

我们可以将这两张表合起来（放在一起，仅仅是行列的元素相似，但是含义不一样）。这样，我们将合并的表的 terminal 的列（既有 transition 又有 action）称为 action table，将 non-terminal 列（只有 transaction）称为 goto table；

2.4.3 LR Parsing Algorithm

我们回顾一下之前的做法就会发现，“每次 reduce 会重置 DFA 的状态为最初状态”，并不是一种高效的做法，因为我们会因此需要从栈底开始一个个重新进行 transaction。我们应该借助已经解析的部分，推断出 reduce 后 DFA 应该位于哪里，这样就能节省一定的状态转换步骤。

Q&A

例如对于 LR(1)，我们只需要记录每次 1 个 symbol 和 state 的对应关系 <sym, state> 就行，方便下次 reduce 后查看到这个符号对应的状态。以上面的 int + (int) + (int) $ 解析为例：

• 先写入 <dummy, 0> 的关系（表示当前栈空，对应状态 0）；

• 根据状态 0 + 输入 int ，查询 action 表后得到 shift；根据状态 0 + 栈顶 int（因为 shift 后栈顶一定是它），提前查询 transition 表得到下一个状态是 1；故转换至新状态 1，则记录 <int, 1>，表示当前栈顶为 int，对应状态 1；

• 根据状态 1 + 输入 +，查询 action 表后得到 reduce E -> int。注意！这里栈里没有信息（<dummy, 0>），我们只能退回状态 0，将 E 入栈。由于我们知道 reduce 的结果一定是 E 在栈顶，因此可以在入栈前提前查询 transition 表（对 non-terminal 来说就是 goto table） “状态 0（查栈顶 <dummy, 0> 得知的将退回的状态） + 栈顶 E”，转移结果是状态 2，所以记录 <E, 2> 后 reduce 入栈，并直接到状态 2；

• 继续根据状态 2 + 输入 +，查询 action 表后得到 shift；根据状态 2 + 栈顶 + 得到下一状态 3（这里记录 <+, 3>）；故转换至新状态 3；

• 根据状态 3 + 输入 (，查询 action 表后得到 shift；根据状态 3 + 栈顶 ( 得到下一状态 4（记录 <(, 4>）；故转换至新状态 4；

• 根据状态 4 + 输入 int，查询 action 表后得到 shift；根据状态 3 + 栈顶 int 得到下一状态 5（记录 <int, 5>，注意和前面已被合并的 <int, 1> 是两回事了）；转换至状态 5；

• 根据状态 5 + 输入 )，查询 action 表后得到 reduce E -> int，注意！这个时候，只需要退回到目前栈顶 ( 存放的状态，即 <(, 4>，就是状态 4 并将 E 入栈。再次地，由于我们知道 reduce 结果是 E 在栈顶，因此可以在入栈前查询 goto-table “状态 4 + 栈顶 E”，转移结果是状态 6，因此记录 <E, 6> 后 reduce 入栈，并直接到状态 6；

  这个时候相当于 4 就是栈中其他所有 symbol 的最终状态；

• ……

2.4.4 Constructing LR Parser DFA

现在的问题还是，如何构建这个 LR(1) 的二维表/DFA？

我们先引入 LR(1) item 的概念：$[X\to \alpha \cdot \beta ,a]$$[X\rightarrow\alpha\cdot\beta,\space a]$；这个 item 描述了 DFA 当前的所有状态以及下一个阶段的信息：

• $X\to \alpha \cdot \beta$$X\rightarrow\alpha\cdot\beta$ 中，$\alpha$$\alpha$ 是栈顶的 symbol，$X\to \alpha \cdot \beta$$X\rightarrow\alpha\cdot\beta$ 是我想要 reduce 的 production；

• 当前输入的 terminal（look ahead terminal）需要是 $\beta a$$\beta a$ 的前缀；

• $a$$a$ 指在 $\alpha \beta$$\alpha\beta$ 成功从 input 中 retrieve（也就是 $\cdot$$\cdot$ 移动到 production 末尾）后，希望接下来的 input 只有是什么 terminal，才能规约（为什么这么突兀地定义一个 $a$$a$？）；

为了描述方便，我们约定一个 trivial case：

当栈为空的时候，我们目标很明确，就是规约成 $E\mathrm{\$}$$E\$$ 的最终状态（$E$$E$ 为这个语言 CFG 的 start symbol），为了表达这个意愿并用 LR(1) item 描述（方便生成 DFA），我们定义新的 start symbol：$S\to \cdot E\mathrm{\$}$$S\rightarrow\cdot E\$$；

这样就能用 LR(1) item 来描述 DFA 状态了。我们举个例子：

• 假设某时刻 LR(1) parser 的状态用 $[E\to E+\cdot (E),+]$$[E\rightarrow E+\cdot\space(E),\space +]$ 来表示，则如果 input 是 (，则 shift；

• 假设某时刻状态 $[E\to E+(E)\cdot ,+]$$[E\rightarrow E+(E)\space\cdot\space,+]$，则如果 input 是 +，则 reduce；

现在我们知道 $\cdot$$\cdot$ 后面 input 是 terminal 时的行为；但如果在期望的 production 中，$\cdot$$\cdot$ 后面是 non-terminal，那应该怎么处理和当前栈顶、input（input 总不会是 non-terminal）的关系表示呢？

还有，我们现在还没搞懂后面缀的一个 “+” 是怎么得出来的？别急，继续向下看。

例如假设某时刻的状态 $[E\to E+(\cdot E),+]$$[E\rightarrow E+(\cdot E),+]$，应该怎么办？答案是将 $E$$E$ 按 production 展开，分裂为两个 LR(1) item，就像 DFA 的一个状态根据 input 不同指出去两个状态结点一样。现在期望的状态就会变为：

• $[E\to \cdot \text{int},)]$$[E\rightarrow\cdot\space\text{int},\space)\space]$；

• $[E\to \cdot E+(E),)]$$[E\rightarrow\cdot E+(E),\space)\space]$；

哦！原来是用类似递归的方式来描述当前 parser 的状态，后面缀的部分其实是递归上一层的解析器的解析要求！

我们把上面的操作定义为 Closure Operation，我们认为，对一个 LR(1) item 的闭包操作如下：

xxxxxxxxxx
procedure Closure(items):
# 这步骤称为闭包的原因就是它会不停地在集合中按照某种方式运算
# 并加入结果，直至结果稳定

repeat util items is unchanged:
    for [X -> a.Yb, w] in items:
        # 对每个下一个是 non-terminal 的 item
        for each production Y -> r:
            # 用对应的 production 展开，并以 First(bw) 讨论情况加入后缀
            for b in First(bw):
                items += [Y -> .r, b]

现在，我们需要构建一个 LR Parser 的理论工具已经准备完全了。接下来我们完整地走一遍构建流程。

1. 初始状态栈为空，状态 $[S\to \cdot E,\mathrm{\$}]$$[S\rightarrow\cdot E,\space\$]$；

2. 由于 $\cdot$$\cdot$ 下一元素是 non-terminal，故计算当前所有 items 的闭包：

   $$\begin{array}{rl}S& \to \cdot E,\mathrm{\$}\\ E& \to \cdot \text{int},\mathrm{\$}\\ E& \to \cdot E+(E),\mathrm{\$}\\ E& \to \cdot \text{int},+\\ E& \to \cdot E+(E),+\end{array}$$

   经过两轮计算后，上述结果稳定，也就是上述 items 为 Closure({S -> . E $})；可以将相同前缀合并同类项（例如：$E\to \cdot \text{int},\mathrm{\$}/+$$E\rightarrow\cdot\space\text{int},\space\$/+$）；

   我们定义：

   • 一个 items 闭包就是一个 DFA 的状态，因此上述 items 就是 DFA 的真正的状态 0（把一开始没求闭包的状态称为 partial state）；

   • 对一个闭包上的所有 $[X\to \alpha \cdot ,b]$$[X\rightarrow\alpha\space\cdot,\space b]$ 情况，会在 DFA 状态结点上标记 “reduce with $X\to \alpha$$X\rightarrow\alpha$ on $b$$b$”；

     其中 $[S\to E\cdot ,\mathrm{\$}]$$[S\rightarrow E\space\cdot,\space\$]$（其中 $S$$S$ 为新的起始符号，$E$$E$ 为原先的起始符号）的情况应该称为 “accept on $\mathrm{\$}$$\$$”；

3. 得到当前 DFA 状态 0 后，考虑 transition：将状态中的所有 items 的 dot 向后推进一位，根据推进的 symbol 绘制出一条出边；进而得到下一状态的 partial state；形式定义如下：

   xxxxxxxxxx
   procedure Transition(State, Y):
   # 不同的 Y 会指向不同的状态结点
   
   items = {}
   for [X -> a.Yb, w] in State:
       items += [X -> aY.b, w]
   return Closure(items)   # 表示最后求闭包才能从 partial state 转变为真正的状态
   

4. 重复第二步的 “求闭包” 得到真正状态以及 reduce 标记、重复第三步 “绘制 出边”，（合起来就是 Transition）直至状态绘制完全。

下面是一个完整实例：

由 DFA，借助之前的知识，我们能够轻松地将其转换为二维表。

也就是说，上述一长串过程（从 CFG 到 LR Parsing Table），全部都可以自动化生成；

2.4.5 Problem I in LR Parsing Table: Shift/Reduce Conflicts

按照上述方法生成的二维表能直接用来作为 LR Parser 了吗？可惜还有点小问题。

考虑一种情况，如果一个 DFA 状态中同时含有 $[X\to \alpha \cdot a\beta ,b]$$[X\rightarrow\alpha\cdot a\beta,b]$ 和 $[Y\to \gamma \cdot ,a]$$[Y\rightarrow\gamma\space\cdot,\space a]$，那么究竟是听前者（“input 是 a，赶紧 shift”），还是听后者（“input 是 a，赶紧 reduce $Y\to \gamma$$Y\rightarrow\gamma$”）？这就是 Shift/Reduce Conflicts。

出现这种情况，原因大多是 CFG 存在二义性。

例如我们之前举过的例子：

$$\begin{array}{rl}E& \to \text{if }E\text{ then }E\\ & |\text{if }E\text{ then }E\text{ else }E\\ & |\dots \end{array}$$

它在生成 Parsing Table 时，就会有如下情况存在一个状态结点中：

$$\begin{array}{rl}S& \to \text{if }E\text{ then }S\cdot ,\text{ else}\\ S& \to \text{if }E\text{ then }S\cdot \text{else }S,x\end{array}$$

我们可能需要对这种情况的默认行为，于是在某些工具（如 bison）中，默认行为就是 shift。

不过回想一下前面说，我们可以通过添加约束/声明来消除二义性，比如在下面的二义性文法中：

可能出现 $[E\to E\ast E\cdot ,+]$$[E\rightarrow E*E\space\cdot,\space+]$ 和 $[E\to E\cdot +E,+]$$[E\rightarrow E\cdot+E,+]$；

我们在 bison 中添加结合性声明，以及基于先后的优先级声明（统称为 directives），来消除二义性：

xxxxxxxxxx
%left +
%left *

那这是怎么实现的？以 Bison 为例，它约定，如果出现 shift/reduce conflict，则：

1. 检查所有 directives 中给定的优先级。input terminal 和 rule（指需要 reduce 的 rule）的优先级更高就遵从谁的。item 的优先级取决于其 production 右侧的最后一个 token（terminal）；

2. 如果优先级相同，则检查 directives 中的结合性，如果 input terminal 是右结合的，则执行 shift；左结合反之；

   为什么 input terminal 右结合的话 shift？

   考虑一个情况：$[E\to E\cdot +E,+]$$[E\rightarrow E\cdot+E,+]$ 和 $[E\to E+E\cdot ,+]$$[E\rightarrow E+E\space\cdot,+]$，此时由于是左结合，所以应该尽可能早地与前面的 “+” 运算，也就是先 reduce；

3. 如果没有涉及优先级的 directives，则也执行默认行为（shift）；

2.4.6 Problem II in LR Parsing Table: Reduce/Reduce Conflicts

shift/reduce conflicts 是解决了，但我们发现按照 shift/reduce conflict 的思路查找，还有一个问题。

考虑这种情况：$[X\to \alpha \cdot ,a]$$[X\rightarrow\alpha\space\cdot,\space a]$ 和 $[Y\to \beta \cdot ,a]$$[Y\rightarrow\beta\space\cdot,\space a]$ 同时出现在一个状态中；我们应该按照哪个 rule 来 reduce？这就是 reduce/reduce conflicts；

这种情况还是因为 CFG 的二义性。例如下面的 CFG：

注：$S\to \epsilon |\text{ id }S$$S\rightarrow\varepsilon\space|\text{ id }S$ 和上面的等价而且不会有问题 :(

一方面，比较遗憾的是 reduce/reduce conflicts 在理论上是没办法直接解决的（只能使用 default behavior）；

但另一方面，reduce/reduce conflicts 通常是因为 CFG 写的已经相当不规范了，像上面的例子，我们可以通过简单的等价重构来避免这个问题。

2.4.7 Optimization: LALR(1)

总结一下，我们介绍的 LR Parser 通过 LR(1) item 构造 DFA 和 2D-Table，再利用优先级和结合性声明来消除 shift/reduce conflicts，最终达到解析语法的目的。

但是有个问题是，这样构造的效率还是太低了，像一个简单的语言，LR(1) Parser 就需要大约 1000 个状态结点来构造一个 DFA！所以实践中一般的 parser generator 不这么实现 parser；

我们注意到，LR(1) Parsing Table 虽然很大，但是 DFA 状态结点中的 item 有很多相似的，例如 $[E\to \text{int}\cdot ,\mathrm{\$}/+]$$[E\rightarrow\text{int}\space\cdot,\space \$/+]$ 和 $[E\to \text{int}\cdot ,)/+]$$[E\rightarrow\text{int}\space\cdot,\space)/+]$；

因此，我们可以考虑把同一个状态中只有 lookahead terminal 不同的 items 合并起来：$[E\to \text{int}\cdot ,\mathrm{\$}/)/+]$$[E\rightarrow\text{int}\space\cdot,\space\$/)/+]$；

所以我们定义，一组 LR(1) items 的核心（core）就是这组 items 去除 lookahead terminal 后的 production 的集合；

两个 LR(1) Parser 的 DFA 状态结点可以合并，就当且仅当这两个状态结点的 core 是相同的。我们称合并后的状态结点为 LALR(1) state（Look-Ahead LR(1) state）；

将 LR(1) DFA 中所有状态都尽可能合并完（直到所有 state 的 core 都两两不再相同），最终得到 LALR(1) DFA；

虽然 LALR(1) 可以显著减少 DFA 状态，但是它也会引入 reduce/reduce conflicts 的问题。例如：

两个状态 $\{[X\to \alpha \cdot ,a],[Y\to \beta \cdot ,b]\}$$\{[X\rightarrow\alpha\space\cdot,\space a],\space[Y\rightarrow\beta\space\cdot,\space b]\}$ 和 $\{[X\to \alpha \cdot ,b],[Y\to \beta \cdot ,a]\}$$\{[X\rightarrow\alpha\space\cdot,\space b],\space[Y\rightarrow\beta\space\cdot,\space a]\}$，在合并后变成 $\{[X\to \alpha \cdot ,a/b],[Y\to \beta \cdot ,a/b]\}$$\{[X\rightarrow\alpha\space\cdot,\space a/b],\space[Y\rightarrow\beta\space\cdot,\space a/b]\}$；

但幸运的是，这样的情况几乎不会发生（除非人为构造一个奇怪的语言），也就是说只要是一个符合人类习惯的正常语言都不会出现这个问题，我们称这种语言为 LALR(1) Language，就像 admissible heuristic function 大多数情况下都有 consistent 性质一样。

于是，LALR(1) 就成为一种语言、parser generator 的事实标准。

现在我们已经完全搞清楚了如何自动生成 parser 了。只要再加上 error handling 就能实现一个 parser generator 来帮助我们生成一个 LALR(1) Parser 了；

注：这个 parser 如何生成最终要输出的 parse tree，在已经了解算法的情况下就很好办了，只要在解析的中途从下到上利用 non-terminal 和 terminal 在 shift 以及 reduce 阶段顺便构建一个 parse tree 的数据结构就行。

2.4.8 LR(1) Error Handling

和 Top-Down Parser 一样，遇到错误后我们有两种方案：

• Error Throwing：立即停止并报出错误（可能会因为连续的简单的错误反复重新编译）；

• Error Recovery：记录错误并报出，但尝试继续解析（可能因为一处错误导致报出一系列其他错误）；

这两种方案都有点问题，不过实践中用第二种比较多。

在 Error Recovery 中又有 3 种调整方式：

• delete tokens；

• insert tokens（可能出现无穷循环问题）；

• substitute tokens；

以及两类使用方式：

• local recovery：在错误发生的位置调整；

• global recovery：在错误发生之前的位置调整；

Local Recovery & Delete Tokens

先讨论 local recovery - delete tokens 这种组合。

借鉴 Top-Down Parsing 的错误处理思路，在遇到错误 token 的时候 skip（也就是 delete）到下一个目标 token 处，这个目标 token 就是我们想要的 synchronizing token，就是让 parser 状态重新恢复到正常的必要步骤。

在 Top-Down 中使用的 synchronizing token 实际上是栈顶 $X$$X$ 的 $\text{Follow}(X)$$\text{Follow}(X)$；而在 Bottom-Up Parsing 中，鉴于解析方式不同，我们应该向 CFG 中插入错误情况的规则，例如对下面的 CFG：

我们应该加入如下 Error Recovering CFG：

这样出现错误时就能恢复了。举个例子，加上在上面的 CFG 前提下，遇到的输入以及栈的状态：

NUM PLUS ( NUM PLUS |> @#$ PLUS NUM ) PLUS NUM

下一步发现这个 token 是 $\text{error}$$\text{error}$，则需要开始 pop stack，直至当前状态匹配 Error Recovering CFG，如下：

NUM PLUS ( |> @#$ PLUS NUM ) PLUS NUM

这里 pop stack 相当于抛弃了那些 tokens；

到这里开始发现可以匹配 $exp\to (\underset{―}{\text{error}})$$exp\rightarrow(\underline{\text{error}})$ 了，于是按照这条 grammar 一直 shift，并持续 discard 有效 token 直至能够把 $\text{error}$$\text{error}$ 规约掉（无条件）：

NUM PLUS ( @#$ PLUS NUM ) |> PLUS NUM

此时栈中的状态是：exp PLUS (error)，规约为：exp PLUS exp，然后状态恢复正常，继续 parser，实现了 Error Recovering；

Global Recovery

global recovery 的策略常常使用一个被称为 “Burke-Fisher error repair” 的实现；

Burke-Fisher error repair 思想如下：

Tries every possible single-token insertion, deletion or replacement（尝试了所有 3 中调整方式）at every point in the input up to K tokens before the error is detected;

e.g. : K = 20: parser gets stuck at token 500; all possible repairs between token 480-500 tried;

best repair = longest successful parse;

其实现方法就是维护两个栈，第二个栈保留第一个普通栈 reduce 后的原始 token（方便出现问题后在 K 个 token 长的滑动窗口中查找问题），也就是第二个栈比第一个栈晚 K 步而已；

于是可能的尝试有 N + 2k * N 个：delete tokens（K）、insertions（(K+1) * N）、replacement（K(N-1)）；

这样的开销在错误处理的情况下是可以接受的。

2.5 Yacc: The tool to generate parsing table from CFG

现在我们已经掌握了基本的语法分析的知识了，这节介绍实践中如何使用一个别人写好的 parser generator；

一个比较常用的 parser generator 就是 yacc，能够在你指定 CFG 和优先级、结合性声明后自动化生成一个 parser。

也就是说，Yacc 之于语法分析器，就像 Lex 之于词法分析器。

附注：Lex、Flex、Yacc、Bison 究竟有什么关系？

• Lex 和 Flex 都是词法分析器，但是 Flex 是在 Lex 基础上发展起来的（Flex is the successor of Lex）；

  • 不过它们的 rules file format 有所差别，前者允许自己的代码控制词法分析器，而后者更严格一点；

• Yacc 和 Bison 都是语法分析器，但是 yacc 更早出现，而 Bison 是 GNU 对 Yacc 的另一种替代的开源实现；

  • 它们的 rules file format 也有差别；

总的来说，Flex 和 Bison 是 GNU 开源免费的，Lex 和 Yacc 是 Unix SVRx licenses 下可以自定义商用的版本；

我们一般学习建议使用 Flex & Bison 组合；

摘自 Bison and Yacc；

Chapter 3. Semantic Actions & Semantic Analysis

本章内容额外摘自：

Synthesized & Inherited Attributes - GeeksForGeeks；

Attribute Grammar - Ques10；

3.1 Where we are now?

我们再次回顾一下 Compiler 设计的各个阶段（简化版）：

我们前两章已经完成了词法分析（lexical analysis）和语法分析（syntax analysis 或 grammar analysis），能够成功地抽象出程序的语法结构，并且以 parse tree 的形式给出语法分析的结果（即程序关于 Context-Free Grammar 的层次结构），证明了程序是符合 CFG 的约定的。

但是，只考虑 context-free 的东西是不行的，是没办法正确地编出一些程序的。

举个例子：int a = "I am a string";，这种语句它能正确地通过词法分析和语法分析，但实际上它是有问题的。那你说它究竟违反了哪一条 Context-Free Grammar？答案是并不违反。

所以，要定义一个高级语言，除了词法、上下文无关文法的约定以外，还需要另一种抽象的约定，用来限制上面的 “上下文相关”（Context-Sensitive）的信息。

这个 “上下文相关的约定”，人们将其称为 “Semantic Rules”，要解析这些约定，就要借助 compiler 的下一个阶段的工作：语义动作 & 语义分析（Semantic Actions & Semantic Analysis）；

而 CFG 和 Semantic Rules 这两种约定合称为 “Syntax Directed Definitions”（简称 语法制导定义，将语法和语义结合起来定义）。只有将语法（grammar/syntax）和语义（semantic）结合起来，才能较为全面地描述一个语言。

思考：为什么既然在 semantic analysis 阶段，需要把语法和语义一起考虑，那为什么 compiler 设计的时候不直接一股脑全放到 parser 中，合并起来，让 parser 直接生成 Abstract Syntax Tree（能同时描述语法和语义的数据结构）不行吗？

因为，这样的设计是通过大量的实践得出的。如果把二者合成一个阶段，则耦合性上升、可配置性就下降了。

对于不同的语言的编译器，我可能需要写很多重复的模板代码（boilerplate code），这是人们不喜欢的，而且会增大错误几率和调试成本。

因此人们为了高度可定制化、代码重用性以及高度模块化，从更高的抽象层级上把 Syntax/Grammar 和 Semantic 拆开分析。

 

实际情况是，为了省事（因为还是需要把 CFG 和 Semantic Rules 放在一起的，如果物理上写成两个程序就不好实现了），人们把这两个阶段合起来（但思想上还是有两个阶段），使用一个工具来完成上述语法分析、语义分析的任务。这就是 Bison。我们在本章末尾介绍它的使用方法。

3.2 Semantic Rules, Attribute Grammar, Abstract Syntax Tree

那么所谓的 semantic rules 究竟怎么约定上下文相关的信息？

首先我们要知道 “上下文相关信息” 究竟是什么：

• 语义值（semantic value）：就是这个 token 的“通俗意义上的”值，例如 int a = 1; 这里假设有个 token type 是 DIGIT，那么在 parse tree 中 1 所代表的结点 token type 是 DIGIT；而它的语义值就是 1 本身；

  一般这个信息应该由 parser 存放在 semantic value stack 上，以供后续语义分析等环节使用。

  non-terminal 也是有 semantic value 的，例如在一个交互式解释器 / 计算器中，一个表达式 expression 的语义值就是一个数字；在一个编译器中，一个表达式的语义通常是描述这个表达式结构的树结构；

• 作用域（scope）信息：典型需要结合上下文得知的信息。它可以体现在：

  • 某些语言会定义一些作用域，不同的作用域下变量的使用情况？

  • 如何发现某些变量在定义前被引用？

• 类型（type）信息：对于一个静态类型语言，编译器可以在语义分析的阶段拿到并分析 terminal 的具体类型，以此判断这种语义是否正确；

  文章开头的类型错误的例子就需要这种信息来识别；

• ……

这些上下文信息构成的语义也被称为 “static semantics”，意为能在编译阶段（compile-time）就能得知的上下文信息。相对的是 “运行时上下文”，它的正确性只能由编程人员自行保证，编译器在整个编译阶段都不会管理。

总而言之，semantic rules 就是在描述这些上下文信息怎么从 parse tree 上被获得、怎么解析和计算。

那么相对地，我们需要严格的、形式化的方法来定义这些 “上下文相关信息”，这就是 attribute grammar：它描述为了明确语义，对于一个 symbol 我们需要哪些上下文信息、如何组织这些信息。

Attribute Grammars define what semantic information is needed and how it is structured, while Semantic Rules define how this information should be computed or derived during parsing and compilation.

In other words:

• Attribute Grammars provide a framework that extends CFGs by associating attributes with grammar symbols and specifying rules for attribute computation;

• Semantic Rules operate within this framework to dictate how those attributes are computed for each production rule in the grammar.

而为了形式化、准确地定义上下文相关信息，Attribute Grammar 本身就是一种形式语言，它和 正则表达式 一样，本身都是一种上下文无关文法，用来描述上下文有关的信息。

它的做法是，向 parse tree 中的 non-terminal 定义一些上下文相关信息的类型（这里被称为 “attributes”），然后利用 semantic rules 去在 parse tree 上解析、运算这些 attributes 的值（value）。semantic rules 可以定义一些 side effects（例如打印一些内容、更新一些 global variables 等），在运算过程中可以顺便执行。当我们利用 attribute grammar 和 semantic rules 充分解析了 parse tree，在 parser tree 的基础上，我们抛弃掉不必要的 non-terminal，在树上点缀上下文相关的信息，会构建出一棵能够描述代码“几乎”全部含义的抽象语法树（Abstract Syntax Tree，AST）（其实也是利用 semantic rules），这步就是 Semantic Action（语义动作）；

注 1：现在还有些上下文相关信息，例如类型检查、作用域关系没有处理；

注 2：如果是这里编写的是直接运算出结果的计算器，或者解释型语言的交互型解释器（REPL），又或者是没有优化的解释器（Interpreter），那么 semantic action 阶段就可以直接执行指令了，这个时候有 side effects 就比较重要了；

注 3：有一部分学者，以及教授此课的臧老师，都将 semantic action 归于 syntax analysis（语法分析），并认为语法分析阶段产出 AST，其实也没有问题，只是设计上的微小差别。更何况实际情况就是 Bison 工具一起处理了语法分析和语义动作。

最终，还需要执行类型/作用域等等上下文信息的补充，并得到一些附加的信息（位于 Environment Table 中）。这一阶段（语义分析，Semantic Analysis）才算真正结束。

3.3 Synthesized Attributes & Inherited Attributes

Attribute Grammar 中将这些 attributes（即上下文相关信息）分为 2 类：Synthesized Attributes 和 Inherited Attributes。

Synthesized Attributes：在 semantic rules 中，总是通过 parse tree 中的子结点的 attributes 计算 / 解析而来的属性。也称 “S-Attributed Definitions”；

这种属性显然对于 Bottom-Up 的解析方法比较友好，也是最常用的 attributes，目前大多数解析 semantic rules 的方法都是通过它来完成。

这样的话，我们进行 semantic analysis 时就可以使用 bottom-up 的方法（称为 “bottom-up evalutation”）。

Inherited Attributes：总是通过 parse tree 中的父结点 / 兄弟结点的 attributes 计算 / 解析而来的属性。

这种属性一般在 top-down evaluation 中才会使用。

3.3.1 Semantic Actions in Bottom-Up Evaluation

Bottom-Up Evaluation 通常和 Bottom-Up Parsing（LR Parser）一起使用。

我们举个例子来阐述用 Bottom-Up Evaluation 来解析 Semantic Rules 的方法。

假设一棵 parse tree 中包含了一个 production $E\to E+T$$E\rightarrow E+T$（为了方便讲解，这里我们记作 $E\to E_1+T$$E\rightarrow E_1+T$，不代表实际的表示方法），如下：

我们对这些 non-terminal 定义一个 synthesized attribute：nptr，记 E.nptr、E1.nptr、T.nptr 分别为指向 AST 中对应结点的指针的值。

这个 attribute 的目的是，为了结合 parse tree 中的语法（CFG）和语义规则（semantic rules），来构建一个 AST 框架。

有了这个 attribute，我们可以将一个 CFG 中的 production 对应一个 semantic rule（创建 AST 的规则），如下：

注意到 $E\to T$$E\rightarrow T$，对应的 semantic rule 为 E.nptr := T.nptr，相对于 parser tree 进行了压缩；

那么还有哪些更多的 attributes（如上面的 .entry / .val）？

另两个 synthesized attribute 定义为 val、lexval，记 terminal.lexval 为这个 terminal 它的实际 token value 的值；记 symbol.val 为这个 symbol 在上下文中实际的值。

这两个 attributes 的目的不言而喻；