YACC

YACC (Yet Another Compiler-Compiler) — это генератор синтаксических анализаторов (парсеров), используемый для автоматического построения программ, выполняющих синтаксический разбор формальных языков. YACC относится к классу инструментов LALR(1) (Look-Ahead Left-to-right Rightmost derivation) и принимает на вход формальное описание грамматики языка в форме контекстно-свободной грамматики с ограниченным предпросмотром на один символ. Результатом работы YACC является исходный код на языке C, реализующий детерминированный синтаксический анализатор с таблицей переходов, построенной по алгоритму LALR. YACC был разработан Стивеном Джонсоном в 1975–1978 годах в Bell Labs (США) и стал частью операционной системы Unix.

История

Предпосылки создания

В начале 1970-х годов в Bell Labs велась активная работа по созданию компиляторов для языков программирования, в частности для языка C. Разработка компиляторов вручную требовала значительных трудозатрат и была подвержена ошибкам. Для автоматизации процесса создания синтаксических анализаторов Стивен Джонсон, работавший в отделе компьютерных наук, предложил инструмент, который бы генерировал код парсера на основе формального описания грамматики.

Разработка и первые версии

Первая версия YACC была написана на языке C и впервые включена в состав Unix (версия 7) в 1979 году. Изначально YACC был ориентирован на генерацию парсеров для компиляторов, но быстро нашёл применение в других задачах, связанных с обработкой структурированных данных, таких как разбор конфигурационных файлов, командных языков и протоколов. В 1980-х годах YACC был портирован на множество платформ, включая BSD, System V и другие варианты Unix.

Распространение и стандартизация

С развитием POSIX (Portable Operating System Interface) YACC был включён в стандарт POSIX.1-2001, что обеспечило его переносимость между различными Unix-подобными системами. Однако из-за патентных ограничений и лицензионных споров вокруг AT&T, оригинальный YACC не был доступен как свободное программное обеспечение. Это привело к появлению альтернативных реализаций, наиболее известной из которых является GNU Bison (1985 год), разработанная Робертом Корбеттом и Ричардом Столлманом. Bison совместим с YACC по синтаксису входных файлов, но имеет расширенные возможности, включая поддержку GLR (Generalized LR) и генерацию кода на C++.

Принцип работы

Входные данные

YACC принимает на вход файл с расширением .y, содержащий три секции, разделённые символами %%:

1. Секция объявлений — включает определения токенов (терминалов), типов данных, начального символа грамматики, а также директивы для препроцессора C.
2. Секция правил грамматики — описывает продукцию (правила вывода) в форме Бэкуса-Наура (BNF) с расширениями, такими как действия на C, выполняемые при свёртке правила.
3. Секция вспомогательных функций — содержит код на C, который может включать лексический анализатор (обычно вызываемый через yylex()), обработчики ошибок и функции main.

Процесс генерации

YACC выполняет следующие шаги:

• Лексический анализ — не выполняется самим YACC; для разбора потока токенов требуется внешний лексический анализатор (например, Lex или Flex), который передаёт токены через глобальную переменную yylval и функцию yylex().
• Построение таблицы LALR(1) — на основе грамматики строится детерминированный конечный автомат с таблицами действий (shift/reduce) и переходов (goto). Для этого применяется алгоритм, основанный на построении множества LR(1)-ситуаций и последующем слиянии состояний с одинаковыми ядрами.
• Генерация кода — создаётся файл y.tab.c (или имя_файла.tab.c при использовании опции -o), содержащий реализацию парсера, таблицы и вспомогательные функции.

Выходные данные

Результатом работы YACC является программа на C, которая после компиляции и линковки с лексическим анализатором и пользовательским кодом образует готовый синтаксический анализатор. Парсер выполняет восходящий разбор (bottom-up), используя стек состояний и символов. При обнаружении ошибки вызывается функция yyerror(), которую пользователь может переопределить.

Синтаксис и структура файла YACC

Объявления

В секции объявлений задаются:

• %token — объявление терминалов (токенов), например, %token NUMBER PLUS MINUS.
• %type — указание типа данных для нетерминалов, например, %type <val> expr.
• %start — явное указание начального символа грамматики (по умолчанию — первый нетерминал в первой продукции).
• %union — объединение для хранения значений токенов и нетерминалов.
• %left, %right, %nonassoc — задание ассоциативности и приоритета операторов.

Правила грамматики

Правила записываются в виде: `` expr: expr '+' term { $$ = $1 + $3; } | term { $$ = $1; } ; ` Здесь $1, $3 — ссылки на значения символов в правой части правила, а $$` — значение, присваиваемое левой части. Действия на C выполняются в момент свёртки (reduction).

Вспомогательные функции

В этой секции обычно размещаются:

• Функция yylex() — лексический анализатор, возвращающий тип токена и устанавливающий его значение в yylval.
• Функция yyerror() — обработчик синтаксических ошибок.
• Функция main() — точка входа программы.

Применение

Разработка компиляторов и интерпретаторов

YACC традиционно используется для создания синтаксических анализаторов в компиляторах языков программирования. Например, компилятор языка C (pcc) и ранние версии компилятора C++ (cfront) использовали YACC. В современных проектах YACC и Bison применяются в компиляторах для языков Python, Ruby, PHP, а также в специализированных инструментах, таких как SQL-парсеры.

Обработка конфигурационных файлов

Многие программы используют YACC для разбора сложных конфигурационных файлов, например, в системах управления базами данных (PostgreSQL, MySQL) и в сетевых сервисах (Apache HTTP Server, BIND).

Генерация кода

YACC может применяться для автоматического преобразования описаний из одного формата в другой, например, для генерации документации, кода на других языках или схем данных.

Образовательные цели

YACC широко используется в учебных курсах по компиляторам и формальным языкам для демонстрации принципов синтаксического анализа и построения трансляторов.

Ограничения и критика

Ограниченный класс грамматик

YACC поддерживает только LALR(1)-грамматики, что накладывает ограничения на выразительность. Некоторые грамматики, не являющиеся LALR(1), требуют модификации (например, введения дополнительных нетерминалов или изменения правил). Для преодоления этого ограничения в Bison была добавлена поддержка GLR-парсеров, которые могут обрабатывать неоднозначные грамматики.

Сложность отладки

Ошибки в грамматике, такие как конфликты shift/reduce или reduce/reduce, могут быть трудно диагностируемы. YACC выводит предупреждения о конфликтах, но не указывает точную причину. Для отладки часто требуется ручной анализ таблиц или использование опции -v для генерации файла .output с детальным описанием состояний.

Зависимость от лексического анализатора

YACC не включает встроенный лексический анализатор, что требует интеграции с внешними инструментами (Lex, Flex) или ручного написания yylex(). Это увеличивает сложность разработки и может привести к несоответствиям между лексическим и синтаксическим анализаторами.

Производительность

Для больших грамматик (сотни правил) таблицы LALR(1) могут занимать значительный объём памяти (до нескольких мегабайт), что критично для встраиваемых систем. Однако в большинстве современных приложений это не является проблемой.

Альтернативы

GNU Bison

Bison (GNU Bison) — наиболее распространённая свободная альтернатива YACC, совместимая с ним по синтаксису. Bison поддерживает расширения, такие как GLR-парсеры, генерация кода на C++, Java, Python, а также улучшенные сообщения об ошибках.

ANTLR

ANTLR (Another Tool for Language Recognition) — генератор парсеров для LL(*)-грамматик, поддерживающий множество языков (Java, C#, Python, JavaScript). В отличие от YACC, ANTLR использует нисходящий разбор (top-down) и автоматически генерирует лексический анализатор.

PEG-парсеры

PEG (Parsing Expression Grammar) — альтернативный подход, основанный на рекурсивном спуске с возвратами. Инструменты, такие как PEG.js, Packrat, предоставляют более гибкое описание грамматик, но могут иметь экспоненциальную сложность в худшем случае.

Ручное написание парсеров

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

Интересные факты

• Название «YACC» расшифровывается как «Yet Another Compiler-Compiler», что отражает ироничное отношение к обилию подобных инструментов в 1970-х годах.
• YACC был одним из первых инструментов, продемонстрировавших практическую применимость теории формальных языков (работы Дональда Кнута по LR-разбору).
• Исходный код YACC, написанный Стивеном Джонсоном, содержал около 2000 строк на C, что по современным меркам является очень компактной реализацией.
• YACC входит в стандарт POSIX, но его использование в коммерческих продуктах было ограничено до 1990-х годов из-за лицензионных условий AT&T.
• Многие современные компиляторы, включая GCC, используют Bison, а не оригинальный YACC, благодаря его свободной лицензии и расширенным возможностям.

Источники

• Стивен Джонсон. «YACC: Yet Another Compiler-Compiler». Bell Laboratories, 1975.
• Альфред Ахо, Моника Лам, Рави Сети, Джеффри Ульман. «Компиляторы: принципы, технологии и инструменты» (2-е издание), 2006.
• Документация GNU Bison (версия 3.8), 2022.
• Стандарт POSIX.1-2001, раздел «yacc — a compiler-compiler».
• Джон Левин. «Flex & Bison: Text Processing Tools», O'Reilly Media, 2009.