解决语法中的 first-follow 冲突

Question

我目前在解决这种语法冲突时遇到问题：

A -> (A)A'
A -> 0A'
A -> 1A'
A'-> NAND A A'
A'-> eps

问题是 A' 的 FIRST 是 NAND - 也是其 FOLLOW 集的一部分。由于存在 A' -> eps 规则，因此会产生冲突。有什么办法可以解决这个冲突吗？代入或因式分解不会产生任何结果 - 所以我想我遗漏了什么。

Answer 1

问题是你的语法有歧义。例如 0 NAND 0 NAND 0 至少有两个最左边的推导：

A => 0 A' => 0 NAND A A' => 0 NAND 0 A' A' => 0 NAND 0 NAND A A' A' =>
  => 0 NAND 0 NAND 0 A' A' A' =>* 0 NAND 0 NAND 0

A => 0 A' => 0 NAND A A' => 0 NAND 0 A' A' => 0 NAND 0 A' => 
  => 0 NAND 0 NAND A A' => 0 NAND 0 NAND 0 A' A' =>* 0 NAND 0 NAND 0

用 ELL 语法重写它（对我来说）更容易看到有两种可能的递归，NAND A 中的 A 或星号（原始语法中的 A'）。

A -> ( '(' A ')' | 0 | 1 ) ( NAND A )*

你可以解决使星号成为添加 NAND 的唯一选择并使用 '(' A ')' | 0 | 1 作为其操作数的歧义：

A -> X ( NAND X )*
X -> '(' A ')' | 0 | 1

解决语法中的 first-follow 冲突

Solving a first-follow conflict in a grammar

grammar

formal-languages

ll