自下而上解析和减少解析树的正确算法是什么？

Question

示例分析树用于表达式

IF( ABS( column ) > 10 ,"8214","8215")

为了将它缩减为一个只有 QueryFunction (ABS, IF), QueryColumns (column), QueryConstants (10 , "8214","8215") 节点（用户定义）的 AST，如

                    IF
                    |
     |--------------|--------------| 
     >            "8214"         "8215"
|----|----|
ABS       10
|
columnName

使用什么算法才是正确的？在这种情况下是否需要像 LR 解析这样的复杂解析方法？

请注意，QueryFunction 可以有不同数量的参数，具体取决于函数的类型。每个函数也可以在其中包含其他嵌套函数。

Answer 1

这样做没有什么特别“复杂”的。对于 ANTLR 用户来说，想要将解析树转换为 AST 是相当普遍的（特别是，给定解析树包含的所有中间 odes）。

使用 ANTLR 侦听器（或访问器），访问解析树并使用它来构造您需要的任何 AST 结构相对简单。

除非您知道需要 AST，否则您可能希望尝试 ANTLR 生成的本机 Listeners/Visitors。通过覆盖 *BaseListener 或 *BaseVisitor 类，您将获得所有节点的默认实现，这些实现允许您编写可以安全地“忽略”您并不真正关心的中间节点的代码关于，并且只是“收听”你关心的节点（对于听众）。（无论如何，如果你想使用它们来创建 AST，你会想要理解这一点，所以不要浪费学习）。

注意：无论您使用什么语法，看起来都可以进行一些改进。如果图表是我正在谈论的示例，则位于最底部。 column_name 解析规则应该是一个 Token 或引用一个 Token 规则，用于将列名拉入单个标记而不是字符列表。使用更合适的语法，您的 ANTLR 解析树将看起来不那么荒谬（如果需要，也更容易生成 AST）。

自下而上解析和减少解析树的正确算法是什么？

What will be the right algorithm to bottom up parse and reduce a parse tree?

tree

antlr

abstract-syntax-tree

traversal

parse-tree