c++ - C++中的抽象语法树表示

我已经有了创建 token 列表的tokenizer接口(interface)。我有解析器的工作机制。它确实是独一无二的，并且像一种魅力。我唯一想念的是AST的基本结构。树，节点和语句应如何在抽象级别上表示。我不需要任何实现，只是一个快速的想法，它在类层次结构中应该是什么样子？
我正在研究一种面向对象的语言。是的，我已经意识到我将需要两种类型的陈述。一些值返回“表达式”类型的语句和一个非返回的指令流控制类型的语句。
非常感谢你。

最佳答案

如果您的语言是命令式/c语言，则常见的情况是将顶级层次结构划分为2个父类(super class)型:

表达式

声明

该程序是一个语句列表，它本身就是一个语句。

您可能希望为扩展语句基类的语句类型使用一个类。

典型场景如下:

语句块(语句列表)

ite(如果是，则另选)

for(带有其初始化语句列表，检查表达式，增量语句和块

的for循环

while(类似，但仅检查表达式

变量声明

赋值(包括+ =-=++-，您可以使用操作符字段，lval和rval将所有内容包装在一个类中)

函数调用(无效)

对于表达式:

Bop(二进制运算，具有2个操作数和1个运算符的任何东西，即+-*/％|＆&& || == <

Uop(一元运算，具有1个操作数和1个运算符的任何东西，即〜!)

函数调用(非无效)

条件表达式(exp？true val:false val)

拥有这2个抽象(表达式和语句)的好处是，在所有类中，您将拥有抽象类型，并且能够使用访问者模式访问AST。

例如，某些类如下所示(伪代码):

class Ite extends Statement {
   Expression condition;
   Statement ifBranch;
   Statement elseBranch;
}


class Bop extends Expression {
   BOperator operator;  // +, -. * or whatever
   Expression left;     // Left operand
   Expression right;    // Right operand
}


class StatementBlock extends Statement {
   List<Statement> statements;
}


class Assignment extends Statement {
   AOperator assignOp;  // = += -= etc.
   LVal lvalue;         // The lvalue cannot be an arbitrary expression, you will usually have a specific type for it
   Expression rvalue;   // Right value
}

另外，您将需要某种方式来表示类型(对于AST，仅静态类型就足够了，如果您还计划实现某些后端，则也将需要一些动态类型)。

如果您不打算支持需要大小信息的固定大小的数组，则通常可以使用一些枚举来指定静态类型。如果要使用size固定大小的数组，则可以实现一个类型的类，并让数组类型保存其他大小信息。

enum Type {
   CHAR,
   SHORT,
   INT,
   LONG,
   FLOAT,
   DOUBLE,
   ARRAY
}

class Float extends StaticType {
    final Type type = Type.FLOAT;
}

class Array extends StaticArray {
    final Type type = Type.ARRAY;

    int size;
}

然后，您将为AST中的每种类型实例化一个StaticType实例，例如，当用户声明一个变量时。如果您将来也打算进行静态类型检查，则可以使用相同的层次结构。

至于以AST形式运行/解释代码，您将需要一个Memory，该Memory包含一个堆栈/堆，其中包含有关运行时内存的信息。此时，您将需要将值及其类型信息一起存储。

关于c++ - C++中的抽象语法树表示，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/18188612/