自制编译器

开始制作编译器

编译

执行一个gcc命令，实际上其内部经历了如下4个阶段的处理

1. 预处理
2. （狭义的）编译
3. 汇编
4. 链接

   预处理

   C语言的代码首先由预处理器(preprocessor)对#include和#define进行处理。具体来说，读入头文件，将所有的宏展开，这就是预处理(preprocess)。预处理的英文是preprocess,就是前处理的意思。这里的”前”是在什么之前呢？当然是编译之前了。
   预处理的内容近似于sed命令和awk命令这样的纯文本操作，不考虑C语言语法的含义。

   狭义的编译

   接着，编译器对预处理的输出进行编译，生成汇编语言的代码。一般来说，汇编语言的代码的文件扩展名是”.s”

   汇编

   然后，汇编语言的代码由汇编器转化为机器语言，这个处理过程称为汇编
   汇编器的输出称为目标文件。一般来说，目标文件的扩展名是”.o”

   链接

   目标文件本身还不能直接使用，无论是直接运行还是作为library文件调用都不可以。将目标文件转换为最终可以使用的处理称为链接(link)
   例如链接hello.o即可生成可执行文件，生成默认的可执行文件名为a.out

在Java的运行环境中，为了提高运行速度，采用了JIT编译器（Just In Time complier).JIT编译器是在程序运行时进行处理，将程序转换为机器语言的编译器。也就是说Java语言是在运行时进行编译的

编程语言的运行方式

编译器会对程序进行编译，将其转换为可执行的形式。另外也有不进行编译，直接运行编程语言的方法。
解释器就是这样，解释器不将程序转换为别的语言，而是直接运行。例如Ruby和Perl语言处理器就是用解释器来实现的。
一般来说，有静态类型检查(static type checking)、要求较高可靠性的情况下使用编译的方式
相反，没有静态类型检查，对灵活性的要求高于严密性的情况下，则使用解释的方式。
静态类型检查是指在程序开始运行之前，对函数的返回值以及参数的类型进行检查的功能。
动态类型检查在程序运行过程中随时进行类型检查的方式
静态就是指不运行程序而进行某些处理
动态就是指一遍运行程序一遍进行某些处理。

编译过程

狭义的编译可以大致分为下面4个阶段

1. 语法分析(syntax analyzing)
2. 语义分析(semantic analysis)
3. 生成中间代码
4. 代码生成

   语法分析(syntax analyzing)

   

   语义分析(semantic analysis)

   解析语法树，出去多余的内容，添加必要的信息，生成抽象语法树(Abstract Syntax Tree, AST)这样一种数据结构。
   语义分析包括以下这些处理

• 区分变量为局部变量还是全局变量
• 解析变量的声明和引用
• 变量和表达式的类型检查
• 检查在引用变量之前是否进行了初始化
• 检查函数是否按照定义返回了结果

syntax analyzing生成的语法树只是将代码的构造照搬了过来，而semantic analysis生成的抽象语法树中还包括了语义信息。
例如，在变量的引用和定义之间添加链接，适当地增加类型转换等命令，使表达式的类型一致。
另外，语法树中的表达式外侧的括号、行末的分号等，在抽象语法树中都被省略了。

生成中间代码

将抽象语法树转化为只在编译器内部使用的中间代码(Intermediate Representation, IR)
之所以特地转化为中间代码，主要是为了支持多种编程语言或者机器语言。


例如GCC使用的是一种名为RTL(Register Transfer Language)的中间代码
当然，根据编译器的不同，也存在不经过中间代码，直接从抽象语法树生成机器语言的情况
解析代码转化为中间代码为止的这部分内容，称为编译器的前端(front-end)

代码生成

将中间代码转换为汇编语言，这个阶段称为代码生成(code generation)。负责代码生成的程序模块称为代码生成器(code generator)
一般来说，比起编程语言，汇编语言在使用上的限制多一些。例如，C和java可以随心所欲地定义局部变量，而汇编语言中能够分配给局部变量的寄存器只有不到30个而已。处理流程控制方面也只有和goto语句功能类似的跳转指令。

语法分析的方法

词法分析、语法分析、语义分析

一般来说，语法分析可以细分为一下两个阶段

1. 词法分析
2. 语法分析
   词法分析(lexical analyze)就是将代码分割成一个个的单词，也可以成为扫描(scan)。举例来说，词法分析就是将x=1+2这样的程序分割为”x” “=” “1” “+” “2”这样5个单词。并且在该过程中，会将空白符和注释这种对程序没有实际意义的部分剔除。正因为预先有了词法分析，语法分析器才可以只处理由意义的单词，进而实现简化处理。
   负责词法分析的模块称为词法分析器(lexical analyze),又称为扫描器（scanner)
   本书制作的Cb编译器的词法分析为独立的模块，但语义分析的一部分将放在语法分析的模块中来实现。

token

在编程语言处理系统中，我们将“一个单词（的字面）”和“它的种类” “语义值”统称为token。通过使用token这个词，词法分析器的作用就可以说是解析代码(字符行)并生成token序列

抽象语法树和节点

编程语言的编译器中解析器的主要作用是解析由扫描器生成的token序列，并生成代码所对应的树形结构（即语法树)。确切的说，也有方法可以不需要生成语法树，但这样的方法仅限于极小型的编译器。
语法树和语法是完全对应的，所以例如C语言的终结符分号以及表达式两端的括号等都包含在真实的语法树中。但是，保存分号和括号基本没有实际的意义，因此实际上大部分情况下会生成一开始就省略分号、括号的抽象语法树。也就是说，解析器会跳过语法树，直接生成抽象语法树。
无论语法树还是抽象语法树，都是树形的数据结构，因此和普通的树结构相同，由称为节点(node)的数据结构组合而成。用java来写的话，一个节点可以用一个节点对象来表示。

解析器生成器

只需指定需要解析的语法，扫描器生成器和解析器生成器都能生成解析相应语法的代码
cbc使用javaCC工具来生成扫描器和解析器。javaCC兼具扫描器生成器和解析器生成器的功能，因此能够在一个文件中同时记述扫描器和解析器


cbc选择javaCC作为解析器生成器的原因

• 具备了所必须的最低限度的功能
• 运行生成的解析器时不需要专门的库
• 软件的实现比较成熟
• 生成的代码还算是可读

相比较LR解析器和LALR解析器生成器，它有着可处理语法的范围相对狭窄的缺点
但另一方面，javaCC生成的解析器有易于理解、易于使用的优势。
另外因为支持了”无限长的token超前扫描”,所以可处理语法范围狭窄的问题也得到了很好的改善。

JavaCC

javaCC的正则表达式

扫描标识符和保留字

javaCC会同时尝试匹配所有的正则表达式，并选择匹配字符串最长的规则
如voidFunction会生成IDENTIFIER的token而不是VOID的token
如果和多个规则的正则表达式匹配的字符串长度相同，例如void f(),和VOID token以及IDENTIFIER token的正则表达式都匹配void这4个字符
像这样和多个规则的正则表达式匹配的字符串长度相同的情况下,javaCC优先选择在文件中先定义的token规则。
也就是说，如果VOID token规则卸载IDENTIFIER token规则之前，那么生成VOID token。而如果IDENTIFIER token的规则先定义的话免责生成IDENTIFIER token
所以 ，所有保留字的规则必须写在IDENTIFIER的规则之前

终端符和非终端符

JavaCC将”语句” “函数调用” “表达式”等非token的语法单位成为非终端符(nonterminal symbol),并将非终端符像Java的函数调用一样在后面加上括号，写成stmt()或expr().
终端符可以归纳为token

javaCC的EBNF表示法

javaCC使用名为EBNF（Extended Backus-Naur Form）的表示法来描述语法规则

语法的二义性

if(cond1)
    if(cond2)    f();
	else    g();

EBNF描述

"if" "(" expr() ")" stmt() ["else" stmt()]

javaCC的局限性

事实上，javaCC在遇到用“|”分隔的选项时，在仅读取了1个token的时刻就会对选项进行判断，确切的动作如下所示

1. 读取一个token
2. 按照书写顺序依次查找由上述token开头的选项
3. 找到的话就选用该选项
   也就是说，根据上述规则，javaCC在读取了token时就已经选择了,即选项1. 因此即便写了选项2和选项3，也是完全没有意义的。这个问题称为javaCC的选择冲突(choice conflict)

通常解决方法由2个，一个是提取左侧共通部分，另一个是token的超前扫描

提取左侧共通部分

token的超前扫描

明确指定，javaCC可以在读取更多的token后再决定选择哪个选项。这个功能就称为token的超前扫描(lookhead)

也就是说，读取2 个 token，如果它们是 和 的话，就选用选项 1。同样，第 2 个选项的意思是读取 2 个 token，如果 它们是 和 的话，就选用选项 2。

需要超前扫描的 token个数（上述例子中为 2）是通过共通部分的 token数 +1这样的算 式计算得到的。例如，上述规则中选项之间的共通部分为 ，只有1 个，因此需要超 前扫描的 token 个数为在此基础上再加 1，即 2。

为什么这样能够解决问题呢？因为只要读取了比共通部分的token数多1 个的token，就一 定能读到非共通部分的token，也就是说，能够读到各选项各自特有的部分。经过了这样的确认 后再进行选择就不会有问题了。

最后的选项（选项 4）不需要使用 LOOKAHEAD。这是因为 LOOKAHEAD 是在还剩下多个选 项时，为了延迟决定选择哪个选项而使用的功能。

可以省略的规则和冲突

如果内侧的if语句的else部分没有省略，则else部分属于内侧的if语句，如果省略的话则属于外侧的if语句。

• 未使用LOOKAHEAD进行判断的规则描述：
• 使用LOOKAHEAD来避免冲突发生的规则： 判断方法本身非常简单。通过添加LOOKAHEAD(1),就可以指定”读取1个token后，如果该token符合规则（即如果说是)则不省略 stmt()”。这样就能明确else始终属于最内侧的if语句，空悬else的问题就可以解决了。

重复和冲突

重复的情况下会发生“是作为重复的一部分读入还是跳出重复”这样的选择冲突。

在这个规则中，表示可变长参数的”,” “…”不会被解析。
根据上述规则，在读取type（）后又读到”,”时候，本来可能是 “,” type()也可能是 “,” “…”的，但 JavaCC默认向前只读取 1 个 token，因此在读到 “,”时就必须判断是继续 重复还是跳出重复。并且恰巧 “,” 和 (“,” type()) 的开头一致，所以 JavaCC 会一直判断为 重复 (“,” type())*，而规则 “,” “…” 则完全不会被用到。实际上如果程序中出现 “,” “…”，会因为不符合规则 “,” type() 而判定为语法错误。

要解决上述问题，可以如下添加LOOKAHEAD

这样javaCC在每次判断该重复时，就会在读取2个token后再判断是否继续重复，因此在输入了 “,” “…” 后就会因为检测到和 “,” type() 不匹配而跳出 (“,” type())* 的重复。

更灵活的超前扫描

指定读取符合这个规则的所有token

用超前扫描来分析上述规则，读取“恰好n 个”token是行不通的。原因在于共通部分 storage() type() 中存在非终端符号 storage() 和 type()。因为不知 道 storage() 和 type() 实际对应几个 token，所以无法用读取“恰好 n 个”token 来处理。

这里就需要使用刚才提到的“读取符合这个规则的所有 token”这样的设置。上述规则中选 项间的共通部分是 storage() type() ，因此只要读取了共通部分加上 1 个 token，即 storage() type() “;”，就能够区别 2 个选项了。将规则进行如 下改写。

如上所示，只需在 LOOKAHEAD的括号中写上需要超前扫描的规则即可。这样利用超前扫 描就能够顺利地区分 2 个选项了。

超前扫描的相关注意事项

即便写了LOOKAHEAD也并非一定能按照预期对程序进行分析。添加LOOKAHEAD后 Choice conflict的警告消息的确消失了，但实际上JavaCC不会对 LOOKAHEAD描述的 内容进行任何检查。在发生选择冲突的地方加上LOOKAHEAD后不再显示警告，仅此而已。 LOOKAHEAD 处理的描述是否正确，我们必须自己思考。

表达式的整体结构

表达式的结构是由层次的。原因在于表达式中所使用的运算符存在优先级(precedence)
例如二元运算符 + 和 之间 的优先级高，所以 1+23 的运算顺 序是 1+(23)，42-3 的运算顺序是 (42)-3。以语法树来说，+ 总 是在上层（靠近根节点），而 * 则位于下层（图 6.2）。

一般来说，越是离语法树的根节点近的符号，其解析规则越是先出现。（这里的“先”是指，从compilation_unit()跟踪调查规则时，会较早地出现在跟踪到的规则中。

换言之，就是可以从优先级低的运算符的规则开始，按照自上而下的顺序来描述表达式的规则。