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

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 解析（也是原论文）

• 道格拉斯·克罗克福德对此的看法

• 一个 Pythonist的看法

• Java版本

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

关键概念是：

• 前缀 vs 中缀 vs mixfix

• 优先级：被3 + 4 * 5解析为(3 + 4) * 5or 3 + (4 * 5)?

• 关联性：被x - y - z解析为x - (y - z)or (x - y) - z?

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