context-free-grammar - 在 CFG 中实现中缀

Question

我有一个关于构建基本上下文无关语法的问题。我的语法旨在解析数学陈述。到目前为止我有这个：

E --> P
E --> E + P
P --> A
P --> P * A
A --> (E)
A --> n

我需要实现另一个非终结符 X，它代表中缀运算符 (^)，意思是提升到一个权力。我不知道如何实现 X 以使其具有右关联性并且具有比 * 和 + 更高的优先级。我无法理解上述 CFG 如何强制 * 比 + 具有更高的优先级。对这两个问题的任何解释（在上述 CFG 中 * 如何优先于 + 以及如何正确实现 ^）将不胜感激。

标签： context-free-grammar

Answer 1

既不P也A不能生产x+y。因此，必须比在or中*更紧密地结合。+x+y*zz*x+y

同样，P可以生产x*y但A不能。因此，鉴于匹配的产生式 is P*A，唯一有效的解析x*y*z是 is P => x*y; A => z。这使得*左联想。

如果你画一些语法树，这可能会变得更加清晰。