22

我已经有了创建标记列表的标记器接口。我有解析器的工作机制。它真的很独特，就像一个魅力。我唯一想念的是 AST 的基本结构。树、节点和语句应如何在抽象级别表示。我不需要任何实现，只需快速了解它在类层次结构中的外观如何？我正在研究一种面向对象的语言。是的，我已经意识到我需要两种类型的陈述。一些返回值的“表达式”类型语句和一个不返回的指令流控制类型语句。非常感谢。

4

1 回答 1

20

如果您的语言是命令式/类 c 语言，那么常见的场景是从顶层层次结构分为 2 个超类型开始：

  • 表达
  • 陈述

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

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

一个典型的场景如下所示：

  • 语句块（语句列表）
  • 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，仅静态类型就足够了，如果您还计划实现一些后端，则还需要一些动态类型）。

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

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

于 2013-08-12T14:04:41.247 回答