Build Compiler with LALR(1) Parser Generator(I)

其实从几年前开始就一直想着自己写个编译器，不管是用LLVM编译成native code还是基于自己写的VM。起因不仅仅是因为写个编译器很“酷”，它还是很多东西的基础——比如游戏引擎，Machine Learning时的配置文件(因为很多Parameters是需要动态改变的)。之前已经试过数次，但都因为各种各样的原因放弃了。几年过去，现在又萌生了这个想法，反正都要从头来，干脆把这些都记录下来，就算再扔掉也不会从零开始。

之前曾经用过flex+yacc，也手写过LL(1)的Parser，但我并不喜欢C语言，也不打算折腾个底朝天，因为最近一直在用D语言，恰好DLang里有LALR(1)的Parser Generator - dunnart.于是以此为基础来试一试。

如果你不了解D语言，也不需要担心，它的语法很像C/C++，比如一个最简单的Hello,World:

import std.stdio;
void main(string[] args){ 
    writeln("Hello, World!"); 
    return; 
}

如果后面遇到特殊的语法，我也会尽量解说。

顺带说一句，现在几乎所有主流语言都是C-Based，而Pascal系已经几乎看不到了，如果硬要说的话，Object Pascal/Delphi还能在每个月的TIOBE排名中看到，但却很少出现在实际应用里。唯一还能用到的似乎就是Ada了吧。

好吧，扯远了，回到正题上来。在这里我们会尝试用dunart构建一个能够运行的玩具语言，至少能够生成自己定义的VMCode，然后运行在一个最简单的虚拟机里。然后给它提供一个类似extern的keyword，让我们能够执行在host端注册过的函数，至少这样就可以拿它来写游戏脚本或者配置文件了。不过不要期待能很快实现，因为我压根不是这方面的行家，或者说，我压根不懂编译器和语言设计。因此一切从实际出发，只要最终的成品能够完成任务，我们不需要在意定义能不能满足Turning-complete，也不在意在我们的语言是否有Funarg Problem。

总之先从一个最简单的例子开始，首先会构造一个计算器，它能够计算加减乘除，然后我们会渐渐的向里面添加功能，包括注释，复数，Array Programming, 变量，函数, 以及类似Slot的东西来模拟object-oriented programming。

现在看代码，这是dunnart自带的例子，你可以在dunnart的Github Repo里找到它。

parser.ddgs :

%{
    double result = 0;
    double evaluate(string text){
%}

%field  double value

%token          PLUS    "+"
%token          MINUS   "-"
%token          TIMES   "*"
%token          DIVIDE  "/"
%token  <value> NUMBER  ([0-9]+(\.[0-9]+){0,1})
%token          LPR     "("
%token          RPR     ")"

%skip   ([ \n\t\r]+)

%right  UMINUS
%right  UPLUS
%left   "*" "/"
%left   "+" "-"

%%
program: expr !{ result = $1.value; !}.

expr: expr "+" expr !{$$.value = $1.value + $3.value;!}
    | expr "-" expr !{$$.value = $1.value - $3.value;!}
    | expr "*" expr !{$$.value = $1.value * $3.value;!}
    | expr "/" expr !{$$.value = $1.value / $3.value;!}
    | "(" expr ")" !{$$.value = $2.value;!}
    | "-" expr %prec UMINUS !{$$.value = -$2.value;!}
    | "+" expr %prec UPLUS !{$$.value = $2.value;!}
    | NUMBER !{$$.value = $1.value;!}
    .

%{
    dd_parse_text(text);
    return result;
}
%}

看起来是不是跟flex+yacc几乎一模一样？整个文件主要有两部分，它们之间用%%隔开，其中上半部分是lexer，下半部分是parser。而%{ %}所包围的区域会被原封不动的拷贝到目标文件中。让我们从头开始分析：

%{
    double result = 0;
    double evaluate(string text){
%}

这一段里的东西会被直接拷贝到目标文件里, 在原例子里result是个local var，这里我们把它移到外面，因为现在我们还没有变量，result暂时用来在运行期间保存结果。

%field  double value

%token          PLUS    "+"
%token          MINUS   "-"
%token          TIMES   "*"
%token          DIVIDE  "/"
%token  <value> NUMBER  ([0-9]+(\.[0-9]+){0,1})
%token          LPR     "("
%token          RPR     ")"

在这一段里定义了一个lexer，任何输入的内容都会首先通过这个lexer变成Token Stream。比如对于输入：

1 * 2 + 3

在通过lexer后会变成：

NUMBER TIMES NUMBER PLUS NUMBER

显然，在这里所有的字符串都变成了Token，但如何知道NUMBER的值呢？ %field就是为此设置的。在scan的过程中，如果一个Token设置了field，那么获得的字符串会被自动转换为对应的类型。比如我们需要以字符串形式记录PLUS的值，那么只要做如下改变：

%field double value
%field string ident

%token <ident> PLUS "+"
....
%token <value> NUMBER ....

这样当scanner遇到"+"时，对应的值会被储存在ident里面。当然在这里没有任何意义，但在后面我们需要添加labels，或者identifiers的时候，这会是个很重要的内容。所有的Tokens都是通过正则表达式来定义的，因此熟悉的人可以很轻松添加新的Tokens。

%skip   ([ \n\t\r]+)

%right  UMINUS
%right  UPLUS
%left   "*" "/"
%left   "+" "-"

至于这一段，相信意思很明确——skip正如字面意思，用来跳过空白字符，而right和left则跟yacc中的用法一模一样，用来定义Operator associativity。简单的说就是这个operator出现在类似"A + B + C"的环境里时，括号应该添加在哪一侧，而定义的顺序则表示了它们的优先级，定义在先的具有较高优先级，这跟yacc是不一样的，在这里，因为乘除定义在先，因此它们总是先于加减。如果一个operator不需要定义关联性，那么可以用%nonassoc来定义。最后，这里优先级最高的UMINUS和UPLUS定义了unary operator，我们在后面会看到。

总之，到这里为止，我们有了一个简单的lexer，它能够把所有可识别的内容变换成易于处理的Tokens。但显然不够，因为一个语言（计算器）不但需要这些最简单的blocks，还需要把这些blocks粘在一起的Rules。yacc以及派生程序都用Backus-Naur-Form（BNF）作为输入，对于BNF，拿golang的Function Types定义来做例子的话, 看起来就像这样：

FunctionType   = "func" Signature .
Signature      = Parameters [ Result ] .
Result         = Parameters | Type .
Parameters     = "(" [ ParameterList [ "," ] ] ")" .
ParameterList  = ParameterDecl { "," ParameterDecl } .
ParameterDecl  = [ IdentifierList ] [ "..." ] Type .

这里Type以及IdentifierList在别的章节里已经定义过了，简单来说，它指出Tokens（words）如果结合成一个程序（sentences）,并且在定义中是允许递归的。让我们来看看这个计算器的定义：

program: expr !{ result = $1.value; !}.

expr: expr "+" expr !{$$.value = $1.value + $3.value;!}
    | expr "-" expr !{$$.value = $1.value - $3.value;!}
    | expr "*" expr !{$$.value = $1.value * $3.value;!}
    | expr "/" expr !{$$.value = $1.value / $3.value;!}
    | "(" expr ")" !{$$.value = $2.value;!}
    | "-" expr %prec UMINUS !{$$.value = -$2.value;!}
    | "+" expr %prec UPLUS !{$$.value = $2.value;!}
    | NUMBER !{$$.value = $1.value;!}
    .

首先我们定义一个“程序”是由一个expression组成的，并且返回值就是expression的值，而expr则是又下面的东西组成的：

两个expr和一个operator的组合
括号里的expr
unary operator和expr的组合
单个数字

在parsing的过程中， parser会维护一个Stack，每遇到一个新的Token，都会将它Push进这个Stack，这个过程叫做Shift，然后检查是否满足定义里的任何一条，如果满足，则执行预先定义的语句(!{!}里面的内容)。随后所有符合条件的Token都会被取出，然后用一个新的Node替代，这个过程叫做Reduce。在预设的命令当中，比标号从左开始设为1, 然后依次增加，比如对于 expr "+" expr, $1.value代表了第一个expr的值，$2则是加号“+”，而$$则代表Reduce后新节点（表达式）。比如对于：

1 + 2 * 3

经过Scanner，我们得到：

NUMBER PLUS NUMBER TIMES NUMBER

我们用圆点"."来表示当前位置，那么在parsing时：

. NUMBER PLUS NUMBER TIMES NUMBER
        Shift
NUMBER . PLUS NUMBER TIMES NUMBER
        Look Ahead: PLUS/Reduce
EXPR . PLUS NUMBER TIMES NUMBER
        Shift
EXPR PLUS . NUMBER TIMES NUMBER
        Shift
EXPR PLUS NUMBER . TIMES NUMBER
        Look Ahead: TIMES/Reduce
EXPR PLUS EXPR . TIMES NUMBER
        Look Ahead: TIMES(More precedence than +) /Shift
EXPR PLUS EXPR TIMES . NUMBER
        Shift
EXPR PLUS EXPR TIMES NUMBER .
        Reduce
EXPR PLUS EXPR TIMES EXPR .
        Reduce
EXPR PLUS EXPR .
        Reduce
EXPR .

既然名称叫做LALR(1)，我们可以看到它总是在Look Ahead，然后根据这个来确定如何处理当前的Token。我们在scanner里定义的优先级也起了作用，尽管“1+2”已经可以进行Reduce，但因为“*”有更高的优先级，所以需要先处理后半部分的表达式。

最后，不要忘了补全最初定义的函数。

%{
    dd_parse_text(text);
    return result;
}
%}

这样，当我们执行ddpg parser.ddpg时，就会得到一个D语言的module，里面包含了我们定义的函数evaluate，调用它就可以parse输入的内容并且返回执行结果。当然，最后还要提供一个主函数：

import std.stdio;
import std.file;
import std.string;
import parser;

int main(string[] args)
{
    if(args.length == 2){
        writeln(evaluate(readText(args[1])));
        return 0; 
    }
    string line;
    while((line = stdin.readln().strip) !is null){
        writefln("(%s) =>\n\t %s", line, evaluate(line));
    }
    return 0;
}

让我们来执行下简单的运算：

./evaluator
60*60.0*24*365 ↩
(60*60.0*24*365) =>
     3.1536e+07

但是这个程序依然很简陋——只能执行最简单的四则运算，没有循环，没有变量，没有函数，甚至没法自由的获取和使用我们唯一的储存器result。因此在下一章，我们会给它添加变量，输出，并且以此为基础实现一个最简单的图灵完备的语言。