algorithm - 找出哪个 token 属于哪个 AST 节点

Question

我在实现解析项目时遇到了这个问题。我使用 Eclipse JDT 进行解析，得到的是解析后的抽象语法树。

我还需要 token 信息，比如哪个 token 属于哪个 AST 节点。由于JDT不直接给我提供信息，我需要将相同的概念移植到C族代码中，我更喜欢使用算法的方式来解决它。

这个问题可以用算法来描述。

对于每个 AST 节点，它在源代码中都有一个起始偏移量和一个结束偏移量。由于 AST 属性，每个节点的区域不会越过边界。 (不会有表达式 1->20 和另一个来自 4->23 的语句，但是有一个节点 1->20 和另一个节点 1->20 是可能的)

每个 token 也有起始偏移量和长度。非交叉边界属性仍然存在。 并且每个 token 都不会与其他 token 重叠。

我手头有一个 AST 和一个标记列表，我想将每个标记与一个 AST 节点匹配，匹配具有最窄区域但仍包含整个标记的 AST 节点。由于非交叉属性，我们只能检查每个标记的起始偏移量，并找到具有最窄区域的 AST 节点。

例如，如果我有一个语句int a = (3 * (5 + b));， token 流是int，a, =, (, 3, *, (, 5, +, b, ), ), ; AST 可能看起来像

statement
  |
assignment
  |    | 
id    expression 1
       |
      binary operation
       |        |
       int      expression 2
                 |
               binary operation
                 |       | 
                int       id

那我要int,;属于语句,b,内部(,) 属于第二个表达式。

虽然我手头有一个 AST，但是用它来查找特定的 AST 节点需要我为 java 语言的各种 ast 节点编写方法，因为没有通用的方法来访问它们的子节点。因此，我正在寻找通用算法解决方案。

Answer 1

最后发现用visitor也可以解决这个问题。让访问者访问 AST 并记住最后看到的 AST 节点包含给定的 token 。那么该 AST 节点就是包含该 token 的最紧密的 AST 节点。