1

我正在用 C++ 实现一种编程语言，我正在进入 AST 生成阶段。

我想使用一个三步程序：

  1. 识别语句的类型；
  2. 将标记与左值右值和节点中的表达式分离为临时和本地 AST；
  3. 设计并将其添加到全局 AST。

例如，这将为声明变量提供以下内容：

var MyVar : integer = 8 + 2;

临时形式（右值/节点/左值）：

left:
    -left:
         "MyVar"
    -node:
         ":"
    -right:
         "integer"
node:
     "="
right:
    -left:
         "8"
    -node:
         "+"
    -right:
         "2"

表示为经典的 AST：

           "="
          /   \
         /     \
        /       \
      ":"       "+"
     /   \     /   \
    /     \  "8"   "2"
   /       \
"MyVar" "integer"

然后，将临时树添加到全局树中，指定声明的类型：

    [EXP]
      |
   VarDecl
      |
   { ... }

这适用于除函数声明和函数调用之外的所有内容：

func add(a : integer, b : integer) : integer;

add(8, 2);

实际上，对于这种类型的表达式，没有节点可以区分左值和右值。我也不知道如何表示函数参数。我曾想过这样的事情：

left:
    "add"
    params:
        [
         -left:
              "a"
         -node:
              ":"
         -right:
               "integer"
        ]
        [
         -left:
              "b"
         -node:
              ":"
         -right:
               "integer"
        ]
node:
    ":"
right:
    "integer"

同上通话：

left:
    "add"
params:
    [
      "8"
    ]
    [
     "2"
    ]

但我觉得如果我这样做，就没有逻辑了。

所以，我想知道是否没有一种方法可以接近我的方法来改进它，或者我的方法是否必须完全修改。

PS：我在抽象语法分析和树领域还比较陌生，但是我已经阅读了很多关于这个主题的文档和教程。

4

1 回答 1

3

首先，我建议您研究用于 C++ 或其他解析器生成器的 bison/flex，因为您可以更轻松地将语句分组到树结构中。

对于您的函数参数问题，AST 不仅仅是左节点。您可以在一个节点下有多个（> 2）个分支，并将这些分支视为它们的语法表达式而不是文字字符。这就是词法分析器提供帮助的地方，因为您可以将字符抽象为标记，然后解析器会将标记抽象为语法结构。一般来说，任何类似的东西都a : integer应该被抽象成一个语法结构，可能叫做类型化声明。

真的func add(a : integer, b : integer) : integer;是这样

func identifier(params) : returnType

AST 中的节点可以跟踪具体信息。

也就是说，您的 AST 应该使用“字符”或“令牌”，但内部节点应该对语言的语法结构进行抽象。特别是对于参数列表，我建议将其作为逗号分隔的类型声明列表，然后 params 节点将有一个子声明节点列表。

同样从您关于将语句添加到全局树的声明中，将其视为将语句添加到 AST 的全局列表可能更有用。

无论如何，这是一个奇怪的答案，希望它有所帮助。

于 2018-08-13T17:56:09.883 回答