Иерархия Хомского

Иерархия Хомского — классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности. Предложена профессором Массачусетского технологического института, лингвистом Ноамом Хомским.

Классификация грамматикПравить

Согласно Хомскому, формальные грамматики можно разделить на четыре типа. Для отнесения грамматики к тому или иному типу необходимо соответствие всех её правил (продукций) некоторым схемам.

Тип 0 — неограниченныеПравить

Грамматика с фразовой структурой G — это алгебраическая структура, упорядоченная четвёрка (V_T, V_N, P, S), где:

• $V_T$$V_{T}$  — алфавит (множество) терминальных символов — терминалов,
• $V_N$$V_{N}$  — алфавит (множество) нетерминальных символов — нетерминалов,
• $V=V_T\cup <!--\; \cup \; -->V_N$$V=V_{T}\cup V_{N}$  — словарь $G$$G$ , причём $V_T\cap <!--\; \cap \; -->V_N=\mathrm{\varnothing <!--\; \varnothing \; -->}$$V_{T}\cap V_{N}=\varnothing$ 
• $P$$P$  — конечное множество продукций (правил) грамматики, $P\subseteq <!--\; \subseteq \; -->V^{+}\times <!--\; \times \; -->V^{\ast <!--\; \ast \; -->}$$P\subseteq V^{+}\times V^{*}$ 
• $S$$S$  — начальный символ (источник).

Здесь $V^{\ast <!--\; \ast \; -->}$$V^*$  — множество всех строк над алфавитом $V$$V$ , а $V^{+}$$V^{+}$  — множество непустых строк над алфавитом $V$$V$ .

К типу 0 по классификации Хомского относятся неограниченные грамматики — грамматики с фразовой структурой, то есть все без исключения формальные грамматики. Правила можно записать в виде:

$\mathrm{\alpha <!--\; \alpha \; -->}\to <!--\; \to \; -->\mathrm{\beta <!--\; \beta \; -->}$$\alpha \rightarrow \beta$ ,

где $\mathrm{\alpha <!--\; \alpha \; -->}\in <!--\; \in \; -->V^{+}$$\alpha \in V^{+}$  — любая непустая цепочка, содержащая хотя бы один нетерминальный символ, а $\mathrm{\beta <!--\; \beta \; -->}\in <!--\; \in \; -->V^{\ast <!--\; \ast \; -->}$$\beta \in V^{*}$  — любая цепочка символов из алфавита.

Практического применения в силу своей сложности такие грамматики не имеют.

Тип 1 — контекстно-зависимыеПравить

К этому типу относятся контекстно-зависимые (КЗ) грамматики и неукорачивающие грамматики. Для грамматики $G(V_T,V_N,P,S),V=V_T\cup <!--\; \cup \; -->V_N$$G(V_{T},V_{N},P,S),V=V_{T}\cup V_{N}$  все правила имеют вид:

• $\mathrm{\alpha <!--\; \alpha \; -->}A\mathrm{\beta <!--\; \beta \; -->}\to <!--\; \to \; -->\mathrm{\alpha <!--\; \alpha \; -->}\mathrm{\gamma <!--\; \gamma \; -->}\mathrm{\beta <!--\; \beta \; -->}$$\alpha A\beta \rightarrow \alpha \gamma \beta$ , где $\mathrm{\alpha <!--\; \alpha \; -->},\mathrm{\beta <!--\; \beta \; -->}\in <!--\; \in \; -->V^{\ast <!--\; \ast \; -->},\mathrm{\gamma <!--\; \gamma \; -->}\in <!--\; \in \; -->V^{+},A\in <!--\; \in \; -->V_N$$\alpha ,\beta \in V^{*},\gamma \in V^{+},A\in V_{N}$ . Такие грамматики относят к контекстно-зависимым.
• $\mathrm{\alpha <!--\; \alpha \; -->}\to <!--\; \to \; -->\mathrm{\beta <!--\; \beta \; -->}$$\alpha \rightarrow \beta$ , где $\mathrm{\alpha <!--\; \alpha \; -->},\mathrm{\beta <!--\; \beta \; -->}\in <!--\; \in \; -->V^{+},1\le <!--\; \le \; -->|\mathrm{\alpha <!--\; \alpha \; -->}|\le <!--\; \le \; -->|\mathrm{\beta <!--\; \beta \; -->}|$$\alpha ,\beta \in V^{+},1\leq |\alpha |\leq |\beta |$ . Такие грамматики относят к неукорачивающим.

Эти классы грамматик эквивалентны. Могут использоваться при анализе текстов на естественных языках, однако при построении компиляторов практически не используются в силу своей сложности. Для контекстно-зависимых грамматик доказано утверждение: по некоторому алгоритму за конечное число шагов можно установить, принадлежит цепочка терминальных символов данному языку или нет.

Тип 2 — контекстно-свободныеПравить

К этому типу относятся контекстно-свободные (КС) грамматики. Для грамматики $G(V_T,V_N,P,S),V=V_T\cup <!--\; \cup \; -->V_N$$G(V_{T},V_{N},P,S),V=V_{T}\cup V_{N}$  все правила имеют вид:

• $A\to <!--\; \to \; -->\mathrm{\beta <!--\; \beta \; -->}$$A\rightarrow \beta$ , где $\mathrm{\beta <!--\; \beta \; -->}\in <!--\; \in \; -->V^{+}$$\beta \in V^{+}$  (для неукорачивающих КС-грамматик) или $\mathrm{\beta <!--\; \beta \; -->}\in <!--\; \in \; -->V^{\ast <!--\; \ast \; -->}$$\beta \in V^{*}$  (для укорачивающих), $A\in <!--\; \in \; -->V_N$$A\in V_{N}$ . То есть грамматика допускает появление в левой части правила только нетерминального символа.

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

Тип 3 — регулярныеПравить

К третьему типу относятся регулярные грамматики (автоматные) — самые простые из формальных грамматик. Они являются контекстно-свободными, но с ограниченными возможностями.

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

• $A\to <!--\; \to \; -->B\mathrm{\gamma <!--\; \gamma \; -->}$$A\rightarrow B\gamma$  или $A\to <!--\; \to \; -->\mathrm{\gamma <!--\; \gamma \; -->}$$A\rightarrow \gamma$ , где $\mathrm{\gamma <!--\; \gamma \; -->}\in <!--\; \in \; -->V_T^{\ast <!--\; \ast \; -->},A,B\in <!--\; \in \; -->V_N$$\gamma \in V_{T}^{*},A,B\in V_{N}$  (для леволинейных грамматик).
• $A\to <!--\; \to \; -->\mathrm{\gamma <!--\; \gamma \; -->}B$$A\rightarrow \gamma B$ ; или $A\to <!--\; \to \; -->\mathrm{\gamma <!--\; \gamma \; -->}$$A\rightarrow \gamma$ , где $\mathrm{\gamma <!--\; \gamma \; -->}\in <!--\; \in \; -->V_T^{\ast <!--\; \ast \; -->},A,B\in <!--\; \in \; -->V_N$$\gamma \in V_{T}^{*},A,B\in V_{N}$  (для праволинейных грамматик).

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

Классификация языковПравить

Формальные языки классифицируются в соответствии с типами грамматик, которыми они задаются. Однако, один и тот же язык может быть задан разными грамматиками, относящимися к разным типам. В таком случае, считается, что язык относится к наиболее простому из них. Так, язык, описанный грамматикой с фразовой структурой, контекстно-зависимой и контекстно-свободной грамматиками, будет контекстно-свободным.

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

ЛитератураПравить

• Молчанов А. Ю. Системное программное обеспечение. СПб.: Питер, 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.