构建解释器：设计 AST

Question

所以我正在为我正在制作的类似于 Python 的语言制作一个解释器。现在我明白这不是一个小任务，我不希望它工作得很好或做很多事情，但我希望它有一些基本功能（变量、函数、循环、if 语句等......）。

所以目前我正处于解释器获取文件并将其拆分为令牌列表的阶段，现在我准备将这些令牌转换为 AST。我打算用递归下降解析器来做到这一点，我相信我理解，但这就是问题。假设我有以下输入

1 + 2 * 3

这将输出 7，因为使用 BIDMAS 首先完成乘法，所以

2 * 3 = 6

然后添加完成后

1 + 6 = 7

我知道如何获得这个订单，因为我有一个简单的语法，但我不知道如何将其存储为 AST。为了简化答案，我们假设这是您将收到的唯一输入，并且语法可以是

program = add
add = mul {"+" mul}
mul = NUM {"*" NUM}

那么基本上，如何创建一个数据结构来存储 AST？

PS我是用C做的。

Answer 1

免责声明：这种表述是主观的，只是为了说明。

从根本上讲，您的 AST 将像二叉树一样构建，其中每个 AST 节点都是一个“C”结构，包含“左”和“右”指针。AST 的其他元素通常是上下文相关的。例如，变量声明与函数定义或函数中的表达式。对于您引用的示例，粗略的树将反映这一点：

   +
 /   \
1     *
      /\
     2  3 

因此，通过将上述节点 1 + (2 * 3) 替换为 AST 构造，将类似于：

                 -----------------
                | type: ADDOP   |
                | left: struct* |
                | right: struct*|
                -----------------
              /                   \
             /                     \
 (ADDOP left points to)         (ADDOP right points to)
------------------------       --------------------------  
| type: NUMLITERAL     |       | type: MULTOP           |
| value: 1             |       | left: struct*          |
| left: struct* (null) |       | right: struct*         |
| right: struct*(null) |       --------------------------
------------------------              /               \
                                     /                 \

                    (MULTOP left points to)         (MULTOP right points to)
                    ------------------------       --------------------------  
                    | type: NUMLITERAL     |       | type: NUMLITERAL       |
                    | value: 2             |       | value: 3               |
                    | left: struct* (null) |       | left: struct* (null)   |
                    | right: struct*(null) |       | right: struct* (null)  |
                    ------------------------       --------------------------

我假设您对“C”以及如何malloc节点和分配左/右指针有足够的了解。

现在剩下的活动是对树进行后序遍历，以计算表达式并生成结果，或者发出与编译结果对齐的适当的中间代码/机器代码。无论哪种选择都会带来大量的思考和计划。

顺便说一句：如上所述，AST 节点通常具有基于您想要表示的抽象级别的属性。另请注意，典型的编译器可能出于不同原因利用多个 AST。是的，你要多读书/学习。

注意：这说明了 AST 的数据结构，但 @mikeb 的答案对于如何将字符串“1 + 2 * 3”放入此类结构的节点中非常可靠。