Berkeley Yacc ( byacc ) — это генератор парсеров Unix , разработанный для совместимости с Yacc . Первоначально он был написан Робертом Корбеттом и выпущен в 1989 году. [3] Благодаря своей либеральной лицензии и более высокой скорости, чем Yacc от AT&T, он быстро стал самой популярной версией Yacc. [4] Он имеет преимущества, поскольку написан на ANSI C89 и является программным обеспечением, находящимся в общественном достоянии .
Он содержит функции, недоступные в Yacc, такие как повторный вход, который реализован таким образом, что он в целом совместим с GNU Bison . [5] [6]
В 1985 году Роберт Корбетт разработал оригинальный генератор синтаксического анализатора LALR, основанный на статье ДеРемера и Пеннелло 1982 года. [7] Корбетт написал его как часть своего исследования для получения докторской степени в Калифорнийском университете в Беркли в июне 1985 года. [8] [9] Первоначально он назывался Byson и был несовместим с Yacc , но впоследствии был переименован в Bison и стал основой GNU Bison .
Позже в 1985 году Корбетт разработал свой генератор парсеров LALR, сделав его совместимым с Yacc и назвав его Zeus, но впоследствии переименовав его в Zoo. [10] Корбетт опубликовал исходный код Zoo в новостной группе Usenet, но он оставался практически незамеченным до сентября 1989 года, когда Корбетт опубликовал в новостной группе comp.compilers сообщение о размещении исходного кода на FTP-сервере . [1] Было обсуждение его переименования, и к октябрю 1989 года он стал известен как Berkeley Yacc (byacc). [11]
В 1995 году Крис Додд разработал BtYacc, производную Berkeley Yacc с возвратом для поддержки разбора контекстно-зависимых языков, таких как C++ , [12] [13] на основе статьи Меррилла 1993 года, описывающей аналогичные модификации AT&T Yacc. [14] [15] Его возможности возврата и устранения семантической неоднозначности позволяют ему генерировать парсеры для неоднозначных грамматик . Правило, проанализированное, но отклоненное семантической информацией, может быть откатено, так что парсер может попробовать другое правило. [16] [17] Однако его также критиковали за необходимость в пробных действиях без побочных эффектов и негибкую обработку конфликтов сдвига-свертки. [18]
В 1997 году Вадим Маслов взял на себя поддержку BtYacc для поддержки синтаксического анализатора COBOL , разработанного его компанией. [19] К 1999 году последний релиз 3.0 был преобразован в C++ , что сделало его более не реализованным на C. [20]
В 2000 году Томас Э. Дики перенес Berkeley Yacc на OpenVMS, чтобы облегчить перенос tin на VMS. После неудачной попытки найти другого сопровождающего, Дики поддерживал Berkeley Yacc с февраля 2002 года. [21] Значительным обновлением стал переход с K&R C на ANSI C89 . [21]
В 2014 году Том Шилдс интегрировал возврат BtYacc в Berkeley Yacc, фактически поглотив BtYacc и снова поддержав C (вместо только C++) в выпусках Dickey с апреля 2014 года. [22]
Генераторы парсеров обычно работают с тремя языками: языком, на котором реализован генератор, языком, на котором реализован сгенерированный парсер, и, конечно, метаязыком , который описывает то, что должен анализировать сгенерированный парсер. Четвертым языком можно считать любой язык, который анализирует сгенерированный парсер, но генераторы парсеров не обрабатывают это напрямую, вместо этого просто сосредотачиваясь на генерации парсера из заданного описания, позволяя сгенерированному парсеру иметь дело с этим. Yacc написан на C и генерирует парсеры на C из собственных описаний метаязыка Yacc. Таким же образом работает Berkely Yacc (отсюда его совместимость), однако было создано несколько производных, позволяющих ему генерировать парсеры на языках, отличных от C.
Рэй Лишнер разработал perl-byacc (pbyacc) из byacc 1.6, так что он также мог генерировать парсеры на Perl . Позже Ричард «Рик» Онемус перенес патчи из byacc 1.6 в byacc 1.8. [23] А позже в 1996 году Джейк Донхэм разработал p5yacc из perl-yacc 1.8.2, так что его сгенерированные парсеры Perl использовали классы Perl 5 .
В 1994 году Майк Клейн разработал tyacc из perl-yacc 1.8.2, чтобы он мог также генерировать парсеры в Tcl [24]
В 1997 году Боб Джеймисон разработал BYACC/Java (позже названный BYACC/J или byaccj) из byacc 1.8, так что он также мог генерировать парсеры на Java . [25] [26]
В 2000 году Брюс Бансен объединил возможности парсера Java BYACC/J с perl-yacc и добавил возможность генерировать парсеры на Python . [27] В 2013 году Томас Дикерсон внес в него дальнейшие улучшения, назвав его PyByacc. [28]
В 2003 году Дэйв Боденстаб объединил tyacc и p5yacc для разработки PERL-TCL-YACC, переместив его с версии 4.8 yacc из FreeBSD (производной byacc). [29]
...поддержка реентерабельного кода, которая развилась в byacc до такой степени, что ее можно сравнивать и настраивать с помощью bison.