代码之家 › 专栏 › 技术社区 › ShadowViper

在程序集86x中创建和实现抽象语法树

abstract-syntax-tree x86 assembly

ShadowViper · 技术社区 · 9 年前

所以我最近开始学习汇编语言,在创建抽象语法树(AST)并在汇编中实现它们时遇到了困难。假设我有一个方程式: z = (3 - 2*x)*x - 2*y + 1 。那么,下面的AST是否正确,因为我知道有多个答案,每个答案的实现都不同?

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

从那里,我将如何将其实现到代码中(如果树是正确的)?不幸的是,我不知道从哪里开始。提前感谢。

2 回复 | 直到 9 年前

Ira Baxter 9 年前

操纵AST的应用程序通常不小,用汇编程序对它们进行编码几乎没有好处。您最好使用更高级的语言编写AST操作,在那里您可以更容易地编写处理树的代码。(请参阅我的个人简历,了解推动AST操作的工具)。

如果你 坚决要求 ,则关键问题是定义AST节点结构。作为一个实际问题,它应该:

保持父级和子级链接
保留节点类型
保持文字值
适合缓存线

(这些约束来自我们的工具所操纵的非常大的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,文字值包含(假设互斥情况): *没有(不需要) *子节点数,如果节点类型是列表节点 *如果节点类型用于具有小值的叶,则为文字常量 *指向文本常量的指针,如果节点类型用于具有大于32位的文本值的叶 *指向标识符字符串或符号表项的指针,如果节点类型为“identifier”

“Children”槽很特殊:它本质上是指向其他AST节点的指针的动态数组。对于许多AST节点类型,子节点的数量是隐式已知的;您可以在节点类型上使用表查找,或者代码可以“知道”。对于列表节点,子节点的数量需要与文本字段指定的列表长度相匹配。

任何少于4个子节点的节点都可以容纳32个字节,并且应该相应地对齐。具有4个子级以上的节点应与缓存线对齐。

您仍然需要构建一个解析器,它必须创建节点并通过填充指针字段将它们链接在一起。

我想你会发现用AST构造构建一个解析器需要很多工作(尤其是在汇编程序中),然后你需要构建一些用树做的东西。

Mike 9 年前

您需要设置堆栈和队列(后进先出和先入先出内存块)。您还需要操作的优先级(BEDMAS-(^/*+-=是一个很好的开始,但快速搜索Web将为不同的操作员提供多达16个不同的优先级)。现在循环浏览您的表达式:

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

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

队列现在处于反向波兰方向-value1,value2,op,因此您的示例如下

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

由于这是一个无效的左手运算符,它将失败,但暂时忽略它并继续。对于队列中的每个项目:

如果它是一个值,请将其推到堆栈上。
如果是运算符,则对堆栈上的顶部项执行操作,并将值返回堆栈。
最终结果将留在堆栈上。

因此,在这种情况下,堆栈将:

 - {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)