如何解析这种类型的表达式？

Question

我没有编译器的背景，所以我不确定这是否是该领域的一个常见问题。有没有标准的技术来解析这样的表达式？ （比如，标签指示深度）

And 
    A + B = 1 
    C + D = 1 
    Or 
     P + Q = 1 
     K = 1 
    And 
     Q = 1 
     R = 2 

应该被解析为：我不知道

((A+B=1) AND (C+D=1) AND ((P+Q=1) OR (K=1)) AND ((Q=1) AND (R=2))) 

，如果我要再打一个基于堆栈的评价？我目前正在尝试一个，我会发布一个工作代码，如果我可以让它运行。

任何建议在一个简单的方法来实现这个？

Answer 1

假设您问的是如何解析由运算符构建的具有不同优先级和关联性的表达式 - 绝对如此。

一种有效的方法称为“自顶向下运算符优先级”，也可能是“运算符优先级”和“优先级爬升”解析。这里有一些很好的来源在详细地解释方法：

• Pratt parsing（也original paper）

• 道格拉斯克罗克福德上的take

• 一个Pythonist它的take

• 一Java version

真正整洁的事情是它实际需要多少代码。

主要概念是：

• 前缀VS缀VS mixfix

• 优先：是3 + 4 * 5解析为(3 + 4) * 5或3 + (4 * 5)？

• 相关性：是x - y - z解析为​​或(x - y) - z？

巧合的是，我刚才最近学习这个东西，最终出了关于类似的方法来操作解析，你可以找到here博客写的文章。在我的方法中，我处理中缀，前缀，后缀和mixfix操作符（即? :）;优先级和关联性都在表中指定;我使用堆栈来跟踪其操作数尚未找到的操作符。解析器然后构建一个解析树，其中每个节点都是一个子表达式。