Наиболее важные классы таких языков могут быть определены в рамках классификации языков, предложенной в 1959 г. американским лингвистом Н. Хомским (классификация по Хомскому). Он предложил классифицировать формальные языки по типу правил порождающих грамматик.

Класс 0. Правила вывода грамматики имеют  без каких либо ограничений на строки   и . Языки этого класса могут  служить моделью естественных языков.

Класс 1. Все элементы Р получают из формы , где =₁₂, = ₁₂, а₁, ₂V*, N, V⁺. Порождающая грамматика с такими правилами называется грамматикой непосредственно составляющих или контекстной грамматикой (HC-грамматика). Языки, порождаемые грамматиками этого класса, называют контекстно-зависимыми. В НС-грамматике каждое правило вывода указывает подстановку некоторой непустой цепочки  вместо нетерминала  при условии, что заменяемый нетерминал  находится в окружении ₁ и ₂, т.е. строки ₁ и ₂ рассматриваются как контекст, в котором можно заменить на .

Языки класса 1 могут порождаться также грамматикой, правая часть каждого правила которой не короче его левой части, т.е. длина цепочки при выводе в такой грамматике может только возрастать. Такая грамматика называется неукорачивающей. Класс НС-грамматик эквивалентен классу неукорачивающих грамматик [8]. Грамматика из примера 1.3.2.2 является НС-грамматикой, у которой ₁₂=.

Класс 2. Все порождающие правила грамматики имеют вид: А, где А — нетерминальный символ, а  — непустая цепочка из V, т.е. V⁺. Замена нетерминала А на строку  происходит без учета контекста, поэтому грамматики этого класса называют контекстно-свободными (КС-грамматиками).

Если допустить, что V^*, т.е. возможна пустая подстановка  вместо нетерминала А, то грамматика называется укорачивающей КС-грамматикой (УКС-грамматика). Доказано, что по любой УКС-грамматике можно построить почти эквивалентную КС-грамматику, т.е. порождающую тот же язык, что и исходная грамматика, за исключением пустой цепочки. УКС-грамматики представляют практический интерес потому, что именно они используются для описания языков программирования. Почти эквивалентность УКС и КС-грамматик позволяет свести изучение УКС-грамматик к изучению соответствующих свойств КС-грамматик. Поэтому КС-грамматики играют главную роль при формальном изучении синтаксиса языков программирования и построении блока синтаксического анализа транслятора.

Класс 3. Все порождающие правила имеют вид: АbB и Ab, где А, ВN, bT, т.е. правая часть правила является или единичным терминалом, или единичным терминалом, за которым следует единичный нетерминал. Языки класса 3 называют языками с конечным числом состояний или автоматными (регулярными) языками, а порождающие их грамматики – автоматными грамматиками (А-грамматики). А-грамматики используются в основном на этапе лексического анализа.

Связь между приведенными классами языков и проблемой распознавания языков формулируется следующей теоремой.

Теорема 1.3.1. Язык L(G), порождаемый неукорачивающей грамматикой G, легко распознаваем [8].

Взаимосвязь (иерархия) языков, в соответствии с классификацией Хомского, определяется нижеследующей теоремой.

Теорема 1.3.2. Если язык L(G) регулярный, то он контекстно-свободный. Если язык L(G) контекстно-свободный, то язык L(G) — НС-язык. Если язык L(G) – НС-язык, то он язык класса 0 [4].

С другой стороны, основные классы языков могут быть определены классами абстрактных распознающих устройств (автоматов), которые также образуют соответствующую иерархию. На рис. 1.2 приведена иерархия языков и соответствующие ей иерархии грамматик и автоматов как распознающих устройств, основные из которых будут подробно описаны при рассмотрении вопросов лексического и синтаксического анализа.

Из четырех классов грамматик контекстно-свободные грамматики наиболее важны в приложении к языкам программирования. С их помощью можно определить большую, хотя и не всю, часть синтаксической структуры языка программирования.

Ранее было показано, как для описания синтаксиса языка используются нормальные формы Бэкуса. Оказывается, между БНФ и КС-грамматиками есть прямая связь – они, по существу, эквивалентны, различия касаются только обозначений. Так связке «::=» из БНФ соответствует в КС-грамматике отношение , металингвистическим переменным из БНФ соответствуют в КС-грамматике нетерминальные  символы,   основным   символам   языка   программирования  из  БНФ

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

Рис. 1.2. Иерархия языков, грамматик и автоматов