Table of contents
Open Table of contents
Introduction
存在两种翻译的模式，一种是编译，一种是解释. 解释器有更大的灵活性，运用了延迟约束（late binding）的方法，而编译器一般能带来更好的性能，也就是编译优化. 区别在于彻底的分析和非平凡的变换.
但实际情况是许多语言采用两者的混合，由源程序经过一个翻译器（可能是解释的，也可能是混合的）得到中间语言 IR，然后 IR 和输入一起进入虚拟机得到输出. 这是一种比较笼统的界定，具体情况各不相同.
编译的阶段：
- 词法分析 Lexical and Syntax Analysis
- 将单词组织为一棵语法分析树 parse tree
- 部分组合使用递归的规则定义则称上下文无关语法 context-free grammar
- 语义分析 Semantic Analysis 与中间代码生成 Intermediate Code Generation
- 追踪标识符的表达式的类型
- 通常需要构造并维护一个符号表 symbol table
- 并非所有语义规则都能在编译时检查，区分了静态语义和动态语义
- 静态语义中语义分析器通常把语法分析树转换为（抽象）语法树 AST
- 许多编译器里带标注的语法树就是从前端传递到后端的中间形式
- 目标代码生成 Target Code Generation
- 优化 Optimization
Programming Language Syntax
记法：
digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
non_zero_digit -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
natural_number -> non_zero_digit digit*
语法与语义的关系就像能指与所指的关系.
Specifying Syntax: Regular Expressions and Context-Free Grammars
就如同记法中所展示的，我们使用了拼接、选择和 Kleene 星号共三类规则，基于这三种规则定义出的字符串集合都成为正则集或正则语言，显然这是由正则表达式生成加之由扫描器识别的.
如果我们加上递归这一条规则，就称之为上下文无关语言 CFL，由上下文无关文法 CFG 定义，由语法分析器识别. 此处讨论的都是形式语言，一个形式语言意味着只是字符串的集合。没有附加其上的语义.
上下文无关文法里的一条规则成为一个产生式，左部的符号成为变量或非终结符，右侧的符号成为终结符. 这种记法有时被成为 Backus-Naur 形式 BNF. 也存在扩充的 BNF 即 EBNF.
在推导语法分析树时有可能产生歧义，这是因为替换策略不同所导致的语法分析树不唯一. 最右推导（也称规范推导）与最左推导显然是不一样的，所得到的产出式（仅由终结符构成）就不一样. 推导一颗语法分析树，以文法的开始符号为根，所有树叶构成其产出式，非根节点表示一次产生式应用.
例如表达式 3 + 4 * 5 在词法分析时先要根据产生式 expr -> term | expr add_op term 做 expr -> expr add_op term，由此得到的是 term + term，与先运算乘法的优先级是相反的. 做过 NJU PA 的友友应该都考虑过这一点.
Scanning
扫描器（Scanner，或称词法分析器 Lexer）和语法分析器（Parser）的目的在于发现程序的语法结构，通常是抽象语法树 AST. 这两者之间的区别在于，Lexer 生成 Token 序列，而 Parser 将 Token 序列生成为语法树 Parser Tree 或抽象语法树 AST.
用一种更结构化的方式构造 Lexer，我们会得到一个有穷自动机 DFA. 有穷自动机确实可以手写，不过使用扫描器生成器来帮助构建是一个更常用的方法. 一般而言，典型的扫描器生成器通过三个连续步骤实现正则表达式到 DFA 的变换：
- 将正则表达式变换为非确定性有穷状态机 NFA
- 将 NFA 翻译为一个等价的 DFA
- 产生一个状态数最少的 DFA 即做空间优化
这里我认为橡书《编译器设计》的讲解好于 PLP. epsilon 转移意味着状态机可以在不读取任何符号的情况下从一个状态跳转到另一个状态，例如我们有一个 a* 和 ab 的 FA，我们就可以通过一个 epsilon 转移将其合并得到 a*ab. 采用橡书中的定义：
- NFA 是允许空串输入 epsilon 上进行转移的 FA，其状态对于同一字符输入可能有多种转移
- DFA 不允许 epsilon 转移，即转移函数为单值的 FA
从正则表达式变换为 NFA 的方法称为 Thompson 构造法，PLP 和橡书在此处的讲解大差不差.
从 NFA 变换到到 DFA 使用子集构造法，其核心思想是用 DFA 的一个状态包含 NFA 在某时刻可能出于的状态的集合，这里 PLP 用一个例子简单讲述了（图 2.9），橡书针对其实现讲了很多，此处先跳过这些细节.
最小化 DFA 的方法 PLP 用其强大的注意力得出了（图 2.10），实际上是基于等价类的划分. 划分的方法 Hopcroft 算法在橡书里详细解释了.
理论结束，从实现的角度来说，我们可以使用嵌套 case 语句或者利用一些程序生成一个表格，称表驱动扫描. 嵌套 case 语句实现 Lexer 看起来还是挺暴力的，和直接写状态机代码是类似的，似乎可以理解为直接编码的一种方法. 表驱动法我的理解是每次读入输入字符后检查读入的字符信息，然后再去查表，显然可维护性和扩展性是更好的，确实表驱动也是工业标准. 这里 PLP 的划分和橡书差异较大，毕竟是概览成分更多.
Parsing
TO BE CONTINUE.