C++ 中的抽象语法树表示 [英] Abstract Syntax Tree representation in C++
问题描述
我已经有了创建标记列表的标记器接口.我有解析器的工作机制.它真的很独特，就像一个魅力.我唯一想念的是 AST 的基本结构.树、节点和语句应如何在抽象级别表示.我不需要任何实现，只需快速了解它在类层次结构中的外观如何?我正在研究一种面向对象的语言.是的，我已经意识到我需要两种类型的陈述.一些返回值的表达式"类型语句和一个不返回的指令流控制类型语句.非常感谢.
I already have the tokenizer interface which creates a list of tokens. I have the working mechanism for the parser. It's really unique and works like a charm. The only thing that i miss is the basic structure of the AST. How the tree, the nodes and the statements should be represented on abstraction level. I don't need any implementation only a quick idea how should it look like in class hierarchy? I'm working on an object-oriented language. Yeah, i already realized that i will need two types of statements. Some value returning "expression" type statement and a non-returning, instruction flow controlling type statement. Thank you very much.
推荐答案
如果你的语言是命令式/c-like，常见的场景是从顶层结构被分成 2 个超类型开始:
If your language is imperative/c-like, the common scenario begins with top-hierarchy being split in 2 supertypes:
- 表达式
- 声明
程序是一个语句列表，它本身就是一个语句.
The program is a list of statement, which is a statement itself.
您可能希望拥有一个扩展语句基类的语句类型类.
You will probably want to have one class for type of statement that extends the statement base class.
一个典型的场景是这样的:
A typical scenario looks like:
- 语句块(语句列表)
- ite (if then else)
- for(一个 for 循环及其初始化语句列表、检查表达式、增量语句和块
- while(类似，但只检查表达式
- 变量声明
- 赋值(包括 += -= ++ --，您可以使用运算符字段、lval 和 rval 将所有内容包装在一个类中)
- 函数调用(空一)
对于表达式:
- Bop(二元运算，任何有 2 个操作数和 1 个运算符，即 + - */% | & && || == <
- Uop(一元运算，任何有 1 个操作数和 1 个运算符，即 ~ ！)
- 函数调用(非空函数)
- 条件表达式(exp ? true val : false val)
拥有这 2 个抽象(表达式和语句)的好处是，在您的所有类中，您将拥有抽象类型，并且将能够使用访问者模式访问 AST.
The good thing of having this 2 abstractions (expressions and statements) is that inside all your classes, you will have abstract types, and will be able to visit the AST with the visitor pattern, for example.
例如，一些类看起来像这样(伪代码):
For example, some classes would look like this (pseudocode):
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，仅静态类型就足够了，如果您的项目还需要实现一些后端，那么您还需要一些动态类型).
Also, you will need some way to represent types (for the AST, just static types are enough, if you project to implement some back-end as well, you will need some dynamic types too).
如果您不打算支持需要大小信息的固定大小数组，通常可以使用一些枚举指定静态类型.如果你想要固定大小的数组，大小，你可以实现一个类型的类，并让数组类型保存额外的大小信息.
Static types can usually be specified with some enumerations, if you don't plan to support fixed-size arrays which need a size information. If you want fixed-size arrays with, size, you can implement one class for type and have the array type hold additional size information.
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 实例，例如当用户声明一个变量时.如果您计划在将来进行静态类型检查，您也可以使用相同的层次结构.
You will then instantiate one StaticType instance for every type in the AST, for example when the user declares a variable. You will be able to use the same hierarchy if you plan to do static type-checking in the future, also.
至于以 AST 形式运行/解释代码，您将需要一个 Memory 来保存包含有关运行时内存信息的堆栈/堆.此时，您需要将值与其类型信息一起存储.
As for running/interpreting the code in the AST form, you will need a Memory which will hold a stack/heap containing information about runtime memory. At that point you will need to store values together with their type information.
这篇关于C++ 中的抽象语法树表示的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
