从字符到抽象语法树的漫长旅程

• 下载源代码 - 7 Kb

引言

在本教程中，您将了解到大多数编译器在将原始源代码形式的程序转换为更易于管理的数据结构（如抽象语法树）时所经历的中间步骤。本教程附带一个解析器的源代码。如果您想一睹我们即将构建的最终产品，可以下载源代码，或者在这里在线尝试：这里。它的基本结构与大多数编译器相同。为了轻松理解本文，您需要具备字符串操作、树（数据结构）和无上下文文法（最好是EBNF符号）的基本知识。

代码是用 JavaScript 编写的，因为它易于原型开发，并且您可以在任何地方找到可以运行您代码的浏览器。您不必过于担心语言本身，因为它是以一种易于转换为任何其他现代面向对象语言的方式编写的。

第一次转换：字符 -> 标记

程序由用户输入为一连串字符。字符都是相等的，完全没有意义——它们只是字符（好吧，有一些语言使用单个字符的指令，但它们很晦涩，通常不用于实际工作）。我们需要将字符组成的字符串划分为一些组合起来更有意义的组。到目前为止，基本构建块是字符，在此阶段之后，我们将得到标记，它们将是下一个阶段的基本构建块。

标记化过程之后，我们将得到，从如下字符串

"fun(x) {return x-5;}"

得到如下标记列表

[identifier(fun), left-paren, identifier(x), right-paren, whitespace, left-curly, keyword(return), ...]

字符是一种基本数据类型，除了其值之外不包含任何内容。然而，标记包含信息（无论是数值还是字符串）以及一些元信息，例如标记的类型。

在字符串 "/*nothing of interest*/" 中，字符 "/*" 用于表示“嘿，后面是注释！”，然后再次使用字符来定义注释内容本身："nothing of interest"。在将此注释转换为标记后，我们将得到一个形式为 [type: comment, content (String): "nothing of interest"] 的数据结构。请注意，"/*" 和 "*/" 在此表示中不出现——它们仅作为元信息。

内容显然将是适合表示它的最佳类型，而不一定是字符串类型。数字标记将具有 [type: fixed-point-number, value (Integer): 3746] 的结构。这次需要从字符串 "3746" 转换为数字 3746，这并不特别，但现在考虑十六进制表示的数字，从 "0x10C" 转换为 268 需要更多的努力。

此外，标记通常只有一个内容/值容器来存储信息，但您可以提出需要更多内容的表示法，例如复数。以 "4r0.9i" 为例；这个标记的结构将是：[type: complex-num, real-part (Float): 4, imaginary-part (Float): 0.9]

需要注意的是，一般来说，标记化后会有尺寸减小。"123456789" 使用 9 个字节，而 123456789 可以很好地放入一个整数（仅 4 个字节）。此外，标记化后，我们可以去除 "/*" 和其他类似的表示法。

一旦我们对代码进行了标记化，我们就可以将其转换回其字符串表示形式（考虑语法高亮）。

一个基本的标记化器（词法分析器）的工作原理如下

1. 开始时，将代码作为字符串，并设置一个索引，以跟踪我们在处理源文件中的进度。

2. 获取一个字符。

2.1 它是空格、制表符或换行符吗？那么，要么将其丢弃，因为它通常没有意义，要么将其添加到标记列表中。

2.2 否则：它是字母吗？然后将控制权交给“字母提取器”，它会“提取”字母（和数字），并在遇到其他东西时返回提取的字母数字字符序列。这个序列将被整齐地包装为“通用标识符”或“关键字”。显然，这个子程序会将控制权交还给通用字符处理器。

2.3 否则：它是数字吗？然后将控制权交给数字生成器。这与上面描述的“字母提取器”的工作方式相同，只是它只喜欢数字，并且可以选择一个点后跟其他数字（浮点数）。

2.4 否则：它是 '"' 吗？然后将控制权交给字符串生成器，它将消耗字符直到遇到另一个 '"'（它会以不同的方式处理前面带有 '\' 的 '"'）。如果在此终止 '"' 之前遇到换行符，则抛出错误。

2.5 否则：它是 '/' 后跟 '*' 吗？这意味着这是一个注释，应该以与字符串相同的方式进行处理。

2.6 否则：它是这些字符之一 ['+', '-', '*', '=', ...] 吗？然后尝试找到最长的匹配受支持运算符的字符字符串。为什么是“最长的字符串……”？ 因为您希望“>=”被翻译为 [Operator(greater-or-equal)] 而不是 [Operator(greater), Operator(equal)]。其他例子包括“>>=”甚至“>>>=”。

2.7 否则：它是语言支持的任何其他内容（单行注释、多行字符串、正则表达式、十六进制数字）吗？然后处理它。

2.8 否则：抛出错误！如果检查了所有可能性但没有找到匹配项，这就是我们能做的。

仍然“/*”似乎可以从两种方式解析。你能澄清一下吗？

当主字符处理器遇到一个可能是不同可能标记起点的字符时，它会进入一个中间状态，并在分析下一个字符后做出决定。"/*" 的特定情况可以按以下方式处理：

if current_char == '/' then
 if next_char == '*' then 
  token += get_multiline_comment()
 else 
  token += get_longest_matching_operator()
else
...

确定当前字符是否是运算符起点的测试应在确定它是注释开头的测试之后进行。如果在此之前处理，它会将 "/*" 标记为 [Operator(/), Operator(*)]。

请注意，这不是标记化东西的最快方法，因为它需要查看未来的字符。此标记化器的结构旨在易于理解，而不是极快。最快的标记化器涉及大量的 goto 而不是“提取器”。

这是我们将要构建的解析器使用的标记化器的源代码。

function Tokenizer() {

}

Tokenizer.chop = function(s) {
    //chop the string of characters into tokens
    var str = new IterableString(s + ' ');
    var tok = [];
 
    while(str.hasNext()) {
        var c = str.cur();
        
        //get an idea of what we're dealing with
        //and give control to specialized munchers
        if(Tokenizer.chop.isDigit(c))
            tok.push(Tokenizer.chop.munchNum(str));
        else if(Tokenizer.chop.isIdHeadChar(c))
            tok.push(Tokenizer.chop.munchAlphanum(str));
        else if(Tokenizer.chop.munchOperator.headList.indexOf(c) != -1)
            tok.push(Tokenizer.chop.munchOperator(str));
        else if(Tokenizer.chop.isWS(c))
            str.adv(); //ignore whitespace
        else throw 'Illegal character: ' + c;
    }
    
    tok.push(new End());
    
    return tok;
}

Tokenizer.chop.isWS = function(c) {
    return c == ' ' || c == '\n' || c == '\t';
}

Tokenizer.chop.isDigit = function(c) {
    return c >= '0' && c <= '9';
}

Tokenizer.chop.isLetter = function(c) {
    return (c >= 'A' && c <= 'Z') 
        || (c >= 'a' && c <= 'z');
}

Tokenizer.chop.isIdChar = function(c) {
    return c == '_' 
        || Tokenizer.chop.isLetter(c) 
        || Tokenizer.chop.isDigit(c);
}

Tokenizer.chop.isIdHeadChar = function(c) {
    return c == '_' || Tokenizer.chop.isLetter(c);
}

Tokenizer.chop.munchNum = function(str) {
    str.setMarker();

    //munch digits
    while(Tokenizer.chop.isDigit(str.cur()))
        str.adv();
        
    //and possibly one '.'
    if(str.cur() == '.') {
        str.adv();
    
        //and some more digits
        while(Tokenizer.chop.isDigit(str.cur()))
            str.adv();
    }
    
    return new Num(str.getMarked());
}

Tokenizer.chop.munchAlphanum = function(str) {
    str.setMarker();
    
    //munch alphanumeric characters
    while(Tokenizer.chop.isIdChar(str.cur()))
        str.adv();
    
    //alphanumeric stuff can only be variable identifiers here
    return new Identifier(str.getMarked());
}

Tokenizer.chop.munchOperator = function(str) {
    //create an alias
    var list = Tokenizer.chop.munchOperator.list;
    for(var i in list)
        if(str.match(list[i]))
            return new Operator(list[i]);
            
    throw 'Unknown symbol sequence';
}
    
//list of all operators 
Tokenizer.chop.munchOperator.list = ['+','-','*','/','(',')'];

//set of first character of every operator
//consequently these two lists match as we don't have lengthy operators
Tokenizer.chop.munchOperator.headList = ['+','-','*','/','(',')'];

我们使用了“IterableString”，它只是 String 的一个包装器，允许添加一些必需的操作。

function IterableString(s) {
    this.s = s;       //the wrapped string
    this.pointer = 0; //keeps track of our current position
    this.marker = 0;  //helps with
}

IterableString.prototype.adv = function() {
    //advances the current position
    this.pointer++;
}

IterableString.prototype.setMarker = function() {
    //updates the marker
    this.marker = this.pointer;
}

IterableString.prototype.cur = function() {
    //get the current character
    return this.s.charAt(this.pointer);
}

IterableString.prototype.next = function() {
    //get the next character
    return this.s.charAt(this.pointer + 1);
}

IterableString.prototype.hasNext = function() {
    //are there any more characters?
    return this.pointer < this.s.length;
}

IterableString.prototype.getMarked = function() {
    //get the substring form marker to the current position
    return this.s.substring(this.marker, this.pointer);
}

IterableString.prototype.match = function(str) {
    //checks if str matches s starting from the current position
    if(this.s.substring(this.pointer, this.pointer + str.length) == str) {
        this.pointer += str.length;
        return true;
    }
    return false;
}

IterableString.prototype.toString = function() {
    var ret = 'IterableString(pointer: ' + this.pointer 
                    + ', marker: ' + this.marker
                    + ', content: [' + this.token.join(', ') + ']';
}

那么，在这个层面上我们可以做什么？

1. 我们可以识别一些错误，例如无效标记，或未正确终止的字符串或注释。

2. 我们可以提供一些语法高亮和自动缩进。更漂亮的语法高亮或自动缩进需要对代码进行更深入的分析。我们无法为变量和函数着色不同的颜色，因为在此阶段我们所知道的关于它们的一切就是它们是“标识符”。此外，我们无法将局部字段与全局字段区分开来，因为标记化器不知道这些概念是什么。当然，我们可以用 L 和 G 来前缀局部变量和全局变量，但这会使语言变得很丑陋，有很多 L 和 G。

3. 我们可以通过删除不必要的空格来重新格式化我们的代码（非常基础的代码压缩器/最小化器）。

4. 我们可以重命名标识符。这会将同名变量视为相同，而不管它们的范围，但至少比使用基本的文本替换要智能。如果我们使用基本的文本替换来重命名变量，可能会得到糟糕的结果。考虑在 "number = 'I like numbers'" 中将 "number" 替换为 "n"。您将得到 "n = 'I like ns'"。但是，如果您使用更智能的重命名工具，允许您在 "number = 'I like numbers'" 中将 Identifier(number) 替换为 Identifier(n)，那么您将得到您想要的，即 "n = 'I like numbers'"。

第二次转换：词法预处理

词法预处理是指可以在标记级别对程序执行的操作。我可以给出的最佳示例是 C 预处理器及其 #define 指令。这些允许用其他标记集替换标记。

C 语言中的预处理非常简洁且有用，因为它有助于创建抽象。然而，如今大多数现代语言都足够灵活，不再需要进一步的抽象，而且它们中的大多数从设计上就是跨平台的，因为它们要么编译成 VM 代码，要么被解释。引用 Stack Overflow 上的 Wood 的话：“（词法）预处理器是一种廉价的方法，以一种丑陋的方式为语言提供不完整的元编程功能。”

注意：一些语言支持“语法预处理”，它对抽象语法树执行操作。这是一种更高级的预处理器，因为它操作的是语法树而不是标记列表。

第三次转换：标记 -> AST

这比上一个更有趣，因为它终于为您的源代码赋予了更高的维度。到目前为止，我们已将扁平的字符序列转换为扁平的标记序列。之后，我们在该序列中进行了一些替换（通过词法预处理）。现在，我们终于要摆脱这个扁平的领域，并以一种更具吸引力的方式表示程序，即一棵树——抽象语法树。

这种更高级别的表示法另一个奇妙之处在于，我们将摆脱大量的标记。当我们从字符转换为标记时，我们摆脱了表示法（"/*"、"*/"、'"'、"0x"）。现在，我们将摆脱描述树结构的标记。

AST 中不需要任何形式的括号。括号、方括号、逗号和分号用于分组和分隔内容，但现在，通过一眼 AST 就可以看到分组——这就是更高维度的意义所在。

构建 AST

有几种构建 AST 的方法，但我将在这里介绍的一种称为“递归下降解析”。

为什么选择递归下降解析？

因为它是最直观、最简单的解析方法。手工编写的递归下降解析器（以下简称 RDP）非常容易编写和维护。当用户出现语法错误时，也很容易向用户提供有意义的错误消息。

现在让我们来看看如何为我们的玩具语言（由简单的算术表达式组成）使用 RDC。首先，我们需要一个好的*文法来描述我们的算术表达式（我稍后会回到这个“好”的度量标准）。我假设您熟悉EBNF符号。

Exp -> Term { ("+" | "-") Term }
Term -> Factor { ("*" | "/") Factor }
Factor -> "(" Exp ")" | Number | Identifier

现在这是解析器实际使用的代码。

function RDP() {

}

RDP.tree = function(t) {
    var token = new TokenList(t);
    var t = RDP.tree.exp(token);
    token.expect(new End(), 'RDP: expression not properly terminated');
    return t;
}

RDP.tree.num = new Num();

RDP.tree.identifier = new Identifier();

RDP.tree.exp = function(token) {
    // Exp -> Term { ( '+' | '-' ) Term }
    var operand = [];
    var operator = [];
    
    operand.push(RDP.tree.term(token));
    while(token.matchAny([[new Operator('+')], [new Operator('-')]])) {
        operator.push(token.next());
        operand.push(RDP.tree.term(token));
    }
    
    //if there's only one operand then we might as well return it without wrapping it
    if(operand.length == 1) return operand[0];
    else return new Exp(operand, operator);
}

RDP.tree.term = function(token) {
    // Term -> Factor { ( '*' | '/' ) Factor }
    var operand = [];
    var operator = [];

    operand.push(RDP.tree.factor(token));
    while(token.matchAny([[new Operator('*')], [new Operator('/')]])) {
        operator.push(token.next());
        operand.push(RDP.tree.factor(token));
    }
    
    //if there's only one operand then we might as well return it without wrapping it
    if(operand.length == 1) return operand[0];
    else return new Term(operand, operator);
} 

RDP.tree.factor = function(token) {
    // Factor -> '(' Exp ')' | Value | Variable
    if(token.match([new Operator('(')])) {
        token.adv();
        var tmp = RDP.tree.exp(token);
        token.expect(new Operator(')'), 'EDP: Factor: missing ")"');
        return tmp;
    }
    else if(token.match([RDP.tree.num])) {
        return new Val(token.next().val);
    }
    else if(token.match([RDP.tree.identifier])) {
        return new Var(token.next().name);
    }
    else throw 'EDP: Factor: Expected either a number, an identifier or a "("';
}

这个递归下降解析器使用了一个类似于 IterableString 的辅助结构。这次它是一个“Iterable Token List”，但我将其命名为“TokenList”。

function TokenList(token) {
    //token list
    this.token = token;
    this.pointer = 0;
}

TokenList.prototype.matchAny = function(token) {
    for(var i=0;i<token.length;i++)
        if(this.match(token[i]))
            return true;

    return false;
}

TokenList.prototype.match = function(token) {
    for(var i=0;i<token.length;i++)
        if(!(this.token[this.pointer + i].match(token[i])))
            return false;
            
    return true;
}

TokenList.prototype.expect = function(token, exMessage) {
    if(this.match([token])) this.adv();
    else throw exMessage;
}

TokenList.prototype.adv = function() {
    if(this.pointer >= this.token.length)
        throw 'TokenList: You\'ve not enough tokens!';
    
    this.pointer++;
}

TokenList.prototype.next = function() {
    this.adv();
    return this.token[this.pointer - 1];
}

TokenList.prototype.toString = function() {
    var ret = 'TokenList(pointer: ' + this.pointer 
                    + ', content: [' + this.token.join(', ') + ']';
}

请注意，这三个函数的结构如何反映了文法的结构。

EBNF -> RDP，总的来说

首先，让我们识别 EBNF 的元素。我们有 4 个运算符：连接（" "）、选择（"|"）、可选（"[ ... ]"）和重复（"{ ... }"）。下面，我将举例说明如何获得执行这些 EBNF 运算符各自功能的代码。

串联

这是一个产生式规则，它描述了大多数语言中常见的 if-then-else 语句的语法。

if-expression -> "if" "(" condition ")" "then" statement-list "else" statement-list

相应的解析子程序将是

function if_expression() {
  expect("if")
  expect("(")
  cond = condition()
  expect(")")
  expect("then")
  stmt1 = statement_list()
  expect("else")
  stmt2 = statement_list()
 
  return new if_expression_node(cond, stmt1, stmt2)
}

选择

这是前面介绍的文法中的另一个规则

condition -> expression relation expression
relation -> "<" | "==" | ">" | "!="

相应的解析子程序将是

function condition() {
  exp1 = expression()
  rel = relation()
  exp2 = expression()
 
  return new condition_node(exp1, rel, exp2)
}

function relation() {
  if(match("<")) return lesser_relation
  else if(match("==")) return equal_relation
  else if(match(">")) return greater_relation
  else if(match("!=")) return notequal_relation
  else throw "Error: invalid relation symbol"
}

重复和可选

考虑用于定义一组变量的规则，其中一些变量可能已初始化。

var-declaration-list -> { var-declaration }
var-declaration -> "var" _IDENTIFIER ["=" _NUMBER] ";"

此文法的相应子程序是

function var_declaration_list() {
  list = []
  while(match("var"))
    list += var_declaration()
 
  return list
}

function var_declaration() {
  expect("var")
  id = get_current()
  advance()
  if(match("=")) {
    advance()
    num = get_current()
    advance()
  }
  expect(";")
 
  return new var_declaration_node(id, num)
}

（我们可以通过定义某种从（非终结符和终结符，ENBF 运算符）到（子程序、某些程序控制语句和指令集）的同态来形式化这一点。）

您可以在 Wikipedia 上找到一个更大的示例。它不包含构建树所需的代码；它只是用于验证代码的语法正确性。

我还想提一下 SEBNF 符号。这极大地简化了从文法到解析器的翻译过程，但代价是需要向文法添加更多规则。您可以通过这个项目找到更多信息。

我能否为任何文法构建一个工作的 RDC？
不。当您开始自己编写文法时，您会很快发现这一点。在定义文法时，您需要处理 2 个问题：

1. 无限递归
以前面示例中定义的文法为例。这不是您在编写算术表达式文法时可能首先想到的方式。让我向您展示一个更直观的文法：

Exp -> Number | Variable
Exp -> Exp ( "+" | "-" | "*" | "/" ) Exp
Exp -> "(" Exp ")"

很容易看出我们是如何得到这个文法的：表达式可以是数字或变量，或者可以重写为两个其他表达式之间的操作，或者可以包装在一对“()”中。但这个文法有一个很大的缺陷：第二条规则会导致堆栈溢出。这是因为 exp() 会在不提取任何标记的情况下调用 exp()。

2. 公共前缀
有时您可能需要向前查看一点。例如，让我们考虑一个只能声明变量或常量的简单语言。可能的文法是：

declarations -> { variable-declaration | constant-declaration }
variable-declaration -> _IDENTIFIER "=" _NUMBER
constant-declaration -> "const" _IDENTIFIER "=" _NUMBER

用这种语言编写的示例“程序”将是：

a = 0, const b = 10, const pi = 5.21, bar = 2

（“a”和“bar”是变量，“b”和“pi”是常量）

declarations() 子程序将继续解析声明，只要它看到标识符（variable-declaration 的第一个“终结符”）或“const”关键字（constant-declaration 的第一个终结符）。因此，declarations() 只需要查看下一个标记就可以确定它应该将解析控制权传递给 variable_declaration() 还是 constant_declaration()。（哦，是的，“const”不是一个有效的标识符，因为它会与具有相同名称的关键字冲突。）

现在让我们让 RDP 的任务更难一些。考虑一个类似的语言，但您将“const”关键字添加到声明的末尾。声明的变量和常量的列表将如下所示：

a = 0, b = 10 const, pi = 5.21 const, bar = 2

（再次，“a”和“bar”是变量，“b”和“pi”是常量）

相应的文法将是：

declarations -> { variable-declaration | constant-declaration }
variable-declaration -> _IDENTIFIER "=" _NUMBER
constant-declaration -> _IDENTIFIER "=" _NUMBER "const"

现在，declarations() 函数无法仅通过查看输入中的当前标记来确定它正在处理常量声明。通过查看第二个或第三个标记也不能。只有通过检查第四个标记，它才能确定这是一个常量声明。

这很不常见。您可以通过感知这个示例看起来有多么“向后”来注意到这一点。为了简单起见，以及为了加快解析速度，大多数使用的语言都具有没有公共前缀的文法。

接近尾声

回到 AST...

现在我们有了 AST，我们应该对其进行一些语义分析。这意味着类型检查和对象绑定等事情。由于我们的语言非常小，它只有一种数据类型，即数字，并且它没有需要绑定的东西。

一旦我们获得了 AST，我们就可以继续通过以下方式之一进行：

1. 执行复杂代码转换并将所有内容重新打包回原始语言（考虑重构）。

2. 将代码翻译成另一个同级语言（这称为转译或源到源编译）。最佳示例是 Coffeescript -> Javascript，Haxe -> 各种。

3. 将代码翻译成低级语言（通常是汇编）；这个过程就是我们传统上称为编译的过程。

4. 直接解释 AST。

这次，首选后一种选择，因为其他选项值得在各自的文章中进行更彻底的讨论。

与我们到目前为止处理的内容相比，求值过程非常简单。一旦我们有了 AST，我们只需要遍历它并跟踪部分结果。

以下是 3 种节点类型及其求值函数：

function Exp(operand, operator) {
    this.operand = operand;
    this.operator = operator;
}

Exp.prototype.evaluate = function(env) {
    var acc = this.operand[0].evaluate(env);
    
    for(var i=1;i<this.operand.length;i++)
        if(this.operator[i-1].match(new Operator('+'))) acc += this.operand[i].evaluate(env);
        else acc -= this.operand[i].evaluate(env);
    
    return acc;
}

Exp 包含对一个或多个带有“+”或“-”的节点的引用。Val 包含一个单独的值。

function Val(val) {
    this.val = val;
}

Val.prototype.evaluate = function(env) {
    return this.val;
}

Var 是一个变量。AST 只知道它的名称。它的值将在运行时从内存（在此称为“环境”）中检索。

function Var(name) {
    this.name = name;
}

Var.prototype.evaluate = function(env) {
    if(!env.container.hasOwnProperty(this.name)) 
        throw 'Interpreter: ' + this.name + ' was not declared in the Environment';
    
    return env.container[this.name];
}

总而言之，本文提出了一个功能齐全的概念验证，演示了将代码从扁平的字符流转换为漂亮的抽象语法树的转换阶段。如文章中所述，有很多内容可以变化和添加。