带括号的逻辑运算符的上下文无关文法的实现

Question

我正在尝试为带括号的逻辑运算符语言实现上下文无关语法，包括运算符优先级。

例如，如下：

{1} or {2}
{1} and {2} or {3}
({1} or {2}) and {3}
not {1} and ({2} or {3})
...

我从以下语法开始：

expr := control | expr and expr | expr or expr | not expr | (expr)
control := {d+}

为了实现运算符优先级和eliminate left recursion，我按以下方式进行了更改：

S ::= expr
expr ::= control or expr1 | expr1
expr1 ::= control and expr2 | expr2
expr2 ::= not expr3 | expr3
expr3 ::= (expr) | expr | control
control := {d+}

但此类语法不支持包含 'and' / [=34= 的示例，例如：（{1} 或 {2}）和 {3} ] 括号后。

现在，我有以下语法：

S ::= expr
expr ::= control or expr1 | expr1
expr1 ::= control and expr2 | expr2
expr2 ::= not expr3 | expr3
expr3 ::= (expr) | (expr) expr4 | expr | control
expr4 :: = and expr | or expr
control := {d+}

这个语法正确吗？可以通过某种方式简化吗？

谢谢！

Answer 1

要实现您的运算符优先级，您只需要：

S ::= expr
expr ::= expr or expr1 | expr1
expr1 ::= expr1 and expr2 | expr2
expr2 ::= not expr2 | expr3
expr3 ::= (expr) | control
control := {d+}

这是左递归是为了左关联，因为这通常是您想要的（为了正确性和大多数解析器生成器），但是如果您出于某种原因需要避免左递归，您可以使用右递归右结合文法：

S ::= expr
expr ::= expr1 or expr | expr1
expr1 ::= expr2 and expr1 | expr2
expr2 ::= not expr2 | expr3
expr3 ::= (expr) | control
control := {d+}

因为and和or都是结合运算符，所以左右不重要。

在这两种情况下，您都可以通过将 expr3 和控制折叠成 expr2 来“简化”它：

expr2 ::= not expr2 | ( expr ) | {d+}

带括号的逻辑运算符的上下文无关文法的实现

Implementation of a context-free grammar for logical operators with parentheses

parsing

context-free-grammar

computation-theory

context-free-language