从标记创建语法树

Question

我正在尝试为 TI-BASIC 语法创建一个小型解释器。

这是我正在尝试解释的 TI-BASIC 片段

A->(2+(3*3))

我已将上面的代码标记为以下标记序列：

Token{type=VARIABLE, content='A'}
Token{type=ASSIGN, content='null'}
Token{type=L_PAREN, content='null'}
Token{type=NUM, content='2'}
Token{type=ADD, content='null'}
Token{type=L_PAREN, content='null'}
Token{type=NUM, content='3'}
Token{type=MULT, content='null'}
Token{type=NUM, content='3'}
Token{type=R_PAREN, content='null'}
Token{type=R_PAREN, content='null'}
Token{type=EOS, content='null'} (end of statement)
Token{type=EOF, content='null'} (end of file)

如果我没记错的话，我认为下一步是将这些标记表示为语句树（抽象语法树？）

 Assignment (->)
    / \
   /   \
  A    Add
       /\
      /  \
     2  Multiply
           /\
          /  \
         3    3

我想知道我应该如何创建这棵树，或者这是否是正确的做法。谢谢！

Answer 1

我正在从事类似的任务来解析和执行算术表达式 - 例如a*(b+c-d)

词法分析提供令牌列表后，解析过程将迭代所有令牌并创建不断增长的节点树。

基本上，这棵树的每个节点都是一个对象，它具有一些属性，并且可以引用另一个节点（它是父节点）。

因此，该树的节点必须至少包含以下信息：

• 父节点（根节点为空）
• 节点类型（该节点代表什么代币）

节点类型可以是（在我的例子中是简单的算术表达式，如 a*(b+c) ）变量名、数字或运算符。括号的含义隐式编码在树的结构中，因此与数字、变量和运算符不同，括号不表示为节点

此类节点的 java 代码可能如下所示：

public class ASTNode {
  Double numberValue;  // Only one of numberValue, varName or operator may be
  String varName;      // set. The other two must be null.
  String operator;
  
  public ASTNode parent;
}

对于 a*b+c-d 的示例，语法树可能会像这样增长：

解析标记“a”：

a

解析标记“*”：

a
|
*

解析标记“b”：

a   b
 \ /
  *

解析标记“+”：

a   b
 \ /
  *
  |
  +

解析标记“c”：

a   b
 \ /
  *   c
   \ /
    +

解析标记“-”：

a   b
 \ /
  *   c
   \ /
    +
    |
    -

解析标记“d”：

a   b
 \ /
  *   c
   \ /
    +   d
     \ /
      -

出于显而易见的原因，这个任务非常适合通过递归来解决。

基本的“解析”函数只需要能够使用一个运算符和 2 个操作数构建一个最小语法树，并递归地调用自身来处理更复杂的情况：

a   b
 \ /
  o

如果 a 或 b 本身恰好是一个复杂表达式（例如，括号中包含一个表达式），它只需再次递归调用自身，并附加生成的子树来代替 a 或 b。

干杯

Answer 2

简单的答案是您需要为 TI-Basic 编写一个解析器。您已经编写了词法分析器（词法分析器），现在需要编写语法分析器。

有很多方法可以做到这一点，但是关于解析器的维基百科页面是一个很好的起点：解析器的示例。