Нормальная форма Хомского

Обозначения для контекстно-свободных формальных грамматик

В формальной теории языка контекстно-свободная грамматика G называется находящейся в нормальной форме Хомского (впервые описанной Ноамом Хомским ) ^[1], если все ее правила вывода имеют вид: ^{[2] [3]}

А → БК , или

А → а , или

С → ε,

где A , B и C — нетерминальные символы , буква a — терминальный символ (символ, представляющий постоянное значение), S — начальный символ, а ε обозначает пустую строку . Кроме того, ни B , ни C не могут быть начальным символом , а третье правило производства может появиться только в том случае, если ε находится в L ( G ), языке , созданном контекстно-свободной грамматикой G. ^{[4] : 92–93, 106}

Каждая грамматика в нормальной форме Хомского является контекстно-свободной, и наоборот, каждая контекстно-свободная грамматика может быть преобразована в эквивалентную грамматику ^{[примечание 1]} , которая находится в нормальной форме Хомского и имеет размер, не превышающий квадрат размера исходной грамматики.

Преобразование грамматики в нормальную форму Хомского

Чтобы преобразовать грамматику в нормальную форму Хомского, применяется последовательность простых преобразований в определенном порядке; это описано в большинстве учебников по теории автоматов . ^{[4] : 87–94  [5] [6] [7]} Представленное здесь изложение следует Хопкрофту, Ульману (1979), но адаптировано для использования названий преобразований из Ланге, Лейсса (2009). ^{[8] [примечание 2]} Каждое из следующих преобразований устанавливает одно из свойств, требуемых для нормальной формы Хомского.

СТАРТ: Удалить символ старта с правой стороны.

Ввести новый начальный символ S ₀ и новое правило

С0 → С ,_​

где S — предыдущий начальный символ. Это не меняет язык, создаваемый грамматикой, и S ₀ не будет встречаться в правой части любого правила.

ТЕРМИН: Исключить правила с неодиночными терминалами

Чтобы устранить каждое правило

А → Х ₁ ... а ... Х _н

с терминальным символом a, не являющимся единственным символом в правой части, ввести для каждого такого терминала новый нетерминальный символ N _a и новое правило

Н _а → а .

Изменить все правила

А → Х ₁ ... а ... Х _н

к

А → Х ₁ ... Н _а ... Х _н .

Если несколько терминальных символов встречаются с правой стороны, одновременно замените каждый из них связанным с ним нетерминальным символом. Это не изменит язык, созданный грамматикой. ^{[4] : 92}

BIN: Исключить правые части, содержащие более 2 нетерминалов.

Заменить каждое правило

А → Х1 _Х2 ... Хn​_​​

с более чем 2 нетерминалами X ₁ ,..., X _n по правилам

А → Х ₁ А ₁ ,

А1 → Х2 _А2 ,_​​_​

... ,

А _{n -2} → Х _{n -1} Х _n ,

где A _i — новые нетерминальные символы. Опять же, это не меняет язык, созданный грамматикой. ^{[4] : 93}

DEL: Устранить ε-правила

ε-правило — это правило вида

А → ε,

где A не является S ₀ , начальным символом грамматики.

Чтобы исключить все правила этой формы, сначала определите множество всех нетерминалов, которые выводят ε. Хопкрофт и Ульман (1979) называют такие нетерминалы nullable и вычисляют их следующим образом:

• Если существует правило A → ε, то A может быть обнулено.
• Если существует правило A → X ₁ ... X _n и каждое X _i может иметь значение NULL, то A также может иметь значение NULL.

Получите промежуточную грамматику, заменив каждое правило

А → Х ₁ ... Х _n

всеми версиями с некоторыми пропущенными обнуляемыми X _i . Удаляя в этой грамматике каждое ε-правило, если только его левая часть не является начальным символом, получаем преобразованную грамматику. ^{[4] : 90}

Например, в следующей грамматике с начальным символом S ₀ ,

S ₀ → АбБ | С

В → АА | АС

С → б | с

А → а | ε

нетерминал A , а значит и B , допускает значение null, тогда как ни C , ни S ₀ не допускают. Следовательно, получается следующая промежуточная грамматика: ^{[примечание 3]}

S ₀ → А б Б | А б Б | А б Б | А б В   |   С

B → AA | А А | А А | А ε А   |   А С | А С

С → б | с

А → а | ε

В этой грамматике все ε-правила были « встроены в место вызова». ^{[примечание 4]} На следующем этапе их можно удалить, получив следующую грамматику:

S ₀ → АбБ | Аб | бВ | б   |   С

Б → АА | А   |   АС | С

С → б | с

А → а

Эта грамматика создает тот же язык, что и исходный пример грамматики, а именно. { ab , aba , abaa , abab , abac , abb , abc , b , ba , baa , bab , bac , bb , bc , c }, но не имеет ε-правил.

UNIT: Устранить правила юнита

Правило единицы — это правило вида

А → Б ,

где A , B — нетерминальные символы. Чтобы удалить его, для каждого правила

В → Х1 ... Хn ,_​​

где X ₁ ... X _n — строка нетерминалов и терминалов, добавьте правило

А → Х ₁ ... Х _n

Если только это не правило единицы, которое уже было (или удаляется). Пропуск нетерминального символа B в результирующей грамматике возможен из-за того, что B является членом замыкания единицы нетерминального символа A . ^[9]

Порядок преобразований

При выборе порядка, в котором должны применяться вышеуказанные преобразования, следует учитывать, что некоторые преобразования могут разрушить результат, достигнутый другими. Например, START повторно введет правило единицы, если оно применяется после UNIT . Таблица показывает, какие упорядочения допускаются.

Более того, наихудшее увеличение размера грамматики ^{[примечание 5]} зависит от порядка преобразования. Используя | G | для обозначения размера исходной грамматики G , увеличение размера в наихудшем случае может варьироваться от | G | ² до 2 ^{2 |G|} , в зависимости от используемого алгоритма преобразования. ^{[8] : 7} Увеличение размера грамматики зависит от порядка между DEL и BIN . Оно может быть экспоненциальным, когда DEL выполняется первым, но линейным в противном случае. UNIT может повлечь за собой квадратичное увеличение размера грамматики. ^{[8] : 5} Упорядочения START , TERM , BIN , DEL , UNIT и START , BIN , DEL , UNIT , TERM приводят к наименьшему (т. е. квадратичному) увеличению.

Пример

Абстрактное синтаксическое дерево арифметического выражения " a ^2+4* b " относительно примера грамматики ( вверху ) и его нормальной формы Хомского ( внизу )

Следующая грамматика с начальным символом Expr описывает упрощенную версию множества всех синтаксически допустимых арифметических выражений в языках программирования, таких как C или Algol60 . И число, и переменная считаются здесь терминальными символами для простоты, поскольку в компиляторе front-end их внутренняя структура обычно не рассматривается синтаксическим анализатором . Терминальный символ "^" обозначает возведение в степень в Algol60.

На шаге "START" вышеприведенного алгоритма преобразования в грамматику добавляется только правило S ₀ → Expr . После шага "TERM" грамматика выглядит так:

После шага «BIN» получается следующая грамматика:

Поскольку ε-правил нет, шаг "DEL" не меняет грамматику. После шага "UNIT" получается следующая грамматика, которая находится в нормальной форме Хомского:

N a _, представленные на шаге "TERM", — это PowOp , Open и Close . A _i , представленные на шаге "BIN", — это AddOp_Term , MulOp_Factor , PowOp_Primary и Expr_Close .

Альтернативное определение

Приведенная форма Хомского

Другой способ ^{[4] : 92  [10]} определить нормальную форму Хомского:

Формальная грамматика находится в редуцированной форме Хомского , если все ее правила производства имеют вид:

${\displaystyle A\rightarrow \,BC}$или

${\displaystyle A\rightarrow \,a}$,

где , и являются нетерминальными символами, а является терминальным символом . При использовании этого определения или может быть начальным символом. Только те контекстно-свободные грамматики, которые не генерируют пустую строку, могут быть преобразованы в приведенную форму Хомского. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle a}$ ${\displaystyle B}$ ${\displaystyle C}$

Нормальная форма Флойда

В письме, где он предложил термин форма Бэкуса–Наура (БНФ), Дональд Э. Кнут подразумевал БНФ, «синтаксис, в котором все определения имеют такую ​​форму, что можно сказать, что он находится в «нормальной форме Флойда»»,

${\displaystyle \langle A\rangle ::=\,\langle B\rangle \mid \langle C\rangle }$или

${\displaystyle \langle A\rangle ::=\,\langle B\rangle \langle C\rangle }$или

${\displaystyle \langle A\rangle ::=\,a}$,

где , и являются нетерминальными символами, а является терминальным символом, поскольку Роберт У. Флойд в 1961 году обнаружил, что любой синтаксис BNF может быть преобразован в указанный выше. ^[11] Но он отозвал этот термин, «поскольку, несомненно, многие люди независимо использовали этот простой факт в своих собственных работах, и этот момент лишь второстепенный по отношению к основным соображениям заметки Флойда». ^[12] В то время как в заметке Флойда цитируется оригинальная статья Хомского 1959 года, в письме Кнута этого нет. ${\displaystyle \langle A\rangle }$ ${\displaystyle \langle B\rangle }$ ${\displaystyle \langle C\rangle }$ ${\displaystyle a}$

Приложение

Помимо своего теоретического значения, преобразование CNF используется в некоторых алгоритмах в качестве этапа предварительной обработки, например, в алгоритме CYK , восходящем синтаксическом анализе для контекстно-свободных грамматик, и его вероятностном варианте CKY. ^[13]

Смотрите также

• Форма Бэкуса–Наура
• Алгоритм CYK
• Нормальная форма Грейбаха
• Нормальная форма Куроды
• Лемма о накачке для контекстно-свободных языков — ее доказательство основано на нормальной форме Хомского

Примечания

1. то есть тот, который производит тот же язык
2. Например, Хопкрофт, Ульман (1979) объединили TERM и BIN в одно преобразование.
3. указывает на сохраненный и пропущенный нетерминальный символ N как N и N , соответственно
4. Если бы грамматика имела правило S ₀ → ε, то ее нельзя было бы «встроить», так как у нее не было бы «мест вызова». Поэтому ее нельзя было бы удалить на следующем шаге.
5. т.е. длина написания, измеряемая в символах

Ссылки

1. Хомский, Ноам (1959). «О некоторых формальных свойствах грамматик». Информация и управление . 2 (2): 137–167. doi :10.1016/S0019-9958(59)90362-6.Здесь: Раздел 6, стр. 152 и далее.
2. Д'Антони, Лорис. "Страница 7, Лекция 9: Алгоритмы синтаксического анализа снизу вверх" (PDF) . CS536-S21 Введение в языки программирования и компиляторы . Университет Висконсин-Мэдисон. Архивировано (PDF) из оригинала 2021-07-19.
3. Sipser, Michael (2006). Введение в теорию вычислений (2-е изд.). Boston: Thomson Course Technology. Определение 2.8. ISBN 0-534-95097-3. OCLC  58544333.
4. Хопкрофт, Джон Э.; Ульман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления. Рединг, Массачусетс: Addison-Wesley Publishing. ISBN 978-0-201-02988-8.
5. Хопкрофт, Джон Э.; Мотвани, Раджив; Ульман, Джеффри Д. (2006). Введение в теорию автоматов, языки и вычисления (3-е изд.). Эддисон-Уэсли. ISBN 978-0-321-45536-9.Раздел 7.1.5, стр.272
6. Рич, Элейн (2007). "11.8 Нормальные формы". Автоматы, вычислимость и сложность: теория и приложения (PDF) (1-е изд.). Prentice-Hall. стр. 169. ISBN 978-0132288064. Архивировано из оригинала (PDF) 2023-01-17.
7. Вегенер, Инго (1993). Theoretische Informatik - Eine orientierte Einführung . Leitfäden und Mongraphien der Informatik (на немецком языке). Штутгарт: Б. Г. Тойбнер. ISBN 978-3-519-02123-0.Раздел 6.2 «Нормальная форма Хомского для контекстной грамматики», стр. 6.2. 149–152
8. Ланге, Мартин; Лейсс, Ганс (2009). «К CNF или нет? Эффективная, но презентабельная версия алгоритма CYK» (PDF) . Informatica Didactica . 8 . Архивировано (PDF) из оригинала 2011-07-19.
9. Эллисон, Чарльз Д. (2022). Основы вычислений: доступное введение в автоматы и формальные языки . Fresh Sources, Inc. стр. 176. ISBN 9780578944173.
10. Хопкрофт и др. (2006) ^{[ нужна страница ]}
11. Флойд, Роберт В. (1961). «Заметка о математической индукции в грамматиках фразовой структуры» (PDF) . Информация и управление . 4 (4): 353–358. doi : 10.1016/S0019-9958(61)80052-1 . Архивировано (PDF) из оригинала 2021-03-05.Здесь: стр.354
12. Кнут, Дональд Э. (декабрь 1964 г.). «Нормальная форма Бэкуса против формы Бэкуса-Наура». Сообщения ACM . 7 (12): 735–736. doi : 10.1145/355588.365140 . S2CID  47537431.
13. Джурафски, Дэниел; Мартин, Джеймс Х. (2008). Обработка речи и языка (2-е изд.). Pearson Prentice Hall. стр. 465. ISBN 978-0-13-187321-6.

Дальнейшее чтение

• Коул, Ричард. Преобразование CFG в CNF (нормальную форму Хомского) , 17 октября 2007 г. (pdf) — использует порядок TERM, BIN, START, DEL, UNIT.
• Джон Мартин (2003). Введение в языки и теорию вычислений . McGraw Hill. ISBN 978-0-07-232200-2. (Страницы 237–240 раздела 6.6: упрощенные формы и нормальные формы.)
• Майкл Сипсер (1997). Введение в теорию вычислений. PWS Publishing. ISBN 978-0-534-94728-6. (Страницы 98–101 раздела 2.1: контекстно-свободные грамматики. Страница 156.)
• Charles D. Allison (2021) (20 августа 2021 г.). Основы вычислений: доступное введение в формальный язык . Fresh Sources, Inc. ISBN 9780578944173.{{cite book}}: CS1 maint: числовые имена: список авторов ( ссылка ) (страницы 171-183 раздела 7.1: Нормальная форма Хомского)
• Сипсер, Майкл. Введение в теорию вычислений, 2-е издание.
• Александр Медуна (6 декабря 2012 г.). Автоматы и языки: теория и приложения. Springer Science & Business Media. ISBN 978-1-4471-0501-5.