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

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

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

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

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

${\displaystyle \alpha \rightarrow \beta }$,

где ${\displaystyle \alpha \in V^{+}}$ — любая непустая цепочка, содержащая хотя бы один нетерминальный[2] символ, а ${\displaystyle \beta \in V^{*}}$ — любая цепочка символов из алфавита.

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

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

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

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

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

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

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

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

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

• ${\displaystyle A\rightarrow B\gamma }$ или ${\displaystyle A\rightarrow \gamma }$, где ${\displaystyle \gamma \in V_{T}^{*},A,B\in V_{N}}$ (для леволинейных грамматик).
• ${\displaystyle A\rightarrow \gamma B}$; или ${\displaystyle A\rightarrow \gamma }$, где ${\displaystyle \gamma \in V_{T}^{*},A,B\in V_{N}}$ (для праволинейных грамматик).

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