使上下文无关文法没有歧义

Question

我这周有考试。布尔语句有如下语法：

B -> B and B | not B | (B) | id

B为非终结符，终结符为：and、not、(、)、id

这个语法有歧义。我需要重写它并创建一个没有歧义且没有左递归的等效语法，这样 not 具有高优先级，'and' 与左侧关联。

我尝试过自己做：我的开始是：

B -> not B' | ( B' | id B'

但我认为这是错误的，我真的卡了很久

Answer 1

使用更多的非终端允许设置所有运算符的优先级（我希望我能正确理解你使用的符号）。

这是为了获得 and 的从右到左的关联性：id 和 id，id 被解析为 id 和 [id 和 id]

B -> NotExpr | NotExpr and B
NotExpr -> PrimaryExpr | not NotExpr
PrimaryExpr -> id | (B)

这是为了获得 and 的从左到右的关联性：id 和 id 并且 id 被解析为 [id 和 id] 和 id

B -> NotExpr | B and NotExpr
NotExpr -> PrimaryExpr | not NotExpr
PrimaryExpr -> id | (B)

Answer 2

另一种方法如下（编辑后，感谢@Peter）：

B  -> not B | B'
B' -> ( B ) | B' and B | id

Make a context free grammar not ambiguous