Ієрархія Хомського

Ієрархія Хомського - класифікація формальних мов і формальних граматик, згідно з якою вони поділяються на 4 типи за їх умовною складності. Запропонована професором Массачусетського технологічного інституту, лінгвістом Ноам Хомський.


1. Класифікація граматик

Згідно Хомскому, формальні граматики діляться на чотири типи. Для віднесення граматики до того чи іншого типу необхідно відповідність всіх її правил (продукцій) деяким схемами.

1.1. Тип 0 - необмежені

Граматика з фразової структурою G - це алгебраїчна структура, впорядкована четвірка (V T, V N, P, S), де [1] :

  • V_T - Алфавіт (множина) термінальних символів - терміналів,
  • V_N - Алфавіт (множина) нетермінальних символів - нетерміналів,
  • V = V_T \ cup V_N - Словник G , Причому V_T \ cap V_N = \ empty
  • P - Кінцеве безліч продукций (правил) граматики, P \ subseteq V ^ + \ times V ^ *
  • S - Початковий символ (джерело).

Тут V ^ * - Множина всіх рядків над алфавітом V , А V ^ + - Безліч непорожніх рядків над алфавітом V .

До типу 0 по класифікації Хомського відносяться необмежені граматики - граматики з фразової структурою, тобто всі без винятку формальні граматики. Правила можна записати у вигляді:

\ Alpha \ rarr \ beta ,

де \ Alpha - Будь-яка непорожній ланцюжок, що містить хоча б один нетермінальний символ, а \ Beta - Будь-яка ланцюжок символів з алфавіту.

Практичного застосування в силу своєї складності такі граматики не мають.


1.2. Тип 1 - контекстно-залежні

До цього типу відносяться контекстно-залежні (КЗ) граматики і неукорачівающіе граматики. Для граматики G (V T, V N, P, S), V = V T ∪ V N усі правила мають вигляд [2] :

  • αAβ → αγβ, де α, β ∈ V *, γ ∈ V +, A ∈ V N. Такі граматики відносять до контекстно-залежним.
  • α → β, де α, β ∈ V +, 1 ≤ | α | ≤ | β |. Такі граматики відносять до неукорачівающім.

Ці класи граматик еквівалентні. Можуть використовуватися при аналізі текстів на природних мовах, однак при побудові компіляторів практично не використовуються в силу своєї складності. Для контекстно-залежних граматик доведено твердження: по деякому алгоритму за кінцеве число кроків можна встановити, належить ланцюжок термінальних символів даному мови чи ні.


1.3. Тип 2 - контекстно-вільні

До цього типу відносяться контекстно-вільні (КС) граматики. Для граматики G (V T, V N, P, S), V = V T ∪ V N усі правила мають вигляд:

  • A → β, де β ∈ V + (для неукорачівающіх КС-граматик, β ∈ V * для укорочують), A ∈ V N. Тобто граматика допускає появу в лівій частині правила тільки нетермінального символу.

КС-граматики широко застосовуються для опису синтаксису комп'ютерних мов (див. синтаксичний аналіз).


1.4. Тип 3 - регулярні

До третього типу відносяться регулярні граматики (автоматні) - найпростіші з формальних граматик. Вони є контекстно-вільними, але з обмеженими можливостями.

Всі регулярні граматики можуть бути розділені на два еквівалентних класу, які для граматики виду III матимуть правила такого вигляду:

  • A → Bγ або A → γ, де γ ∈ V T *, A, B ∈ V N (для леволінейних граматик).
  • A → γB; або A → γ, де γ ∈ V T *, A, B ∈ V N (для праволінейних граматик).

Регулярні граматики застосовуються для опису найпростіших конструкцій: ідентифікаторів, рядків, констант, а також мов асемблера, командних процесорів і ін


2. Класифікація мов

Формальні мови класифікуються відповідно до типами граматик, якими вони задаються. Однак, один і той же мова може бути заданий різними граматиками, що відносяться до різних типів. У такому випадку, вважається, що мова належить до найбільш простого з них. Так, мову, описаний граматикою з фразової структурою, контекстно-залежної і контекстно-вільної граматиками, буде контекстно-вільним.

Так само, як і для граматик, складність мови визначається його типом. Найбільш складні - мови з фразової структурою (сюди можна віднести природні мови), далі - КЗ-мови, КС-мови і найпростіші - регулярні мови.


Примітки

Джерела

  • А. Ю. Молчанов. Системне програмне забезпечення. Санкт-Петербург. Питер, 2006

Література

  • Джон Хопкрофт, Раджив Мотвані, Джеффрі Ульман РОЗДІЛ 5. Контекстно-вільні граматики та мови / / Введення в теорію автоматів, мов і обчислень = Introduction to Automata Theory, Languages, and Computation. - М .: "Вильямс", 2002. - С. 528. - ISBN 0-201-44124-1
  • Робін Хантер Основні концепції компіляторів = The Essence of Compilers. - М .: "Вильямс", 2002. - С. 256. - ISBN 5-8459-0360-2
  • Кук Д., Бейз Г. Глава 8. Мови та граматики / / Комп'ютерна математика = Computer Mathematics. - М .: Наука. Физматлит, 1990. - 384 с. - ISBN 5-02-014216-6