Решая первого последующего конфликта в грамматике

Question

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

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

Проблема в том, что первый из А»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 ')' | 0 | 1) (NAND A)* 

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

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