Yacc - Yacc

Yacc
Оригинальный автор (ы)Стивен С. Джонсон
Репозиторий
Отредактируйте это в Викиданных
Операционная системаUnix, Unix-подобный, План 9, Inferno
ПлатформаКроссплатформенность
ТипКоманда

Yacc (Еще один компилятор-компилятор) это компьютерная программа для Unix операционная система, разработанная Стивен С. Джонсон. Это Генератор парсера Look Ahead слева направо (LALR), генерируя Парсер LALR (часть компилятор который пытается придать синтаксический смысл исходный код ) на основе формальная грамматика, записанные в обозначениях, аналогичных Форма Бэкуса – Наура (БНФ).[1] Yacc поставляется как стандартная утилита для BSD и AT&T Unix.[2] GNU -основан Linux дистрибутивы включают Бизон, прямая совместимость с заменой Yacc.[3]

История

В начале 1970-х гг. Стивен С. Джонсон, специалист по информатике в Bell Labs / AT&T, разработал Yacc, потому что он хотел вставить Эксклюзивный или оператора в Язык B компилятор (разработан с использованием Макилрой с TMG компилятор-компилятор[4]), но это оказалось непростой задачей. В результате его возглавил коллега Bell Labs. Аль Ахо к Дональд Кнут работает над LR разбор, который послужил основой для Yacc.[5] Яцк находился под влиянием[6] и получил свое название от имени компилятора-компилятора TMG.[7]

Yacc изначально был написан в Язык программирования B, но вскоре был переписан на C.[4] Он появился в составе Версия 3 Unix,[8] а полное описание Yacc было опубликовано в 1975 году.[6]

Джонсон использовал Yacc для создания Портативный компилятор C.[8] Бьярне Страуструп, с другой стороны, пытался использовать Yacc для своей первоначальной работы над C ++, но "был побежден синтаксисом C" (например, имея как префиксные, так и постфиксные операторы объявления).[9]

В интервью 2008 года Джонсон отметил, что «вклад Якка в распространение Unix и C это то, чем я горжусь больше всего ».[10]

Описание

Входными данными Yacc является грамматика с фрагментами C код (называемый «действиями»), прикрепленный к его правилам. Его вывод - парсер сдвиг-уменьшение в C, который выполняет фрагменты C, связанные с каждым правилом, как только правило распознается. Типичные действия включают построение разбирать деревья. На примере Джонсона, если звонок узел (метка, слева, справа) создает узел двоичного дерева синтаксического анализа с указанным метка и дети, то правило

выражение: выражение '+' выражение {$$ = узел ('+', $ 1, $ 3); }

распознает выражения суммирования и строит для них узлы. Специальные идентификаторы $$, $1 и $3 обратитесь к элементам парсера куча.[6]

Yacc производит только парсер (анализатор фраз); для полного синтаксического анализа требуется внешний лексический анализатор для выполнения первого этапа токенизации (анализа слов), за которым следует собственно этап синтаксического анализа.[6] Генераторы лексических анализаторов, такие как Лекс или же Flex, широко доступны. В IEEE POSIX Стандарт P1003.2 определяет функциональность и требования как для Lex, так и для Yacc.[11]

Некоторые версии AT&T Yacc стали Открытый исходный код. Например, исходный код доступен в стандартных дистрибутивах План 9.[12]

Влияние

Yacc и подобные программы (в основном повторные реализации) были очень популярны. Сам Yacc раньше был доступен в качестве генератора синтаксического анализатора по умолчанию в большинстве систем Unix, хотя с тех пор он был вытеснен более новыми, в значительной степени совместимыми программами, такими как Беркли Якк, GNU Bison, МКС Yacc и Abraxas PCYACC. Обновленная версия оригинальной версии AT&T включена как часть Солнце OpenSolaris проект. Каждый из них предлагает небольшие улучшения и дополнительные функции по сравнению с исходным Yacc, но концепция и основной синтаксис остались прежними.[13]

Среди языков, которые были впервые реализованы с Yacc: AWK, уравнение и Рис.[14] Yacc также использовался в Unix для реализации Портативный компилятор C, а также парсеры для таких языков программирования, как FORTRAN 77, Ratfor, APL, до н.э, м4, так далее.[8][15]

Yacc также был переписан для других языков, включая OCaml,[16] Ratfor, ML, Ада, Паскаль, Ява, Python, Рубин, Идти,[17], Common Lisp[18] и Erlang.[19]

Смотрите также

Рекомендации

  1. ^ «Азбука языков программирования: YACC». Computerworld. Получено 30 ноября 2012.
  2. ^ Левин, Джон (1992). Лекс и ЯКЦ. Севастополь, Калифорния: O'Reilly & Associates. п. хх. ISBN  1-56592-000-7.
  3. ^ Левин, Джон (2009). Flex & bison. Севастополь, Калифорния: O'Reilly Media. п. XV. ISBN  978-0-596-15597-1.
  4. ^ а б Ричи, Деннис М. (Апрель 1993 г.). Развитие языка C (PDF). Ассоциация вычислительной техники, Inc.
  5. ^ Моррис, Ричард (1 октября 2009 г.). "Стивен Кертис Джонсон: Компьютерщик недели". Программное обеспечение Red Gate. Получено 19 января 2018.
  6. ^ а б c d Джонсон, Стивен С. (1975). Yacc: еще один компилятор-компилятор (Технический отчет). Мюррей Хилл, Нью-Джерси: AT&T Bell Laboratories. 32. Получено 31 января 2020.
  7. ^ «Системы письма ранних переводчиков». Компьютерная лаборатория Атлас.
  8. ^ а б c Макилрой, М.Д. (1987). Читатель Research Unix: аннотированные выдержки из Руководства программиста, 1971–1986 (PDF) (Технический отчет). CSTR. Bell Labs. 139.
  9. ^ Страуструп, Бьярне. «История C ++: 1979–1991» (PDF).
  10. ^ Гамильтон, Наоми (2008-07-09). «Yacc, Unix и советы выпускников Bell Labs Стивена Джонсона». www.computerworld.com. В архиве из оригинала 2020-08-22. Получено 2020-11-10.
  11. ^ lex - Справочник по командам и утилитам, Единая спецификация UNIX, Выпуск 7 из Открытая группа, yacc - Справочник по командам и утилитам, Единая спецификация UNIX, Выпуск 7 из Открытая группа.
  12. ^ "plan9: выпуск Plan 9 Калифорнийского университета в Беркли под лицензией GPLv2". 26 декабря 2017 г.. Получено 2 января 2018.
  13. ^ Руководство Bison: История
  14. ^ "UNIX Special: проф. Керниган и Брейлсфорд". Компьютерил. 30 сентября 2015 года.
  15. ^ Керниган, Брайан В .; Пайк, Роб (1984). Среда программирования Unix. Прентис Холл. ISBN  0-13-937681-X.
  16. ^ "Руководство пользователя OCaml: Глава 12 Генераторы лексического анализатора и парсера (ocamllex, ocamlyacc)". Получено 25 ноя 2013.
  17. ^ "Yacc.go: версия Yacc для языка программирования Go". Получено 15 июля 2017.
  18. ^ "CL-Yacc: Common Lisp версия Yacc".
  19. ^ "yecc: реализация Yacc на Erlang".
  20. ^ Джон Левин (август 2009 г.), Flex & Bison, O'Reilly Media

внешняя ссылка