Беркли Якк
| Оригинальный автор(ы) | Роберт Корбетт |
|---|---|
| Разработчик(и) | Томас Дики |
| Первоначальный выпуск | 2 сентября 1989 г [1] |
| Стабильная версия | 20240109 [2]  / 9 января 2024 г |
| Репозиторий | |
| Написано в | АНСИ С89 |
| Операционная система | Unix-подобный |
| Тип | Генератор парсера |
| Лицензия | общественное достояние |
| Веб-сайт | невидимый остров |
Berkeley Yacc ( byacc ) — Unix генератор синтаксического анализатора , разработанный для совместимости с Yacc . Первоначально он был написан Робертом Корбеттом и выпущен в 1989 году. [3] Благодаря либеральной лицензии и более быстрой скорости, чем AT&T Yacc, он быстро стал самой популярной версией 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]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б Корбетт, Роберт (2 сентября 1989 г.). «Генератор парсера PD LALR(1)» . Группа новостей : comp.compilers . Usenet: [электронная почта защищена] . Проверено 17 сентября 2021 г.
- ^ «Индекс /archives/byacc» .
- ^ Дуг Браун; Джон Левин; Тони Мейсон (октябрь 1992 г.), lex & yacc (2-е изд.), O'Reilly Media
- ^ Джон Левин (август 2009 г.), flex & bison , O'Reilly Media
- ^ «Беркли Якк» . invisible-island.net . Архивировано из оригинала 19 октября 2020 г. Проверено 10 ноября 2020 г.
... поддержка реентерабельного кода, который развился до такой степени, что его можно сравнивать и настраивать против bison.
- ^ "Журнал изменений Berkeley Yacc, см. запись "2010-06-07 Andres.Meji" " . 07.06.2010. Архивировано из оригинала 10 ноября 2020 г. Проверено 10 ноября 2020 г.
- ^ ДеРемер, Фрэнк; Пеннелло, Томас (октябрь 1982 г.). «Эффективное вычисление наборов упреждающего просмотра LALR (1)» (PDF) . АКМ Транс. Программа. Ланг. Сист. 4 (4). АКМ : 615–649. дои : 10.1145/69622.357187 . ISSN 0164-0925 . S2CID 52833742 . Проверено 26 августа 2017 г.
- ^ Корбетт, Роберт (24 сентября 1998 г.). «Re: Кто-нибудь расширял MAXTABLE в парсерах yacc?» . Группа новостей : comp.compilers . Usenet: [электронная почта защищена] . Проверено 26 августа 2017 г.
- ^ Корбетт, Роберт Пол (июнь 1985 г.). Статическая семантика и восстановление ошибок компилятора (доктор философии). Калифорнийский университет в Беркли . ДТИК ADA611756 .
- ^ Корбетт, Роберт (6 сентября 1989 г.). «Назовите этот генератор анализатора PD» . Группа новостей : comp.compilers . Usenet: [электронная почта защищена] . Проверено 26 августа 2017 г.
- ^ Корбетт, Роберт (3 октября 1989 г.). «Беркли Якк (новая версия)» . Группа новостей : comp.compilers . Usenet: [электронная почта защищена] . Проверено 17 сентября 2021 г.
- ^ Додд, Крис (7 марта 1995 г.). «BTYACC — yacc с обратным отслеживанием и унаследованными атрибутами» . Группа новостей : comp.compilers . Usenet: [электронная почта защищена] . Проверено 17 сентября 2021 г.
- ^ «README.txt» . BtYacc: обратное отслеживание Yacc. Сибирские Системы . Проверено 14 мая 2020 г.
- ^ «README.BYACC» . Возврат yacc. Гитхаб . Проверено 12 августа 2022 г.
- ^ Меррилл, Гэри Х. (1 августа 1993 г.). «Разбор грамматик, отличных от LR (k), с помощью yacc». Программное обеспечение: практика и опыт . 23 (8): 829–850. CiteSeerX 10.1.1.14.1958 . дои : 10.1002/спе.4380230803 . ISSN 0038-0644 . S2CID 14695500 .
- ^ "btyacc(1)" . Растяжка Debian — Руководства Debian .
- ^ Додд, Крис (13 февраля 2019 г.). "КрисДодд/btyacc" . Гитхаб .
- ^ Терстон, Адриан Д.; Корди, Джеймс Р. (2006). «Алгоритм LR с возвратом для анализа неоднозначных контекстно-зависимых языков» (PDF) . В Эрдогмусе, Хакан; Струля, Элени; Стюарт, Дарлин А. (ред.). Материалы конференции Центра перспективных исследований совместных исследований 2006 г., 16–19 октября 2006 г., Торонто, Онтарио, Канада . КАСКОН 2006. стр. 39–53. CiteSeerX 10.1.1.518.7094 . дои : 10.1145/1188966.1188972 . Проверено 14 мая 2020 г.
- ^ Маслов, Вадим (8 октября 1997 г.). «Доступна версия 1.1 BtYacc (Backtracking Yacc)» . Группа новостей : comp.compilers . Usenet: [электронная почта защищена] . Проверено 17 сентября 2021 г.
- ^ «BtYacc: генератор синтаксического анализатора Yacc с обратным отслеживанием» . Сибирские Системы . Проверено 18 мая 2020 г.
- ^ Jump up to: а б «БАЙАКК-БЕРКЛИ ЯКК» . invisible-island.net . Архивировано из оригинала 6 апреля 2002 г. Проверено 10 ноября 2020 г.
- ^ «Выпуск t20140407» . ThomasDickey/byacc-снапшоты. Гитхаб . Проверено 18 мая 2020 г.
- ^ «БЛАГОДАРНОСТИ» . elfprince13/PyByacc. Гитхаб . 14 января 2013 г. Проверено 1 ноября 2021 г.
- ^ "tyacc-0.9.README" . паб/языки/tcl/ibp. ftp.funet.fi . Проверено 1 ноября 2021 г.
- ^ «Домашняя страница BYACC/Java» . Боб Джеймисон. ЛинКом Инновации АСГ . Архивировано из оригинала 5 декабря 1998 г.
- ^ "master/src/skeleton.c" . поакк/дж. СоурсФордж . Проверено 28 октября 2021 г.
- ^ «Беркли Якк» . СоурсФордж . Проверено 1 ноября 2021 г.
- ^ "elfprince13/PyByacc" . Гитхаб . 14 января 2013 г. Проверено 1 ноября 2021 г.
- ^ «BYACC, производящий парсеры Perl/Tcl» . Домашняя страница Дэйва Боденстаба . Архивировано из оригинала 1 мая 2021 г.