Рубрики

Упрощение контекстно-свободных грамматик

Определение контекстно-свободных грамматик (CFG) позволяет нам разрабатывать широкий спектр грамматик. В большинстве случаев некоторые виды производства СУГ бесполезны и являются излишними. Это происходит потому, что определение CFG не ограничивает нас от создания этих избыточных производств.

Упрощая CFG, мы удаляем все эти избыточные произведения из грамматики, сохраняя преобразованную грамматику эквивалентной исходной грамматике. Две грамматики называются эквивалентными, если они производят один и тот же язык. Упрощение CFGs необходимо позже преобразовать их в обычные формы.

Типы избыточных производств и порядок их устранения указаны ниже.
1. Бесполезные произведения — произведения, которые никогда не могут участвовать в создании какой-либо строки, называются бесполезными произведениями. Точно так же переменная, которая никогда не может участвовать в выводе какой-либо строки, называется бесполезной переменной. Например,

S -> abS | abA | abB
A -> cd
B -> aB
C -> dc 						

В приведенном выше примере производство 'C -> dc' бесполезно, поскольку переменная 'C' никогда не будет возникать при выводе какой-либо строки. Другие произведения написаны таким образом, что переменная «C» никогда не может быть достигнута из начальной переменной «S».

Производство 'B -> aB' также бесполезно, потому что нет способа, которым оно когда-либо прекратится. Если он никогда не завершится, он никогда не сможет создать строку. Следовательно, производство никогда не может участвовать ни в каком выводе.

Чтобы удалить бесполезные произведения, мы сначала находим все переменные, которые никогда не приведут к терминальной строке, такой как переменная 'B'. Затем мы удаляем все произведения, в которых встречается переменная «B».
Таким образом, измененная грамматика становится

S -> abS | abA
A -> cd
C -> dc

Затем мы пытаемся определить все переменные, которые никогда не могут быть достигнуты из начальной переменной, такой как переменная «C». Затем мы удаляем все произведения, в которых встречается переменная «C».
Грамматика ниже теперь свободна от бесполезных произведений —

S -> abS | abA
A -> cd

2. Производство λ — Производство типа «A -> λ» называется производством λ (также называется производством лямбда и нулевым производством). Эти произведения могут быть удалены только из тех грамматик, которые не генерируют λ (пустая строка). Грамматика может содержать нулевые произведения и при этом не создавать пустую строку.

Чтобы удалить нулевые произведения, мы сначала должны найти все переменные, которые могут иметь значение null. Переменная «A» называется nullable, если λ можно получить из «A». Для всех произведений типа 'A -> λ', 'A' является переменной, допускающей значение NULL. Для всех произведений типа «B -> A1A2… An», где все «Ai» являются переменными, допускающими значение NULL, «B» также является переменной, допускающей значение NULL.

После нахождения всех переменных, допускающих значение NULL, мы можем приступить к построению свободной грамматики для нулевого производства. Для всех произведений в исходной грамматике мы добавляем исходное произведение, а также все комбинации произведений, которые можно сформировать, заменив переменные с нулем в произведении на λ. Если все переменные на RHS производства являются обнуляемыми, то мы не добавляем 'A -> λ' к новой грамматике. Пример прояснит суть. Рассмотрим грамматику —

S -> ABCd						(1)
A -> BC						        (2)
B -> bB | λ						(3)	
C -> cC | λ						(4)	

Давайте сначала найдем все переменные. Переменные «B» и «C» явно обнуляются, потому что они содержат «λ» на RHS их производства. Переменная «A» также может иметь значение NULL, поскольку в (2) обе переменные RHS также могут иметь значение NULL. Аналогично, переменная 'S' также может иметь значение null. Таким образом, переменные 'S', 'A', 'B' и 'C' являются обнуляемыми переменными.

Давайте создадим новую грамматику. Начнем с первого производства. Добавьте первую продукцию как есть. Затем мы создаем все возможные комбинации, которые можно сформировать, заменив обнуляемые переменные на λ. Поэтому строка (1) теперь становится 'S -> ABCd | ABd | ACd | BCd | Объявление | Bd | Cd | d '. Мы применяем то же правило к строке (2), но мы не добавляем' A -> λ ', хотя это возможная комбинация. Мы удаляем все произведения типа 'V -> λ'. Новая грамматика теперь становится —

S -> ABCd | ABd | ACd | BCd | Ad  |  Bd  |Cd | d
A -> BC | B | C
B -> bB | b
C -> cC | c

3. Производство единицы продукции — Производство типа «А -> В» называется производством единицы.
Чтобы создать единичную бесплатную грамматику 'Guf' из исходной грамматики 'G', мы следуем процедуре, упомянутой ниже.

Сначала добавьте все не-единичные произведения «G» в «Guf». Затем для каждой переменной «A» в грамматике «G» найдите все переменные «B», такие, что «A * => B». Теперь для всех переменных, таких как «A» и «B», добавьте «A -> x1 | х2 | … Xn 'в' Guf ', где' B -> x1 | х2 | … xn в Guf . Ни одна из x1, x2… xn не является единственной переменной, потому что мы добавили не-единичные произведения в 'Guf'. Следовательно, результирующая грамматика бесплатна. Например,

S -> Aa | B
A -> b | B
B -> A | a

Давайте добавим все не-единичные произведения G в Guf. «Guf» теперь становится —

S -> Aa
A -> b
B -> a

Теперь мы находим все переменные, которые удовлетворяют 'X * => Z'. Это 'S * => A', 'S * => B', 'A * => B' и 'B * => A'. Для «A * => B» мы добавляем «A -> a», потому что «B -> a» существует в «Guf». «ГУФ» теперь становится

	
S -> Aa
A -> b | a
B -> a

Для «B * => A» мы добавляем «B -> b», потому что «A -> b» существует в «Guf». Новая грамматика теперь становится

S -> Aa
A -> b | a
B -> a | b

Мы следуем тому же шагу для 'S * => A' и 'S * => B' и, наконец, получаем следующую грамматику:

S -> Aa | b | a
A -> b | a
B -> a | b

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

Эта статья предоставлена Нитишем Джоши . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Упрощение контекстно-свободных грамматик

0.00 (0%) 0 votes