Кратко и по существу — сравнение по выразительности и применению.
1) Выразительность (языки)
- Регулярные: языки, распознаваемые конечными автоматами. Обозначение включения: ${\mathcal{L}}_{\mathrm{Reg}}\subset {\mathcal{L}}_{\mathrm{CFL}}\subset {\mathcal{L}}_{\mathrm{RE}}$.
- Контекстно‑свободные (КС): генерируются КС‑грамматиками; могут выражать вложенность, например язык сбалансированных скобок $\{a^n{b}^n\mid n\ge 0\}$, который не регулярный.
- Turing‑полные / рекурсивно перечислимые: соответствуют неограниченным грамматикам или машинам Тьюринга; описывают все вычислимые/рекурсивно перечислимые множества языков.
2) Замкнутость и разрешимость
- Регулярные замкнуты относительно объединения, конкатенации, звезды, дополнения, пересечения; проблемы распознавания и эквивалентности разрешимы и эффективно решаемы.
- КС замкнуты относительно объединения, конкатенации, звезды; не замкнуты по дополнению и пересечению (в общем). Некоторые свойства (пустота, вывод для НВГ) разрешимы; эквивалентность двух общих КС‑грамматик — неразрешима в общем.
- Turing‑полные системы (рекурсивно перечислимые) не обладают многих разрешимых свойств: пустота, равенство, принадлежность часто неразрешимы в общем.
3) Сложность распознавания
- Регулярные: можно распознавать конечным автоматом за $\Theta (n)$ времени (при детерминированном автомате).
- КС: общий алгоритм (CYK) — $\Theta (n^3)$; для детерминированных подклассов (LL(k), LR(k)) — $\Theta (n)$.
- Turing‑полные: вычисление зависит от программы; в общем может быть неостановимым или иметь экспоненциальную/непредсказуемую сложность.
4) Применение в компиляторах и анализаторах
- Лексический анализ (токенизация): регулярные выражения/конечные автоматы — основной инструмент; быстро и просты для токенов.
- Синтаксический анализ (парсинг): КС‑грамматики (обычно LALR(1), LR(k), LL(k)) — подходят для описания синтаксиса языков программирования (вложенность, рекурсивные конструкции). Генераторы парсеров (yacc, bison, ANTLR) работают с КС‑грамматиками или их детерминированными подклассами.
- Семантика, проверка типов, оптимизация: требуют контекстно‑чувствующих или вычислительных механизмов; часто реализуются как алгоритмы/интерпретируемые программы (Turing‑полные), потому что проверки могут быть контекстно‑чувствующими или вообще вычислительными.
- Инструменты анализа кода (статический анализ, интерпретация): часто используют Turing‑полные формализмы/языки правил; некоторые проверки сводимы к недетерминированным/неразрешимым задачам и решаются эвристически или с ограничениями.
5) Практические замечания
- «Регулярные выражения» в реализациях (Perl, PCRE) иногда дают дополнительные конструкции (backreferences), что делает их сверхрегулярными и может привести к экспоненциальной сложности и возможности распознавать нерегулярные языки; это худшая практика для токенизации.
- Для парсеров выбирают детерминированные подклассы КС ради линейности и предсказуемости; семантические действия в парсере могут быть Turing‑полными, что усложняет формальные рассуждения.
- При проектировании компилятора разумно: регулярные для лексики, КС для синтаксиса, алгоритмические/Turing‑полные механизмы для семантики и трансформаций.
Если нужно — приведу конкретные примеры (LR(1) vs LL(1), пример НВГ и регулярного языка, опасности backreference).