Решение первоочередного конфликта в грамматике

Question

В настоящее время у меня проблемы с разрешением такого рода конфликта в грамматике:

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

Проблема в том, что FIRST of A'- это 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, мне будет легче увидеть две возможные рекурсии, с A в NAND Aили со звездочкой (A'в исходной грамматике).

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

Вы можете решить эту двусмысленность, сделав звезду единственным выбором для добавления NAND, и используя '(' A ')' | 0 | 1 как его операнды:

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