Yacc

редактировать
Yacc
Исходный автор (ы) Стивен С. Джонсон
Репозиторий Измените это в Викиданных
Операционная система Unix, Unix- например, Plan 9, Inferno
Platform Cross-Platform
Type Command

Yacc (Another Compiler -Compiler ) - это компьютерная программа для операционной системы Unix, разработанная Стивен С. Джонсон. Это генератор парсера Look Ahead слева направо (LALR), генерирующий парсер LALR (часть компилятора , которая пытается придать синтаксический смысл исходного кода ) на основе формальной грамматики, записанной в нотации, аналогичной форме Бэкуса – Наура (BNF). Yacc поставляется как стандартная утилита для BSD и ATT Unix. Дистрибутивы на основе GNU Linux включают Bison, замену Yacc с прямой совместимостью.

Содержание

  • 1 История
  • 2 Описание
  • 3 Воздействие
  • 4 См. Также
  • 5 Ссылки
  • 6 Внешние ссылки

История

В начале 1970-х годов Стивен К. Джонсон, специалист по информатике из Bell Labs / ATT, разработал Yacc, потому что хотел вставить оператор исключающий или в Компилятор языка B (разработанный с использованием компилятора-компилятора McIlroy TMG ), но это оказалось сложной задачей. В результате его коллега по Bell Labs Аль Ахо направил его к работе Дональда Кнута по синтаксическому анализу LR, которая послужила основой для Yacc. Yacc находился под влиянием и получил свое название от имени компилятора-компилятора TMG.

Первоначально Yacc был написан на языке программирования B, но вскоре был переписан на C. Он появился как часть версии 3 Unix, а полное описание Yacc было опубликовано в 1975 году.

Джонсон использовал Yacc для создания Portable C Compiler. Бьярн Страуструп, с другой стороны, попытался использовать Yacc для своей первоначальной работы над C ++, но «потерпел поражение из-за синтаксиса C» (например, имея как префиксные, так и постфиксные операторы объявления).

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

Описание

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

expr: expr '+' expr {$$ = узел ('+', $ 1, $ 3); }

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

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

Некоторые версии ATT Yacc стали с открытым исходным кодом. Например, исходный код доступен в стандартных дистрибутивах Plan 9.

Impact

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

Среди языков, которые были впервые реализованы с Yacc: AWK, экв и Рис. Yacc также использовался в Unix для реализации Portable C Compiler, а также парсеров для таких языков программирования, как FORTRAN 77, Ratfor, APL, bc, m4 и т. Д.

Yacc также был переписан для других языков, включая OCaml, Ratfor, ML, Ada, Pascal, Java, Python, Ruby, Go, Common Lisp и Erlang.

  • Berkeley Yacc : реализация Yacc в Беркли быстро стала более популярной чем сам ATT Yacc из-за его производительности и отсутствия ограничений на повторное использование.
  • Парсер LALR : лежащий в основе алгоритм синтаксического анализа в синтаксических анализаторах, созданных Yacc.
  • Bison : GNU-версия Yacc.
  • Lexлексический анализатор Flex ), синтаксический анализатор токенов, обычно используемый в сочетании с Yacc (и Bison).
  • BNF - это метасинтаксис, используемый для выражения контекстно-свободные грамматики : это формальный способ описания контекстно-свободных языков.
  • PLY (Python Lex-Yacc) - альтернативная реализация Lex и Yacc в Python.

См. также

Ссылки

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

Wikibook Руководство по Unix содержит страница по теме: Commands
Последняя правка сделана 2021-06-22 09:14:20
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте