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 parsing (也是 original paper )

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

• 一个 Pythonist 的 take在上面

• 一个Java version

真正巧妙的是它实际上只需要很少的代码。

关键概念是:

• 前缀与中缀与混合

• 优先级:是 3 + 4 * 5 解析为 (3 + 4) * 5 或 3 + (4 * 5)?

• 关联性:x - y - z 被解析为 x - (y - z) 或 (x - y) - z?

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