Введение

Генератор парсеров

Yacc (Yet Another Compiler Compiler) — компьютерная программа для операционной системы Unix, разработанная Стивеном К. Джонсоном. Это генератор LALR-парсерa (lookahead left-to-right rightmost derivation), создающий LALR-парсер (часть компилятора, которая пытается придать синтаксический смысл исходному коду) на основе формальной грамматики, записанной в нотации, аналогичной форме Бэкуса — Наура (BNF). Yacc поставляется в качестве стандартной утилиты в BSD и AT&T Unix. Дистрибутивы Linux на основе GNU включают Bison — замену Yacc, обратно совместимую с ней.

История

В начале 1970-х годов Стивен К. Джонсон, учёный в области компьютерных наук из Bell Labs / AT&T, разработал Yacc, потому что хотел добавить оператор исключающего ИЛИ в компилятор языка B (разработанный с использованием компилятора-генератора компиляторов TMG Макилроя). Yacc испытал влияние [TMG].

Yacc был первоначально написан на языке программирования B, но вскоре Алан Снайдер переписал его на языке C. Он вошёл в состав Unix версии 3, а полное описание Yacc было опубликовано в 1975 году. Джонсон использовал Yacc для создания переносимого компилятора C. Хотя Строструп счёл его непригодным для формальной спецификации языка, он всё же использовал Yacc для реализации Cfront, первой реализации C++. В интервью 2008 года Джонсон отметил, что "самое большое достижение Yacc, которым я горжусь, – это его вклад в распространение Unix и C".

Влияние

Yacc и подобные программы (в основном, повторные реализации) пользовались большой популярностью. Сам Yacc ранее был доступен как генератор парсеров по умолчанию в большинстве систем Unix, однако впоследствии его заменили более современные, в значительной степени совместимые программы, такие как Berkeley Yacc, GNU Bison, MKS Yacc и Abraxas PCYACC. Обновленная версия оригинального AT&T Yacc включена в проект OpenSolaris от Sun. Каждая из них предлагает незначительные улучшения и дополнительные возможности по сравнению с оригинальным Yacc, но концепция и базовый синтаксис остались неизменными. Yacc также был одним из нескольких инструментов UNIX, доступных для операционной системы UNOS компании Charles River Data Systems по лицензии Bell Laboratories. Среди языков, которые впервые были реализованы с использованием Yacc, – AWK, C++, eqn и Pic. Yacc также использовался в Unix для реализации портативного C-компилятора, а также парсеров для таких языков программирования, как FORTRAN 77, Ratfor, APL, bc, m4 и другие. Yacc также был переписан для других языков, включая OCaml, Ratfor, ML, Ada, Pascal, Java, Python, Ruby, Go, Common Lisp и Erlang. Berkeley Yacc: реализация Berkeley Yacc быстро стала популярнее, чем сама AT&T Yacc, благодаря своей производительности и отсутствию ограничений на повторное использование. LALR-парсер: базовый алгоритм парсинга, используемый в Yacc для генерации парсеров. Bison: версия Yacc от GNU. Lex (и Flex – лексический анализатор), токенный парсер, обычно используемый совместно с Yacc (и Bison). BNF – метасинтаксис, используемый для представления контекстно-свободных грамматик, то есть формальный способ описания контекстно-свободных языков. PLY (Python Lex Yacc) – альтернативная реализация Lex и Yacc на Python.