在 Assembly 86x 中创建和实现抽象语法树

Question

所以我最近开始学习汇编语言，但我在创建抽象语法树 (AST) 然后在汇编中实现它们时遇到了麻烦。所以假设我有这个等式：z = (3 - 2*x)*x - 2*y + 1。那么下面的 AST 是否正确，因为我知道有多个答案，每个答案在实现上都不同？

                             =
                            / \
                           -   *
                          / \   \
                         *   3   *
                        / \     / \
                       2   x   -   +
                              / \  / \
                             x   2 y  1

从那里开始，我将如何在我的代码中实现它（如果树是正确的）？不幸的是，我不知道从哪里开始。提前致谢。

Answer 1

你需要设置栈和队列（后进先出和先进先出的内存块）。您还需要操作的优先级（BEDMAS -（^/*+-= 是一个好的开始，但快速搜索 Web 将为您提供最多 16 个不同操作员的不同优先级）。现在循环你的表达式：

如果是一个值，将其添加到队列
当堆栈上有更高优先级的操作时，将其移至队列末尾。
将操作添加到堆栈。

当所有参数完成后，取出堆栈的剩余部分并将其添加到队列的末尾。

队列现在处于逆波兰方向 - value1、value2、op 所以你的例子是

2,x,*,3,-,{right hand branch},=

因为这是一个无效的左手运算符，它会失败但暂时忽略它并继续。对于队列中的每个项目：

如果是一个值，将其压入堆栈。
如果是运算符，则对堆栈顶部的项目执行操作，然后 return 将值放回堆栈。
最后的结果会留在栈上。

所以在这种情况下，堆栈将变为：

 - {empty}    ; 2
 - 2          ; x
 - 2,x        ; *(multiply top 2 items on stack and push result)
 - {2x}       ; 3
 - {2x},3     ; -(subtract top 2 items on stack and push result)
 - {2x-3}     ; (final result)

Answer 2

操作 AST 的应用程序通常不小，用汇编程序编写它们的好处不大。你最好用一种更高级的语言来编写 AST 操作，这样你就可以编写更容易处理树的代码。（有关推动 AST 操作的工具，请参阅我的简历）。

如果你坚持，那么关键问题就是定义一个AST节点结构。实际上，它应该：

按住parent和children links
持有节点类型
持有字面值值
适合缓存行

（这些约束来自我们的工具操作的非常大的 AST）。

如果您坚持使用 MASM-x86，则以下结构定义可能是合适的：

  ASTNODE STRUCT
  NodeType dword ?     ; holds type of AST node
  LiteralValue dword ? ; holds child count, literal value or pointer to big literal value, as indicated by the type
  Parent  dword ?
  Children dword ?
  ASTNODE ENDS

[您可以轻松定义 MASM-x64 的等效项。如果你不知道怎么做，你不应该这样做。]

我们假设有很多AST节点类型，为了区分语句、运算符、操作数、标识符……所以我们需要区分它们，因此NodeType。

基于Node，字面值包含（假定互斥情况）： * 没有（没有必要） * children的个数，如果节点类型是列表节点 * 一个文字常量，如果节点类型是一个持有小值的叶子 * 指向文字常量的指针，如果节点类型是用于保存文字值大于 32 位的叶子 * 指向标识符字符串或符号 table 条目的指针，如果节点类型为 "identifier"

"Children"槽比较特殊：它本质上是一个指向其他AST节点的动态指针数组。对于许多 AST 节点类型，children 的数量是隐式已知的；您可以在节点类型上使用 table 查找，或者代码可以 "know"。对于列表节点，children 的数量需要与文字字段指定的列表长度相匹配。

任何小于4的节点children都适合32个字节，并且应该相应地对齐。超过 4 children 的节点应该 cache-line 对齐。

您仍然需要构建一个解析器，它必须通过填充指针字段来创建节点 link 它们在一起。

我想你会发现用 AST 构造构建一个解析器需要做很多工作（尤其是在汇编器中），然后你需要构建一些对树执行某些操作的东西。

在 Assembly 86x 中创建和实现抽象语法树

Creating and Implementing Abstract Syntax Tree in Assembly 86x

assembly

x86

abstract-syntax-tree