Иерархия Хомского
Иерархия Хомского — классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности. Предложена профессором Массачусетского технологического института, лингвистом Ноамом Хомским.
Классификация грамматик
Согласно Хомскому, формальные грамматики можно разделить на четыре типа. Для отнесения грамматики к тому или иному типу необходимо соответствие всех её правил (продукций) некоторым схемам.
Тип 0 — неограниченные
Грамматика с фразовой структурой G — это алгебраическая структура, упорядоченная четвёрка (VT, VN, P, S), где[1]:
- [math]\displaystyle{ V_T }[/math] — алфавит (множество) терминальных символов — терминалов,
- [math]\displaystyle{ V_N }[/math] — алфавит (множество) нетерминальных символов — нетерминалов,
- [math]\displaystyle{ V = V_T \cup V_N }[/math] — словарь [math]\displaystyle{ G }[/math], причём [math]\displaystyle{ V_T \cap V_N = \varnothing }[/math]
- [math]\displaystyle{ P }[/math] — конечное множество продукций (правил) грамматики, [math]\displaystyle{ P \subseteq V^+\times V^* }[/math]
- [math]\displaystyle{ S }[/math] — начальный символ (источник).
Здесь [math]\displaystyle{ V^* }[/math] — множество всех строк над алфавитом [math]\displaystyle{ V }[/math], а [math]\displaystyle{ V^+ }[/math] — множество непустых строк над алфавитом [math]\displaystyle{ V }[/math].
К типу 0 по классификации Хомского относятся неограниченные грамматики — грамматики с фразовой структурой, то есть все без исключения формальные грамматики. Правила можно записать в виде:
- [math]\displaystyle{ \alpha\rarr\beta }[/math],
где [math]\displaystyle{ \alpha\in V^+ }[/math] — любая непустая цепочка, содержащая хотя бы один нетерминальный[2] символ, а [math]\displaystyle{ \beta\in V^* }[/math] — любая цепочка символов из алфавита.
Практического применения в силу своей сложности такие грамматики не имеют.
Тип 1 — контекстно-зависимые
К этому типу относятся контекстно-зависимые (КЗ) грамматики и неукорачивающие грамматики. Для грамматики [math]\displaystyle{ G(V_T,V_N, P, S), V=V_T \cup V_N }[/math] все правила имеют вид[3]:
- [math]\displaystyle{ \alpha A \beta \rarr \alpha \gamma \beta }[/math], где [math]\displaystyle{ \alpha, \beta \in V^*, \gamma \in V^+, A \in V_N }[/math]. Такие грамматики относят к контекстно-зависимым.
- [math]\displaystyle{ \alpha \rarr \beta }[/math], где [math]\displaystyle{ \alpha, \beta \in V^+, 1\le|\alpha|\le|\beta| }[/math]. Такие грамматики относят к неукорачивающим.
Эти классы грамматик эквивалентны. Могут использоваться при анализе текстов на естественных языках, однако при построении компиляторов практически не используются в силу своей сложности. Для контекстно-зависимых грамматик доказано утверждение: по некоторому алгоритму за конечное число шагов можно установить, принадлежит цепочка терминальных символов данному языку или нет.
Тип 2 — контекстно-свободные
К этому типу относятся контекстно-свободные (КС) грамматики. Для грамматики [math]\displaystyle{ G(V_T,V_N,P, S), V=V_T \cup V_N }[/math] все правила имеют вид:
- [math]\displaystyle{ A \rarr \beta }[/math], где [math]\displaystyle{ \beta \in V^+ }[/math] (для неукорачивающих КС-грамматик) или [math]\displaystyle{ \beta \in V^* }[/math] (для укорачивающих), [math]\displaystyle{ A \in V_N }[/math]. То есть грамматика допускает появление в левой части правила только нетерминального символа.
КС-грамматики широко применяются для описания синтаксиса компьютерных языков (см. синтаксический анализ).
Тип 3 — регулярные
К третьему типу относятся регулярные грамматики (автоматные) — самые простые из формальных грамматик. Они являются контекстно-свободными, но с ограниченными возможностями.
Все регулярные грамматики могут быть разделены на два эквивалентных класса, которые для грамматики вида III будут иметь правила следующего вида:
- [math]\displaystyle{ A \rarr B\gamma }[/math] или [math]\displaystyle{ A \rarr \gamma }[/math], где [math]\displaystyle{ \gamma \in V_T^*, A, B \in V_N }[/math] (для леволинейных грамматик).
- [math]\displaystyle{ A \rarr \gamma B }[/math]; или [math]\displaystyle{ A \rarr \gamma }[/math], где [math]\displaystyle{ \gamma \in V_T^*, A, B \in V_N }[/math] (для праволинейных грамматик).
Регулярные грамматики применяются для описания простейших конструкций: идентификаторов, строк, констант, а также языков ассемблера, командных процессоров и др.
Классификация языков
Формальные языки классифицируются в соответствии с типами грамматик, которыми они задаются. Однако, один и тот же язык может быть задан разными грамматиками, относящимися к разным типам. В таком случае, считается, что язык относится к наиболее простому из них. Так, язык, описанный грамматикой с фразовой структурой, контекстно-зависимой и контекстно-свободной грамматиками, будет контекстно-свободным.
Так же, как и для грамматик, сложность языка определяется его типом. Наиболее сложные — языки с фразовой структурой (сюда можно отнести естественные языки), далее — КЗ-языки, КС-языки и самые простые — регулярные языки.
Примечания
- ↑ Кук, Бейз, 1990, с. 258,264.
- ↑ Серебряков В. А., Галочкин М. П., Гончар Д. Р., Фуругян М. Г. Теория и реализация языков программирования. — М. : МЗ-Пресс, 2006. — С. 21. — ISBN 5-94073-094-9.
- ↑ Кук, Бейз, 1990, с. 268.
Литература
- Молчанов А. Ю. Системное программное обеспечение. СПб.: Питер, 2006.
- Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. ГЛАВА 5. Контекстно-свободные грамматики и языки // Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1.
- Серебряков В. А., Галочкин М. П., Гончар Д. Р., Фуругян М. Г. Теория и реализация языков программирования — М.: МЗ-Пресс, 2006 г., 2-е изд. — ISBN 5-94073-094-9
- Робин Хантер. Основные концепции компиляторов = The Essence of Compilers. — М.: «Вильямс», 2002. — С. 256. — ISBN 5-8459-0360-2.
- Кук Д., Бейз Г. Глава 8. Языки и грамматики // Компьютерная математика = Computer Mathematics. — М.: Наука. Физматлит, 1990. — 384 с. — ISBN 5-02-014216-6.