Build Compiler with LALR(1) Parser Generator(II)
在上一篇文章里， 我们通过最简单的dunnart自带例子构建了一个计算器，并且对Parser Generator的结构做了说明，不过就像结尾时所说的一样，那个计算器只能进行简单的四则运算，无法保存输出，没有变量，并不怎么让人兴奋。因此，在这篇文章的前半段，我们会对之前的代码进行小小的修改，让它支持变量，然后会尝试让他支持循环——但这个事情并不是那么容易，因此在这次的后半段，会有另外一个小例子来了解下循环的构造。
首先，从上次已经完成的计算器程序开始，我们希望添加变量之后能够实现下面的功能：
a = 1
b = 2
a+b
(Output -> 3)
简单来说就是任何第一次使用并且以字母或者下划线开头的字符串都是变量， 并且只能通过赋值的方式来定义。 现阶段为了例子简单，我们只考虑变量是浮点数的情况。在动手折腾lexer和parser之前，先来定义一个最简单的储存器，它的主要功能是指定一个String之后，能够储存或者读取相应的值。这并不是一个很难的事情，你可以用喜欢的任何Container来实现它，比如HashedList，LinkedList，甚至是RandomAccess的Stack。在这里我选用了最简单的Associative Array(内部实现也是HashedList)：
double[string] list;
在有了这个储存设备之后，就可以真正的着手来添加功能了，首先我们需要定义Identifier的Token：
%field double value
%field string ident
...
%token <ident> ID ([A-Za-z_][A-Za-z_0-9]*)
%token TERM ([;\n])
...
%left "+" "-"
%right "="
%nonassoc TERM
可以看到这里的定义是这样的： 第一个字符只能是大小写字母或者下划线， 后面可以包含数字。这个定义基本上没有跟我们熟悉的变量定义冲突。这里还顺便定义了一个终止符，它可以是分号或者一行的结尾，后面它会用来区分不同的表达式，从而让parser可以一次性执行多个语句。
在定义了Token之后，下一步就是完善Parser，仔细考虑下就会发现一共只有两种情况： 赋值（定义）和使用。 在赋值时，左边只可能是变量，而当变量出现在右边时，他应该跟普通的表达式有着完全相同的作用。把这上面的文字用BNF写出来：
expr: ID !{ $$.value = (($1.ident in list) is null)?0:list[$1.ident]; !}
| ID "=" expr !{ list[$1.ident] = $3.value; $$.value = $3.value; $1.value = $3.value; !}
| expr "+" expr !{$$.value = $1.value + $3.value;!}
....
其他部分则没有任何变化。 让我们再稍微仔细的看下上面两行的定义： 首先如果identifier出现在右边，那么它应当是一个Expression，此时它的值是Variable Table里储存的值， 如果不存在，那么默认它为0。另外，如果ID出现在了左侧，那么只可能是对它赋值，这就是第二行里所定义的东西， 不过需要注意的是，在这里赋值语句也是一个表达式，它会返回等号右边的值，这种定义能够允许诸如“(a=3)+b*4”这种写法，另外在这里虽然有对$1.vaule赋值的语句，但它没有任何意义，因为即使遇到的Identifier，也并不会直接使用ID的value，Reduce时总是会从表里查询实际的值的。
到这里对变量的处理就完成了，不过为了能够一次性执行多个语句， 还需要让lexer里定义的TERM能够发挥作用。在这里然我们用写简单粗暴的方法来实现它：
program: equation.
equation:TERM !{ result = 0; !}
| expr TERM !{ result = $1.value; !}
| equation expr TERM !{ result = $2.value; !}
| equation TERM !{ result = $2.value; !}
.
可以看到在这里定义的program不再是一个expr， 而是一个equation（实际上更“准确”的名字应该是block），而equation则是分号，expr与分号的组合。在实现了这些之后，至少这个计算器就能用不同的语句来操作变量和进行简单的计算了。不过是不是觉得还少些什么？ 对，这个计算器没有输出，直到现在为止都是result变量在做这个工作——但有时候仅仅输出一个变量是不够的，比如我们执行如下语句：
a = 3
b = c = 4
d = a*3+c=b*4+c*5
这时候parser将默认返回d的值，但如果同时希望取得c的值（这将有助于调试operator的优先级），那么就显得不够用了，因此我们还需要一个输出语句，这里定义为“print”。在lexer定义的最后追加这个Token：
%token PR "print"
%skip ([ \t\r]+)
%skip (--[^\n]*\n)
.....
这里我们顺便给计算器追加了注释语句， 任何以"--"开头的语句是一个整行注释，直接将符合条件的正则表达式放进skip语句里即可。而实现输出是非常简单的，只需要在expr的定义最末尾追加一句输出：
expr: ....
| PR expr !{ $$.value = $2.value; writeln($2.value); !}
.
这样当程序遇到类似"print a"的语句时，就会输出它的值了。
到这里，给计算器追加变量的任务就完成了，试着执行一个简单的脚本：
INSERT$ cat test_input
--toaehustohae test file
a = 10
print 10+a
b = 20
print b+a
print (c=10)+b+a
print (d=10)+d*d
(f=e=d+1)
print f
print e
0
INSERT$ ./evaluator test_input
20
30
40
110
11
11
0
可以看到变量已经可以正常使用了。 不过先不要急着高兴，这些元素依然不足以让这个计算器变成一门程序语言，因为至少还需要一个循环才能让这个计算器变得有意义。不过遗憾的是到目前为止，我们接触到的内容还不足以实现一个loop循环——想想看，现在所有的语句都是在触发规则时就已经被执行了，因此每一个节点里只需要储存执行的结果，如果用现在的思想来实现loop，它看起来就像是样：
loop: "while" expr "then" "begin" equation "end" TERM !{ while($2.value) equation; $$.value = $5.value; !}.
我们并没有办法去实际执行expr和equation，而是只能获得他们的结果，自然循环的说法无从谈起。 这个问题的完整解决办法需要在下一章才能实现，在这里，作为导入，先把计算器问题放到一边，我们来实现一个图灵完备的小程序语言——Brainfuck。
Brainfuck是一个很精简的语言，整个语言也不过使用了8个Operator，并且既然是图灵完备那么它就一定在某种意义上实现了递归或者循环，仔细阅读它的Spec就会发现"["和"]"是一个循环结构。现在开始，目标不再是给计算器添加循环，而是实现一个Brainfuck的lexer，parser，并且把它编译成能够在虚拟机里运行的二进制代码。
首先让来人力模拟一下这个程序的执行过程，比如下面的一段小程序：
+[,.]
那么该怎么执行呢？ 显然的，首先把当前位置的内容加1, 然后执行循环里面的内容，对于任何输入都原封不动的输出它， 一直重复到输入值为0………… 看起来似乎很简单， 但是等等， 这里有一个被忽略了的问题： 在执行到"]"时，我们如何才能知道对应的"["在哪里？ 对于手工执行， 这个答案看起来也不难——我们向前查找， 一直到第一次遇到"["，那么它的下一条指令就是对应的循环体。虽然不是怎么高效，但容易理解并且易于实现。在正式的开始实现parser时，不妨先来实现一个具有上述功能的解析器。 用块内存来表示磁带， 用一个指针（或者Array Index）来表示磁头的位置，把所有brainfuck语言翻译成我们使用的高级语言，可以得到：
%{
import std.stdio;
import std.conv: to;
int[] mem ;
int result;
void execute(int[] op){
int ap = 0;
mem.length = 512; mem[] = 0;
while(ap<op.length){
int loopLayer = 0;
switch(op[ap]){
case 0:
result++; break;
case 1:
result--; break;
case 2:
mem[result]++; break;
case 3:
if(mem[result]>0)
mem[result]--;
break;
case 4:
write(mem[result].to!dchar); break;
case 5:
write("Waiting for input: ");
readf("%d\n", &mem[result]); break;
case 6:
if(mem[result]==0)
while(op[++ap]!=7 || loopLayer > 0){
if(op[ap] == 6) loopLayer++;
if(op[ap] == 7 && loopLayer > 0) loopLayer--;
}
break;
case 7:
if(mem[result]!=0){
while(op[--ap]!=6 || loopLayer > 0){
if(op[ap] == 7) loopLayer++;
if(op[ap] == 6 && loopLayer > 0) loopLayer--;
}
}
loopLayer--;
break;
default:
throw new Exception("Unknown Operator");
}
ap++;
}
}
%}
%{
double evaluate(string text)
{
int[] op;
if(text.length == 0) return 0;
%}
%field int value
%token PP ">"
%token PM "<"
%token MP "+"
%token MM "-"
%token PR "."
%token RD ","
%token JF "["
%token JB "]"
%skip ([ \n\t\r]+)
%%
program: expr !{ execute(op); !}.
expr: atom
| expr atom
.
atom: PP !{ op~=0; !}
| PM !{ op~=1; !}
| MP !{ op~=2; !}
| MM !{ op~=3; !}
| PR !{ op~=4; !}
| RD !{ op~=5; !}
| JF !{ op~=6; !}
| JB !{ op~=7; !}
.
%{
dd_parse_text(text);
writeln();
return result;
}
%}
上面的代码描述了一个最简单的解析器， 为了让这个部分跟这个系列的主题——LALR(1) Parser Generator——有点关联，源代码先通过parser解析成了数字，但直接用字符作为输入进行相同的操作也并没有什么不同。注意到这里的Case6和case7，跟之前描述的一样， 每当需要跳转时，我们就会去搜索需要的位置。而对于其他Operator，需要做的就是简单的加减Tape上的记录和移动磁头，这根最初的图灵机是几乎一模一样的。
case 6:
if(mem[result]==0)
while(op[++ap]!=7 || loopLayer > 0){
if(op[ap] == 6) loopLayer++;
if(op[ap] == 7 && loopLayer > 0) loopLayer--;
}
不过还有一个小细节需要注意： 考虑循环嵌套的情形， 比如类似"[>[,.]]"的程序段，如果没有任何约束直接搜索最近的括号，那么对第二个"]"向前搜索时，实际上返回的结果是内层循环的开始——这显然是不正确的。为了解决这个问题，不能仅仅进行简单的搜索， 而是引入一个Loop Layer的概念，它标志这目前所在的循环是第几次嵌套，这样，只查找相同layer的循环，就能够实现括号的配对了。而Loop Layer的维护也非常简单——根据遇到的Operator进行加减即可。
不过在这个程序里， 你会发现我们并没有维护全局的Loop Layer，每次这个变量都会被初始化为0，这是因为这里我们只需要相对Layer就足够了——跟当前括号配对的括号总是0，除此之外别的信息在现阶段没有太大意义。
虽然这个程序看起来很简单，也很不优雅，但他确实具有了执行brainfuck程序的能力， 编译他， 然后执行HelloWorld程序的话：
INSERT$ cat hello.bf
++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.
>.+++.------.--------.>+.>.
INSERT$ ./evaluator hello.bf
Hello World!
4
我们得到了最初的结果，当然，这只是第一步，因为没有人希望自己的程序在每次跳转时都要做一次搜索，那么我们有必要寻找更好的解决办法。一个简单的想法就是把跳转的目标地址放在Operator Code的后面，每当需要跳转，只需要跳转到后面一个Op所指向的位置就可以了。这看起来似乎是个好主意，免去了搜索，并且看起来很容易实现。在这里，为了避免二次编译的问题，我们不会用全局跳转地址，而是采用类似Intel 8088汇编的方式，所有的短跳转都用相对位置来表示。 同时，从现在开始在parser里导入循环的定义：
%{
alias OPList = ulong[];
%}
%{
OPList evaluate(string text)
{
if(text.length == 0) return [];
OPList machineCode;
%}
%field OPList value
%token PP ">"
%token PM "<"
%token MP "+"
%token MM "-"
%token PR "."
%token RD ","
%token JF "["
%token JB "]"
%skip ([ \n\t\r]+)
%%
program: expr !{ machineCode = $1.value; !}.
expr: atom !{ $$.value = $1.value; !}
| loop !{ $$.value = $1.value; !}
| expr loop !{ $$.value = $1.value ~ $2.value; !}
| expr atom !{ $$.value = $1.value ~ $2.value; !}
.
loop: JF expr JB !{ $$.value = [cast(ulong)6]~[$2.value.length]~$2.value~[cast(ulong)7]~[$2.value.length]; !}
.
atom: PP !{ $$.value~=[0]; !}
| PM !{ $$.value~=[1]; !}
| MP !{ $$.value~=[2]; !}
| MM !{ $$.value~=[3]; !}
| PR !{ $$.value~=[4]; !}
| RD !{ $$.value~=[5]; !}
.
%{
dd_parse_text(text);
return machineCode;
}
%}
循环被正式的作为一种结构写入了Parser，而不是完全在执行器（VM）里实现了。虽然写出他的BNF定义不难，不过注意，在之前的小程序里，所有的Operator Code都是直接追加到结果里面的，而循环并不能从前向后的被解析，因为首先循环体需要被Reduce成一个expr才行。如果没一条指令都直接把结果写进返回值里，那么最后得到的将是一堆乱码。
为了解决这个问题，在这里，每一个Node都有一个数组，在自下而上的Parsing过程中，首先每个小元素都会存进数组中， 然后通过合并的方式产生更大的数组， 最后把所有数组片都集合起来， 就是我们的程序。这种做法大大简化了我们的工作量，因为在遇到循环时，"[]"内部的expression已经被解析完毕了，也就是说已经知道循环体的长度，剩下的就是简单的将跳转相对地址存到对应的位置即可。同时也不必担心多层循环——因为每一个"]"总是和最近的"["配对，这个工作会有Parser Generator帮我们完成。最后这个parser的返回值也从double改成了生成的Operator Code，只要把它保存到本地文件，就可以说“编译”成功了。
在有了这个二进制Operator Code之后， 我们的工作就简单多了，之前的解析器绝大多数地方都不需要改变， 需要改变的只有跳转部分：
case 6:
if(mem[result]==0)
ap += op[ap+1]+3;
else ap++;
break;
case 7:
if(mem[result]!=0)
ap -= op[ap+1]+1;
else ap++;
break;
这里可以通过直接设定ap（Array Index）的值来实现循环了。不过相应的，因为记录了多余的内容（跳转地址），因此在执行的时候需要跳过它们。下面是一个求\(n!\)的程序，让我们来测试一下：
>++++++++++>>>+>+[>>>+[-[<<<<<[+<<<<<]>>[[-]>[<<+>+>-]<[>+<-]<[>+<-[>+<-[>
+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>[-]>>>>+>+<<<<<<-[>+<-]]]]]]]]]]]>[<+>-
]+>>>>>]<<<<<[<<<<<]>>>>>>>[>>>>>]++[-<<<<<]>>>>>>-]+>>>>>]<[>++<-]<<<<[<[
>+<-]<<<<]>>[->[-]++++++[<++++++++>-]>>>>]<<<<<[<[>+>+<<-]>.<<<<<]>.>>>>]
:::text
INSERT$ ./compiler fact.bf fact
INSERT$ ./executer fact
1
1
2
6
24
120
720
5040
40320
362880
.......
它会一直执行下去，直到内存溢出。
到此为止，我们实现了一个最简单的图灵完备的语言。虽然它很难看，也没有任何实用价值，但毕竟是第一步。而于此同时，相信肯定会有人想到，除了托管代码之外，有时候还会希望生成本地代码。因此在下一章中，我们会实现一个简单的brainfuck到汇编的转换器，并且用nasm和ld编译成实际可以执行的本地程序，同时，也会导入一些更加“高级”的结构，向着最初的目标——给计算器添加循环——走进一大步。