Грамматики первого типа называют КОНТЕКСТНО-ЗАВИСИМЫМИ (или просто КЗ ). В большинстве случаев разумно принять общее ограничение, что правило заменяет строго один нетерминальный символ. Отличительная особенность КЗ –правил в том, что замена нетерминального символа на строку допускается, когда этот символ находится в некотором окружении других символов (в контексте). Например, нетерминальный символ «оператор» может быть заменен на нетерминальный символ «пустой оператор», если в преобразуемой строке перед символом «оператор» был другой символ, за которым непосредственно следовал «оператор». А иначе такую замену делать нельзя.

Представьте например, правило официанта. Осуществлять замену грязной тарелки на выписанный счет можно при наличии опустошенного бокала. В другом контексте (при полном бокале [граненом стакане] рядом) вместо грязной тарелки клиенту предлагается новая закуска.

Для того, чтобы грамматика относилась к типу КЗ достаточно, чтобы хотя бы одно правило было именно первого типа. (Остальные могут быть других типов, кроме нулевого).

Грамматики второго типа называют КОНТЕКСТНО-СВОБОДНЫМИ (или просто КС ). Каждое правило может применяться без оглядки на контекст. Вместо грязной тарелки – новая закуска (без всяких дополнительных условий)… Грамматики разных типов могут порождать один и тот же язык. Компиляторы диктуют требование приводить грамматику к типу КС . Обычно в рамках уже этого типа накладываются дополнительные ограничения, что позволяет существенно упростить грамматический разбор в компиляторе.

Грамматики последнего третьего типа называются АВТОМАТНЫМИ или РЕГУЛЯРНЫМИ . Это связано с тем, что они порождаются и распознаются автоматами (эту математическую модель ассоциируют не с Калашниковым, а с фамилиями математиков-логиков Мили Мура Трахтенбротта и т. п.) и регулярными выражениями (это, как и в регулярной армии – выражения строятся по простым правилам и просто распознаются – это тоже математическая модель).

Обычно автоматные грамматики используются на уровне лексики. Лексема, в обычном понимании – это словарная единица. Тем ни менее, с точки зрения компилятора это «символ», коль скоро «словом» будет вся программа. В данном случае, например, 345.08 может быть распознан как один символ – действительное число.

Лексический анализ в компиляторе предшествует синтаксическому анализу… Существуют знаменитые команды UNIX lex и yacc , который позволяют автоматизировать процесс написания лексического и синтаксического анализаторов компилятора.

Что– то мы очень уклонились в сторону программирования. Программирование -это тоже математика. Тоже дискретная. Но уже другая. И это другая история.

А из программирования уже, обычно, так просто не возвращаются…