Существует 96 способов получить строку терминалов в этой грамматике.Мы подозреваем, что некоторые из этих производных производят избыточные строки терминалов, поэтому число строк в сгенерированном языке на самом деле меньше 96. Мы хотели бы расположить его так, чтобы каждое получение строки терминалов приводило к отдельной строке.
Мы могли бы перечислить все 96 производных, отсортировать их по производной строке и затем выяснить, как таким образом избежать неоднозначности.Это заняло бы немного больше времени, чем мне хотелось бы, и мы, вероятно, можем разумно сузить пространство поиска для повторяющихся строк путем анализа.
У нас нет другого выбора, кроме как использовать производственную S -> ABCD.Далее нужно выбрать ровно одно из произведений A -> ae, A -> af, A -> ag, A -> ah.Тем не менее, пока нет никакой двусмысленности в выборе.Далее мы должны выбрать либо B -> b, либо B -> e.Все еще нет двусмысленности.Именно с нашим выбором продукции для удаления С мы вводим неоднозначность впервые.Проблема в том, что cd является суффиксом hcd и bcd, и при соединении с другой строкой может создать суффикс hcd или bcd.Имея это в виду, мы находим следующие дубликаты дериваций:
S -> ABCD -> axBCD -> axbCD -> axbcdD -> axbcy
S -> ABCD -> axBCD -> axCD -> axbcD -> axbcy
Выше x обозначает один из символов e, f, g или h;и у обозначает один из символов е, 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