Введение

Программа Unix для генерации парсеров. Berkeley Yacc (byacc) — это генератор парсеров Unix, разработанный для совместимости с Yacc. Он был первоначально написан Робертом Корбетом и выпущен в 1989 году. Благодаря своей либеральной лицензии и более высокой скорости работы по сравнению с AT&T Yacc, он быстро стал самой популярной версией Yacc. Он обладает преимуществами, такими как реализация на ANSI C89 и статус программного обеспечения, находящегося в общественном достоянии. В нем реализованы функции, отсутствующие в Yacc, например, возможность повторного входа, которая совместима с GNU Bison.

История

В 1985 году Роберт Корбет разработал оригинальный генератор LALR-анализатора на основе статьи Деремера и Пеннелло 1982 года. Корбет написал его в рамках своего исследования для получения степени Ph. D., которую он получил в Университете Калифорнии в Беркли в июне 1985 года. Изначально он назывался Byson и был несовместим с Yacc, но впоследствии был переименован в Bison и стал основой GNU Bison. Позже, в 1985 году, Корбет разработал свой генератор LALR-анализатора, сделав его совместимым с Yacc и назвав его Zeus, но затем переименовав в Zoo. Корбет опубликовал исходный код Zoo в Usenet-группе новостей, но он остался в основном незамеченным до сентября 1989 года, когда Корбет разместил сообщение в группе новостей comp.compilers о размещении исходного кода на FTP-сервере. В 1995 году Крис Додд разработал BtYacc, производную от Berkeley Yacc, для поддержки анализа контекстно-зависимых языков, таких как C++, на основе статьи Меррилла 1993 года, описывающей аналогичные модификации AT&T Yacc. Его возможности отката и семантической деамбигуации позволяют генерировать анализаторы для неоднозначных грамматик. Правило, проанализированное, но отклоненное на основе семантической информации, может быть отменено, чтобы анализатор мог попробовать другое правило. Однако его также критиковали за необходимость побочно-эффектных пробных действий и негибкое разрешение конфликтов сдвига-сокращения. В 1997 году Вадим Маслов взял на себя поддержку BtYacc для COBOL-анализатора, разработанного его компанией. К 1999 году последняя версия 3.0 была переписана на C++, что означало, что она больше не реализована на C.

В 2000 году Томас Э. Дикки портировал Berkeley Yacc на OpenVMS для облегчения переноса tin на VMS. Не найдя другого сопровождающего, Дикки поддерживает Berkeley Yacc с февраля 2002 года. Значительным обновлением стал переход от K&R C к ANSI C89.

Языки

Парсер-генераторы обычно работают с тремя языками: языком, на котором реализован сам генератор, языком, на котором реализован генерируемый парсер, и, конечно же, метаязыком, описывающим, что должен разбирать генерируемый парсер. Четвертый язык можно рассматривать как язык, который разбирает сгенерированный парсер, но парсер-генераторы не обрабатывают его напрямую, а сосредотачиваются на генерации парсера из заданного описания, позволяя уже сгенерированному парсеру работать с этим языком. Yacc написан на C и генерирует парсеры на C из описаний своего собственного метаязыка Yacc. То же самое относится и к Berkeley Yacc (отсюда и его совместимость), однако было создано несколько производных, позволяющих генерировать парсеры на языках, отличных от C.

Рэй Лишнер разработал perl byacc (pbyacc) на основе byacc 1.6, чтобы он также мог генерировать парсеры на Perl. Позже Ричард "Рик" Онемус перенес исправления из byacc 1.6 в byacc 1.8. А позднее, в 1996 году, Джейк Донхэм разработал p5yacc на основе perl yacc 1.8.2, чтобы сгенерированные Perl-парсеры использовали классы Perl 5. В 1994 году Майк Клейн разработал tyacc на основе perl yacc 1.8.2, чтобы он также мог генерировать парсеры на Tcl.

В 1997 году Боб Джеймисон разработал BYACC/Java (позже названный BYACC/J или byaccj) на основе byacc 1.8, чтобы он также мог генерировать парсеры на Java. В 2000 году Брюс Бахнен объединил возможности Java-парсера BYACC/J с perl yacc и добавил возможность генерировать парсеры на Python. В 2013 году Томас Дикерсон внес в него дальнейшие улучшения, назвав его PyByacc. В 2003 году Дэйв Боденстаб объединил tyacc и p5yacc для разработки PERL TCL YACC, взяв за основу версию 4.8 yacc из FreeBSD (производная от byacc).