Иерархия Хомского: Формальные грамматики и языки программирования
Как научить компьютер "понимать" текст? Будь то исходный код на языке C++, поисковый запрос или фраза на русском языке — для алгоритмической обработки текста требуется математическая модель, описывающая правила его построения. В 1956 году выдающийся лингвист и математик Ноам Хомский создал классификацию формальных грамматик, которая стала фундаментом для теории компиляторов и компьютерной лингвистики (NLP).
Формальная грамматика — это строгий набор математических правил (продукций), по которым из символов алфавита можно генерировать допустимые строки языка. Иерархия Хомского делит все возможные формальные языки на четыре вложенных класса (от самых сложных к самым простым), причем каждому классу грамматик соответствует строго определенный тип вычислительной машины, способной этот язык распознать:
Тип 0: Рекурсивно перечислимые языки (Unrestricted). Самый широкий класс. В правилах замены нет никаких ограничений: любую цепочку символов можно заменить на любую другую. Эти языки распознаются только Машиной Тьюринга. Они способны описать любую вычислимую функцию, но алгоритмически неразрешима проблема проверки того, принадлежит ли случайная строка этому языку (из-за проблемы остановки).
Тип 1: Контекстно-зависимые языки (Context-sensitive). Правила разрешают заменять символ только если он окружен определенным контекстом (соседями). Длина правой части правила должна быть не меньше левой. Распознаются линейно-ограниченными автоматами (Тьюринг-машина с ограниченной лентой). Естественные человеческие языки находятся примерно на этом уровне сложности.
Тип 2: Контекстно-свободные языки (Context-free, КС-языки). Самый важный класс для программистов. Правило замены выглядит просто: один единственный нетерминальный символ слева заменяется на любую последовательность справа, независимо от окружающего текста. Эти языки распознаются автоматами с магазинной памятью (Pushdown Automata, стэковые автоматы). Синтаксис абсолютно всех современных языков программирования (Java, Python, PHP) описывается КС-грамматиками. Для их спецификации используется стандарт Бэкуса-Наура (BNF). Именно этот класс языков позволяет описывать вложенные конструкции: скобки внутри скобок, циклы внутри циклов.
Тип 3: Регулярные языки (Regular). Самый простой и строгий класс. Правила замены жестко ограничены (один нетерминал порождает терминал и, возможно, еще один нетерминал с одного края). Распознаются конечными автоматами (FSM). Эти языки не имеют "памяти" (не могут посчитать баланс открывающихся и закрывающихся скобок), но они лежат в основе всем известных регулярных выражений (RegEx). Лексические анализаторы компиляторов используют регулярные грамматики для разбиения сплошного текста кода на токены (числа, переменные, ключевые слова) перед передачей их синтаксическому КС-анализатору.
