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

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

• 道格拉斯·克罗克福德 (Douglas Crockford) 的看法

• Python 主义者的看法

• Java版本

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

关键概念是：

• 前缀 vs 中缀 vs mixfix

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

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

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