Как я могу преобразовать эту неоднозначную грамматику в недвусмысленную грамматику?

В этой грамматике есть 96 способов получить строку терминалов. Мы подозреваем, что некоторые из этих производных производят избыточные цепочки терминалов, поэтому количество строк в сгенерированном языке на самом деле меньше 96. Мы хотели бы упорядочить его так, чтобы каждое производное строки терминалов давало отдельную строку.

Мы могли бы перечислить все 96 производных, отсортировать их по производной строке, а затем выяснить, как таким образом избежать двусмысленности. Это займет немного больше времени, чем мне хотелось бы, и мы, вероятно, сможем разумно сузить область поиска повторяющихся строк путем анализа.

У нас нет другого выбора, кроме как использовать продукцию S -> ABCD. Далее, мы должны выбрать ровно одну из продукций A -> ae, A -> af, A -> ag, A -> ah. Тем не менее, двусмысленность в выборе пока невозможна. Далее мы должны выбрать либо B -> b, либо B -> e. Все равно нет никакой двусмысленности. Именно с нашим выбором продукции для удаления C мы впервые вводим неоднозначность. Проблема в том, что cd является суффиксом hcd и bcd, и при объединении с другой строкой может быть создан сам суффикс hcd или bcd. Имея это в виду, мы находим следующие повторяющиеся выводы:

S -> ABCD -> axBCD -> axbCD -> axbcdD -> axbcy
S -> ABCD -> axBCD -> axCD -> axbcD -> axbcy

Выше x обозначает один из символов e, f, g или h; а y заменяет один из символов e, f, g или h. Неоднозначность возникает из-за того, что мы можем получить b либо из B -> b, либо из C -> bcd.

Прежде чем мы продолжим, мы должны переписать грамматику, чтобы устранить этот источник двусмысленности; нет смысла идти дальше, пока мы не преодолеем это. Как мы можем это решить? В этом случае подумайте, как могла бы выглядеть грамматика, если бы мы объединили символы A и B в новый символ A'. Тогда производство будет:

A' -> ae | af | ag | ah | aeb | aef | aeg | aeh

Однако мы обнаружим, что та же проблема все еще существует; изначально проблема была не между продукцией для B и продукцией для A, а между продукцией для B и для C. Вместо этого мы могли бы попробовать:

B' -> hcd | bcd | cd | bhcd | bbcd

Важно отметить, что мы перечислили только пять терминов выше, а не 6, потому что одна продукция, B' -> bcd, генерируется дважды путем объединения этих смежных продуктов. Когда вы видите, как это происходит, это означает, что вы устраняете двусмысленность. Новая грамматика выглядит так:

S  -> ABCD
A  -> ae | af | ag | ah
B' -> cd | hcd | bcd | bhcd | bbcd
C  -> e | f | g | h

Мы можем повторить анализ с самого начала здесь и найти следующее:

• мы должны выбрать S -> ABCD
• мы должны выбрать одно из A -> ae, A -> af, A -> ag, A -> ah, и никакой выбор не вводит двусмысленность
• мы должны выбрать один из продуктов для B', и это не может привести к двусмысленности, потому что все префиксы, к которым мы добавляем, имеют одинаковую базовую длину (2 символа), и они были однозначно получены
• мы должны выбрать одну из постановок для D, и это не может привести к двусмысленности, потому что все префиксы, к которым мы добавляем, содержат только один экземпляр d, который встречается в самом конце, поэтому мы всегда можем однозначно сказать, где символы, введенные постановкой для B 'конец и символ, введенный производством для D, начинается