В CFG может случиться так, что все производственные правила и символы не нужны для получения строк. Кроме того, могут быть нулевые производства и единичные производства. Устранение этих производств и символов называется упрощением CFG . Упрощение состоит из следующих этапов:
- Снижение CFG
- Вывоз единицы продукции
- Удаление Нулевых Продукций
Снижение CFG
CFG снижаются в два этапа —
Фаза 1 — Вывод эквивалентной грамматики G ‘ из CFG, G , так что каждая переменная выводит некоторую терминальную строку.
Процедура деривации —
Шаг 1 — Включите все символы W 1 , которые выводят некоторый терминал и инициализируют i = 1 .
Шаг 2 — Включите все символы W i + 1 , которые выводят W i .
Шаг 3 — Увеличить i и повторять Шаг 2, пока W i + 1 = W i .
Шаг 4 — Включите все производственные правила, в которых есть W i .
Этап 2 — Вывод эквивалентной грамматики G ” из CFG G ‘ , так что каждый символ появляется в форме предложения.
Процедура деривации —
Шаг 1 — Включите начальный символ в Y 1 и инициализируйте i = 1 .
Шаг 2. Включите все символы Y i + 1 , которые могут быть получены из Y i, и включите все производственные правила, которые были применены.
Шаг 3 — Увеличьте i и повторяйте Шаг 2, пока Y i + 1 = Y i .
проблема
Найдите приведенную грамматику, эквивалентную грамматике G, имеющей правила производства, P: S → AC | B, A → a, C → c | BC, E → aA | е
Решение
Фаза 1 —
T = {a, c, e}
W 1 = {A, C, E} из правил A → a, C → c и E → aA
W 2 = {A, C, E} U {S} из правила S → AC
W 3 = {A, C, E, S} U ∅
Поскольку W 2 = W 3 , мы можем вывести G ‘как —
G ‘= {{A, C, E, S}, {a, c, e}, P, {S}}
где P: S → AC, A → a, C → c, E → aA | е
Фаза 2 —
Y 1 = {S}
Y 2 = {S, A, C} из правила S → AC
Y 3 = {S, A, C, a, c} из правил A → a и C → c
Y 4 = {S, A, C, a, c}
Поскольку Y 3 = Y 4 , мы можем вывести G ”как —
G ”= {{A, C, S}, {a, c}, P, {S}}
где P: S → AC, A → a, C → c
Вывоз единицы продукции
Любое производственное правило в форме A → B, где A, B ∈ Non-Terminal, называется единичным производством. ,
Процедура удаления —
Шаг 1 — Чтобы удалить A → B , добавьте производство A → x к правилу грамматики всякий раз, когда B → x встречается в грамматике. [x ∈ Terminal, x может быть нулевым]
Шаг 2 — Удалить A → B из грамматики.
Шаг 3 — Повторите с шага 1, пока все производства юнитов не будут удалены.
проблема
Удалить единицу продукции из следующего —
S → XY, X → a, Y → Z | b, Z → M, M → N, N → a
Решение —
В грамматике есть 3 единичных произведения —
Y → Z, Z → M и M → N
Сначала мы удалим M → N.
При N → a мы добавляем M → a, а M → N удаляется.
Производственный набор становится
S → XY, X → a, Y → Z | b, Z → M, M → a, N → a
Теперь мы удалим Z → M.
При M → a мы добавляем Z → a, а Z → M удаляется.
Производственный набор становится
S → XY, X → a, Y → Z | b, Z → a, M → a, N → a
Теперь мы удалим Y → Z.
При Z → a мы добавляем Y → a, а Y → Z удаляется.
Производственный набор становится
S → XY, X → a, Y → a | b, Z → a, M → a, N → a
Теперь Z, M и N недоступны, поэтому мы можем их удалить.
Конечный CFG — единичное производство бесплатно —
S → XY, X → a, Y → a | б
Удаление Нулевых Продукций
В CFG нетерминальный символ «A» является переменной, допускающей значение NULL, если существует произведение A → ε или существует деривация, которая начинается в A и в конце заканчивается
ε: A → …….… → ε
Процедура удаления
Шаг 1 — Узнайте обнуляемые нетерминальные переменные, которые выводят ε.
Шаг 2 — Для каждого производства A → a построим все производства A → x, где x получается из «a» , удаляя один или несколько нетерминалов из шага 1.
Шаг 3 — Объедините оригинальные произведения с результатом шага 2 и удалите ε — произведения .
проблема
Удалить нулевую продукцию из следующего —
S → ASA | АБ | b, A → B, B → b | ∈
Решение —
Есть две обнуляемые переменные — A и B
Сначала мы удалим B → ε.
После удаления B → ε производственный набор становится —
S → ASA | АБ | б | a, A ε B | б | & эпсилон, B → b
Теперь мы удалим A → ε.
После удаления A → ε производственный набор становится —
S → ASA | АБ | б | а | SA | AS | S, A → B | б, б → б
Это окончательный набор продукции без нулевого перехода.