在C++中的抽象语法树表示

Question

在C++中的抽象语法树表示

c++c++11g++

22

我已经有了创建令牌列表的分词器接口，并且已经实现了解析器的工作机制，它非常独特，运行得非常好。我所缺少的只是AST的基本结构，以及如何在抽象层面上表示树、节点和语句的方式。我不需要任何实现，只需要快速了解类层次结构中应该看起来像什么？

我正在开发一种面向对象的语言。是的，我已经意识到我将需要两种类型的语句。一些返回值的“表达式”类型语句和一种无返回值的指令流控制类型语句。

非常感谢。

- Daniel Adamko

我建议研究CLANG/LLVM项目。这是一个非常稳定的开源编译器，具有很多优点。它将帮助您入门，并且通过查看他们的论坛/代码，可以提供比任何人在堆栈溢出帖子中提供的更好的答案。http://clang.llvm.org/docs/InternalsManual.html - MobA11y

2

@ChrisCM：Clang存在一个问题，他们所谓的“AST”实际上是一个“ABT”，也就是绑定（这个标识符在这里被声明，这个变量的类型是X）已经被解析。更容易的方法是使用两阶段算法：1/生成AST 2/解析绑定。 - Matthieu M.

1

这是一个正确的澄清，但我认为在将其用作理解语法树起点时是不必要的。你需要的节点类型、结构、语句等在两种方案中都是相似的，这正是OP感到好奇的地方。 - MobA11y

@MatthieuM 什么是 ABT？ - HelloGoodbye

@HelloGoodbye：这是我知道的用于表示抽象绑定树最好的名称。也就是说，它是一个带有语义信息的AST：名称已经解析，表达式和变量已经类型化... - Matthieu M.

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Lake · Accepted Answer

如果你的编程语言是命令式/C语言风格，通常情况下顶层结构会被分成两个超类型：

表达式
语句

程序是语句列表，每个语句本身都是一个语句。

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

一个典型的场景看起来像:

语句块（一堆语句）
条件语句（if else）
for循环（包括初始化语句列表、检查表达式、增量语句和块）
while循环（类似，但只检查表达式）
变量声明
赋值（包括+= -= ++ --，可以用一个操作符字段、一个左值和一个右值封装在一个类中）
函数调用（返回void）

对于表达式:

Bop（二元操作，任何有两个运算对象和一个运算符的东西，例如 + - * /％ | & && || == <）
Uop（一元操作，任何有一个运算对象和一个运算符的东西，例如~！）
函数调用（非void类型）
条件表达式（exp? true val : false val）

有这两个抽象（表达式和语句）的好处是在所有类中，您将拥有抽象类型，并能够使用访问者模式访问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而言，仅静态类型就足够了；如果要实现一些后端，还需要一些动态类型）。

如果您不打算支持需要大小信息的定长数组，则通常可以使用一些枚举指定静态类型。如果您想要带有大小的定长数组，则可以为类型实现一个类，并使数组类型包含额外的大小信息。

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，它将持有包含有关运行时内存信息的堆栈/堆。此时，您需要将值与其类型信息一起存储。