到目前为止，我们已经为解释器写了一个词法分析器和 一个解析器组合子库。在这里，我们会创建抽象语法树（AST）的数据结构，使用组合子库写一个解析器，组合子库可以实现将词法分析器返回的标记列表转换为一个抽象语法树（AST）。
定义抽象语法树（AST）
在我们正式写解析器之前，需要定义清楚解析器输出的数据结构。我们将以类的形式实现这个数据结构。IMP语言的每个语法元素都有一个对应的类。这些类的对象各自代表了抽象语法树（AST）的一个结点。
IMP 中有三种结构：算术表达式（用于计算数字）、布尔表达式（用于为if-else和while语句计算条件）、声明语句。我们将从算术表达式开始，因为另外两种都依赖于它们。
算术表达式可能是下列三种之一：
- 文字型整型常量，比如
42; - 变量，比如
x; - 二进制操作，比如
x+42。
这些组成了其他的算术表达式。
我们也可以用括号将表达式分组，像(x+2)*3。这并不是另一种不同的表达式，而是一种解析表达式的方式。
我们将为这三种形式定义三个类，加上为一般算术表达式定义的基类。现在，这些类除了存储数据并没有太多的功能。包含了__repr__函数，我们就可以在调试时打印抽象语法树（AST）。所有的AST类从继承自Equality，这样我们可以比较两个AST对象是不是相同的。这对于测试很有用。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
from equality import * class Aexp(Equality): pass class IntAexp(Aexp): def __init__(self, i): self.i = i def __repr__(self): return 'IntAexp(%d)' % self.i class VarAexp(Aexp): def __init__(self, name): self.name = name def __repr__(self): return 'VarAexp(%s)' % self.name class BinopAexp(Aexp): def __init__(self, op, left, right): self.op = op self.left = left self.right = right def __repr__(self): return 'BinopAexp(%s, %s, %s)' % (self.op, self.left, self.right) |
布尔表达式有一点复杂。它分为四种：
- 关系式表达（如
x < 10） - 与表达式（如
x < 10 and y > 20） - 或表达式
- 非表达式
关系表达式的左边和右边都是算术表达式。“与”，“或”和“非”的左右两边都是布尔表达式。限制类型可以帮助我们避免类似 “x<10 and 30” 这样的无意义的表达式。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Bexp(Equality): pass class RelopBexp(Bexp): def __init__(self, op, left, right): ... class AndBexp(Bexp): def __init__(self, left, right): ... class OrBexp(Bexp): def __init__(self, left, right): ... class NotBexp(Bexp): def __init__(self, exp): ... |
声明语句既可以包含算术表达式，也可以包含布尔表达式。声明语句也分为四种：赋值语句、复合语句、条件语句以及循环语句。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Statement(Equality): pass class AssignStatement(Statement): def __init__(self, name, aexp): ... class CompoundStatement(Statement): def __init__(self, first, second): ... class IfStatement(Statement): def __init__(self, condition, true_stmt, false_stmt): ... class WhileStatement(Statement): def bole.com/category/feedback/trans-team/">翻译组。 到目前为止，我们已经为解释器写了一个词法分析器和 一个解析器组合子库。在这里，我们会创建抽象语法树（AST）的数据结构，使用组合子库写一个解析器，组合子库可以实现将词法分析器返回的标记列表转换为一个抽象语法树（AST）。 定义抽象语法树（AST）在我们正式写解析器之前，需要定义清楚解析器输出的数据结构。我们将以类的形式实现这个数据结构。IMP语言的每个语法元素都有一个对应的类。这些类的对象各自代表了抽象语法树（AST）的一个结点。 IMP 中有三种结构：算术表达式（用于计算数字）、布尔表达式（用于为if-else和while语句计算条件）、声明语句。我们将从算术表达式开始，因为另外两种都依赖于它们。 算术表达式可能是下列三种之一：
这些组成了其他的算术表达式。 我们也可以用括号将表达式分组，像 我们将为这三种形式定义三个类，加上为一般算术表达式定义的基类。现在，这些类除了存储数据并没有太多的功能。包含了
布尔表达式有一点复杂。它分为四种：
关系表达式的左边和右边都是算术表达式。“与”，“或”和“非”的左右两边都是布尔表达式。限制类型可以帮助我们避免类似 “x<10 and 30” 这样的无意义的表达式。
声明语句既可以包含算术表达式，也可以包含布尔表达式。声明语句也分为四种：赋值语句、复合语句、条件语句以及循环语句。
|
