CFG находится в нормальной форме Грейбаха, если продукция представлена в следующих формах:
A → b
A → bD 1 … D n
S → ε
где A, D 1 , …., D n не являются терминалами, а b является терминалом.
Алгоритм для преобразования CFG в нормальную форму Грейбаха
Шаг 1 — Если начальный символ S встречается справа, создайте новый начальный символ S ‘ и новый производственный S’ → S.
Шаг 2 — Удалить нулевые произведения. (Использование алгоритма удаления продукции Null, обсуждавшегося ранее)
Шаг 3 — Удалить единицу продукции. (Использование алгоритма удаления производства блока обсуждалось ранее)
Шаг 4 — Удалить все прямые и косвенные левые рекурсии.
Шаг 5 — Делайте правильные замены произведений, чтобы преобразовать его в правильную форму GNF.
проблема
Конвертировать следующие CFG в CNF
S → XY | Xn | п
X → mX | м
Y → Xn | о
Решение
Здесь S не отображается справа от любого производства, и в наборе правил производства нет единичных или нулевых производств. Итак, мы можем пропустить Шаг 1 до Шаг 3.
Шаг 4
Теперь после замены
X в S → XY | Xo | п
с
мх | м
мы получаем
S → mXY | мг | mXo | мо | п.
И после замены
X в Y → X n | о
с правой стороны
X → mX | м
мы получаем
Y → mXn | мн | о.
Два новых произведения O → o и P → p добавляются к производственному набору, а затем мы подошли к финальному GNF следующим образом:
S → mXY | мг | mXC | мс | п
X → mX | м
Y → mXD | мд | о
O → o
P → p