折腾一个编译器（语法分析篇）

MyLang编译器大致可以分成三个部分：

语法分析器MyParser；
语义分析器libBlock；
后端，我们在大作业中使用的是基于LLVM的代码生成器。

本篇的主角是语法分析器MyParser。MyParser沿用了MyLang的“My”命名，但它在更大程度上是一个独立的库，用于生成自顶向下Parser。它由两部分组成，分别是Parser生成器和C++库。

语法规则文件

MyParser使用带有特殊格式的Markdown文件记录语法规则。

下面看一个简单的例子：

 1 **space**:
 2 
 3     <space regex>
 4 
 5 *space regex*:
 6 
 7     [ \t]*
 8 
 9 **keyword**:
10 
11     <id>
12     <sign>
13 
14 *id*:
15 
16     [a-z]+
17 
18 *sign*:
19 
20     [,.!]
21 
22 greet:
23 
24     hello
25     goodbye
26 
27 **root**:
28 
29     <greet> <sign> <id> !
30     goodbye <sign> <id> .

好吧，其实不那么简单……

这组语法规则可以接受形如“hello, world!”、“goodbye, bug.”的输入。

我们看到，有一系列冒号结尾的标签，它们表示规则的名称。

MyParser使用的语法规则可以分为列表规则和正则表达式规则。

上例中的一些规则名被星号包围。一个星号在Markdown里表示斜体，在这里表示正则表达式规则；两个星号是粗体，在这里表示“特殊”的列表规则；没有星号的规则名是普通的列表规则。

例如，id规则使用正则表达式[a-z]+，那么它可以接受一串小写字母；greet规则可以接受hello或goodbye。

规则中的一行以四个空格开头。列表规则中，优先匹配靠前的行。仍然以上面的规则为例，如果解析“goodbye, bug.”，会首先尝试root的第一行。发现无法匹配感叹号后，再尝试第二行。

“特殊”的规则只有三条，分别是root、space和keyword。它们都是列表规则。

root是语法规则默认的入口；
space就是空格了。在列表规则中出现的空格都会用它来匹配，<sign> <id> !相当于<sign><space><id><space>!；
keyword是列表规则中的关键字（包括符号）。对于关键字，需要先进行一次使用keyword的匹配，再检查匹配结果是否满足原来的关键字。至于为什么不直接做全字匹配呢？这是为了确保形如for <id>的规则不会匹配以for开头的其它单词，如foreach。

Parser生成器

Parser生成器是一系列Python脚本，读取一个Markdown文件，对规则进行一些检查，然后生成一个C++代码文件。

 1 import myparser
 2 import myparser_cpp
 3 
 4 # load rules
 5 parser = myparser.MyParser()
 6 parser.add_file('syntax.md')
 7 
 8 # generate c++ code
 9 gen_file = myparser_cpp.cplusplus_gen(
10     parser.xdump(myparser_cpp.cplusplus_dump),
11     'myparser/',
12     'SYNTAX_HPP'
13 )
14 
15 # write to file
16 syntax_hpp = open('syntax.hpp', 'w')
17 syntax_hpp.write(gen_file)

生成文件的格式大致如此：

 1 template<>
 2 class RuleDef<MP_STR("keyword", 7)>:
 3 public RuleList<MP_STR("keyword", 7),
 4     RuleLine<
 5         RuleItemRef<MP_STR("id", 2)>
 6     >,
 7     RuleLine<
 8         RuleItemRef<MP_STR("sign", 4)>
 9     >
10 > {};
11 
12 template<>
13 class RuleDef<MP_STR("id", 2)>:
14 public RuleRegex<MP_STR("id", 2),
15     MP_STR("[a-z]+", 6)
16 > {};

一个有意思的细节是，Parser生成器本身也是一个编译器，即以带特殊格式的Markdown为输入、以C++代码为输出。这也就意味着它自身带有一个Parser。当然，由于Markdown本身足够简单，MyParser中处理Markdown只使用了正则匹配，并没有做bootstrap。

Parser生成器除了生成C++代码外，也可以模拟执行语法分析，方便编译器开发者对语法规则进行除错。

C++库

MyParser的C++库是完全用头文件配合模板展开完成的。将C++库与Parser生成器生成C++代码文件（也是个头文件）一起include进项目中，就可以使用了。

从上面的例子可以看到，Parser生成器生成的文件大致包含：

RuleDef模板的特化；
语法规则类RuleList和RuleRegex，分别对应列表规则和正则表达式规则；
RuleList中的每一行RuleLine，以及RumeItemRef等成员；
MP_STR宏，用来将字符串传入模板参数。

它们由C++库实现。

先从MP_STR说起。这个宏将字符串如"hello"打散成字符'h', 'e', 'l', 'l', 'o'，然后返回一个编译时字符串类。其中使用的方法比较简单粗暴，展开"hello"[0], "hello"[1], ...而已。我们可以用编译时字符串类给AST（抽象代码树）节点标注类型。

AST节点分为List、Text和Error。

很显然，列表规则生成List节点，Text节点来自正则表达式规则。实现中，RuleList简单地依次调用RuleLine直到找到第一个匹配的；RuleLine依次调用各个成员，并将匹配结果连接到一起；RuleRegex封装了C++11的正则库。

这是一个自顶向下的语法分析过程，类似于LL分析器。

继续使用之前的例子，“hello, world!”会被这样扫描：

 1 hello, world!
 2 ^ <root>
 3 ^ <greet>
 4 ^ <keyword: "hello">
 5 ^ <keyword>
 6 ^ <id>
 7 ^ id: "hello"
 8      ^ keyword: [id: "hello"]
 9      ^ greet: [keyword: [id: "hello"]]
10      ^ root: [greet: [keyword: [id: "hello"]], ...]
11 
12 hello, world!
13      ^ <space>
14      ^ <space regex>
15      ^ space regex: ""
16      ^ space: [space regex: ""]
17      ^ root: [greet, space: [space regex: ""], ...]
18 
19 hello, world!
20      ^ <sign>
21      ^ sign: ","
22       ^ root: [greet, space, sign: ",", ...]
23 
24 hello, world!
25       ^ <space>
26       ^ <space regex>
27       ^ space regex: " "
28        ^ space: [space regex: " "]
29        ^ root: [greet, space, sign, space, ...]
30 
31 hello, world!
32        ^ <id>
33        ^ id: "world"
34             ^ root: [greet, space, sign, space, id, ...]
35 
36 hello, world!
37             ^ <space>
38             ^ <space regex>
39             ^ space regex: ""
40             ^ space: [space regex: ""]
41             ^ root: [greet, space, sign, space, id, space, ...]
42 
43 hello, world!
44             ^ <keyword: "!">
45             ^ <keyword>
46             ^ <sign>
47             ^ sign: "!"
48              ^ keyword: [sign: "!"]
49              ^ root: [greet, space, sign, space, id, space, keyword]

Error节点会被追加到错误的发生地，通常是上一个节点所在的位置之后。MyParser解析过程中，会保留走得最远的Error节点。例如对于：

1 some rule:
2 
3     <some part> <some part> <some part>
4 
5 some part:
6 
7     foo foo bar bar
8     foo

规则some rule匹配“foo foo bar baz”时，可能得到的错误形态有：

some rule: [some part: ["foo", "foo", "bar", <error>]]；
some rule: [some part:["foo"], some part:["foo", <error>]]；
some rule: [some part:["foo"], some part:["foo"], some part:[<error>]]。

那么，当Parser发现不可能正确匹配时，会返回第一种，因为它已匹配的部分最长。

为了继续处理大量不同的AST节点，MyParser包含一个被称为Pass的模块，实现对节点的访问（即“visitor模式”）。MyLang实现中使用它将AST翻译成语义分析所需的中间表示形式。AST格式化输出、语法高亮等功能也是基于这个模块完成的。

MyParser的代码在这里。其中用到大量的C++模板，获得灵活性、运行性能的同时也会增加编译耗时和代码的复杂程度。

>>>>> C++11 Lambda函数闭包的类型与存储形式

<<<<<<