Якк

Якк
Оригинальный автор(ы)	Стивен С. Джонсон
Репозиторий	www .тьфух .org /cgi-bin /матка .pl?file=V6%2Fusr%2Fsource%2Fyacc ;
Написано в	С
Операционная система	Unix , Unix-подобные , Plan 9 , Inferno
Платформа	Кросс-платформенный
Тип	Команда
Лицензия	План 9: МОЯ лицензия

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

История

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

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

Джонсон использовал Yacc для создания C. портативного компилятора ^[8] Бьёрн Страуструп также пытался использовать Yacc для создания формальной спецификации C++ , но «потерпел поражение из-за синтаксиса C». ^[9] Считая его непригодным для формальной спецификации языка, Страуструп все же приступил к использованию Yacc для реализации Cfront , первой реализации C++. ^[10]

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

Описание

Входные данные для Yacc — это грамматика с фрагментами кода C (называемыми «действиями»), прикрепленными к ее правилам. Его выходные данные — это синтаксический анализатор на языке C, который выполняет фрагменты кода C, связанные с каждым правилом, как только правило распознается. Типичные действия включают в себя построение деревьев разбора . Используя пример Джонсона, если вызов node(label, left, right) создает узел двоичного дерева разбора с указанным метка и дети, затем правило

expr : expr '+' expr  { $$ = node('+', $1, $3); }

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

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

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

Влияние

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

Yacc также был одним из нескольких инструментов UNIX, доступных для операционной системы UNOS компании Charles River Data Systems по лицензии Bell Laboratories . ^[15]

Среди языков, которые были впервые реализованы с помощью Yacc, — AWK , C++ , ^[10] уравнение и рис . ^[16] Yacc также использовался в Unix для реализации портативного компилятора C , а также парсеров для таких языков программирования, как FORTRAN 77 , Ratfor , APL , bc , m4 и т. д. ^[8]^[17]

Yacc также был переписан для других языков, включая OCaml , ^[18] Ratfor , ML , Ada , Pascal , Java , PHP , Python , Ruby , Go , ^[19] Общий Лисп ^[20] и Эрланг . ^[21]

Berkeley Yacc : реализация Yacc в Беркли быстро стала более популярной, чем сама AT&T Yacc, благодаря своей производительности и отсутствию ограничений на повторное использование. ^[22]
Парсер LALR : основной алгоритм синтаксического анализа в парсерах, генерируемых Yacc.
Bison : GNU-версия Yacc.
Lex (и лексический анализатор Flex ), анализатор токенов, обычно используемый вместе с Yacc (и Bison).
BNF — это метасинтаксис, используемый для выражения контекстно-свободных грамматик : это формальный способ описания контекстно-свободных языков.
PLY (Python Lex-Yacc) — альтернативная реализация Lex и Yacc в Python.

См. также

Ссылки

^ «А-Я языков программирования: YACC» . Компьютерный мир. Архивировано из оригинала 31 января 2013 года . Проверено 30 ноября 2012 г.
^ Левин, Джон (1992). Лекс и Якк . Севастополь, Калифорния: O'Reilly & Associates. п. хх. ISBN 1-56592-000-7 .
^ Левин, Джон (2009). Флекс и бизон . Севастополь, Калифорния: O'Reilly Media. п. хв. ISBN 978-0-596-15597-1 .
^ Jump up to: ^а ^б Моррис, Ричард (1 октября 2009 г.). «Стивен Кертис Джонсон: Компьютерщик недели» . Программное обеспечение «Красные ворота» . Проверено 19 января 2018 г.
^ Jump up to: ^а ^б Ричи, Деннис М. (апрель 1993 г.). «Развитие языка Си». История языков программирования---II . Ассоциация вычислительной техники, Inc. (опубликовано 1 января 1996 г.). дои : 10.1145/234286.1057834 . ISBN 0-201-89502-1 . стр. 675, 684: После того, как версия B для TMG заработала, Томпсон переписал B сам по себе (шаг начальной загрузки).… Когда Джонсон вернулся в Bell Labs в 1973 году, он был сбит с толку, обнаружив, что язык, семена которого он привнес в Канада развилась дома; даже его собственная программа yacc была переписана на C Аланом Снайдером.
^ Jump up to: ^а ^б ^с ^д Джонсон, Стивен К. (1975). Yacc: Еще один компилятор-компилятор (Технический отчет). Мюррей Хилл, Нью-Джерси: AT&T Bell Laboratories. 32 . Проверено 31 января 2020 г.
^ «Ранние системы письма переводчиков» . Компьютерная лаборатория Атлас.
^ Jump up to: ^а ^б ^с Макилрой, доктор медицины (1987). Читатель Research Unix: аннотированные выдержки из Руководства программиста, 1971–1986 (PDF) (Технический отчет). CSTR. Лаборатории Белла. 139.
^ Страуструп, Бьерн . «История C++: 1979–1991» (PDF) .
^ Jump up to: ^а ^б Страуструп, Бьерн . «Исходный код Cfront» .
^ Гамильтон, Наоми (9 июля 2008 г.). «Yacc, Unix и советы выпускника Bell Labs Стивена Джонсона» . www.computerworld.com . Архивировано из оригинала 22 августа 2020 г. Проверено 10 ноября 2020 г.
^ lex – Справочник по оболочке и утилитам, Единая спецификация UNIX , версия 4 от Open Group , yacc – Справочник по оболочке и утилитам, Единая спецификация UNIX , версия 4 от Open Group .
^ «plan9: выпуск Plan 9 в Калифорнийском университете в Беркли под лицензией GPLv2» . Гитхаб . 26 декабря 2017 года . Проверено 2 января 2018 г.
^ Руководство для бизонов: История
^ Путеводитель по Вселенной для инсайдеров (PDF) . Charles River Data Systems, Inc., 1983. с. 13.
^ «Специальный выпуск UNIX: профессора Керниган и Брейлсфорд» . Компьютерфил . 30 сентября 2015 г. Архивировано из оригинала 11 декабря 2021 г.
^ Керниган, Брайан В.; Пайк, Роб (1984). Среда программирования Unix . Прентис Холл. ISBN 0-13-937681-Х .
^ «Руководство пользователя OCaml: Глава 12 Лексеры и генераторы синтаксических анализаторов (ocamllex, ocamlyacc)» . Проверено 25 ноября 2013 г.
^ «Yacc.go: версия Yacc для языка программирования Go» . Проверено 15 июля 2017 г.
^ «CL-Yacc: версия Yacc для Common Lisp» .
^ "yecc: реализация Yacc на Erlang" .
^ Джон Левин (август 2009 г.), flex & bison , O'Reilly Media

Внешние ссылки

Игровая площадка для изучения и тестирования синтаксиса

yacc – Справочник по оболочке и утилитам, Единая спецификация UNIX , версия 4 от Open Group.
yacc(1) – Plan 9 , том 1 Руководство программиста
yacc(1) – Inferno по общим командам Руководство
yacc(1) – Linux по основным командам Руководство

[1] «А-Я языков программирования: YACC» . Компьютерный мир. Архивировано из оригинала 31 января 2013 года . Проверено 30 ноября 2012 г.

[Levine_1992_p.xx-2] Левин, Джон (1992). Лекс и Якк . Севастополь, Калифорния: O'Reilly & Associates. п. хх. ISBN 1-56592-000-7 .

[Levine_2009_p.xv-3] Левин, Джон (2009). Флекс и бизон . Севастополь, Калифорния: O'Reilly Media. п. хв. ISBN 978-0-596-15597-1 .

[red-4] Jump up to: ^а ^б Моррис, Ричард (1 октября 2009 г.). «Стивен Кертис Джонсон: Компьютерщик недели» . Программное обеспечение «Красные ворота» . Проверено 19 января 2018 г.

[Chistory-5] Jump up to: ^а ^б Ричи, Деннис М. (апрель 1993 г.). «Развитие языка Си». История языков программирования---II . Ассоциация вычислительной техники, Inc. (опубликовано 1 января 1996 г.). дои : 10.1145/234286.1057834 . ISBN 0-201-89502-1 . стр. 675, 684: После того, как версия B для TMG заработала, Томпсон переписал B сам по себе (шаг начальной загрузки).… Когда Джонсон вернулся в Bell Labs в 1973 году, он был сбит с толку, обнаружив, что язык, семена которого он привнес в Канада развилась дома; даже его собственная программа yacc была переписана на C Аланом Снайдером.

[Yacc:_Yet_Another_Compiler-Compiler-6] Jump up to: ^а ^б ^с ^д Джонсон, Стивен К. (1975). Yacc: Еще один компилятор-компилятор (Технический отчет). Мюррей Хилл, Нью-Джерси: AT&T Bell Laboratories. 32 . Проверено 31 января 2020 г.

[7] «Ранние системы письма переводчиков» . Компьютерная лаборатория Атлас.

[reader-8] Jump up to: ^а ^б ^с Макилрой, доктор медицины (1987). Читатель Research Unix: аннотированные выдержки из Руководства программиста, 1971–1986 (PDF) (Технический отчет). CSTR. Лаборатории Белла. 139.

[hopl2-9] Страуструп, Бьерн . «История C++: 1979–1991» (PDF) .

[oldcfront-10] Jump up to: ^а ^б Страуструп, Бьерн . «Исходный код Cfront» .

[cw-11] Гамильтон, Наоми (9 июля 2008 г.). «Yacc, Unix и советы выпускника Bell Labs Стивена Джонсона» . www.computerworld.com . Архивировано из оригинала 22 августа 2020 г. Проверено 10 ноября 2020 г.

[12] lex – Справочник по оболочке и утилитам, Единая спецификация UNIX , версия 4 от Open Group , yacc – Справочник по оболочке и утилитам, Единая спецификация UNIX , версия 4 от Open Group .

[13] «plan9: выпуск Plan 9 в Калифорнийском университете в Беркли под лицензией GPLv2» . Гитхаб . 26 декабря 2017 года . Проверено 2 января 2018 г.

[14] Руководство для бизонов: История

[15] Путеводитель по Вселенной для инсайдеров (PDF) . Charles River Data Systems, Inc., 1983. с. 13.

[16] «Специальный выпуск UNIX: профессора Керниган и Брейлсфорд» . Компьютерфил . 30 сентября 2015 г. Архивировано из оригинала 11 декабря 2021 г.

[17] Керниган, Брайан В.; Пайк, Роб (1984). Среда программирования Unix . Прентис Холл. ISBN 0-13-937681-Х .

[18] «Руководство пользователя OCaml: Глава 12 Лексеры и генераторы синтаксических анализаторов (ocamllex, ocamlyacc)» . Проверено 25 ноября 2013 г.

[19] «Yacc.go: версия Yacc для языка программирования Go» . Проверено 15 июля 2017 г.

[20] «CL-Yacc: версия Yacc для Common Lisp» .

[21] "yecc: реализация Yacc на Erlang" .

[22] Джон Левин (август 2009 г.), flex & bison , O'Reilly Media

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

v т и Unix Программы интерфейса командной строки и встроенные оболочки оболочки
File system	cat chattr chmod chown chgrp cksum cmp cp dd du df file fuser ln ls mkdir mv pax pwd rm rmdir split tee touch type umask
Processes	at bg crontab fg kill nice ps time
User environment	env exit logname mesg talk tput uname who write
Text processing	awk basename comm csplit cut diff dirname ed ex fold head iconv join m4 more nl paste patch printf read sed sort strings tail tr troff uniq vi wc xargs
Shell builtins	alias cd echo test unset wait
Searching	find grep
Documentation	man
Software development	ar ctags lex make nm strip yacc
Miscellaneous	bc cal expr lp od sleep true and false
Categories Standard Unix programs Unix SUS2008 utilities List

v т и Plan 9 Программы интерфейса командной строки и встроенные оболочки оболочки
File system	chmod chgrp cmp cp dd du file gzip ls mkdir pwd rm split tee touch
Processes	kill ps
User environment	passwd who
Text processing	awk basename comm diff ed eqn join sed sort spell strings tail tr troff uniq wc
Shell builtins	echo test
Networking	ip/ipconfig ip/ping netstat
Searching	grep
Software development	ar hoc lex nm strip yacc
Miscellaneous	bc cal fortune sleep
Category