Yacc
Encyclopedia
The computer program
yacc is a parser generator developed by Stephen C. Johnson
at AT&T
for the Unix
operating system. The name is an acronym for "Yet Another
Compiler Compiler." It generates a parser
(the part of a compiler
that tries to make syntactic sense of the source code
) based on an analytic grammar
written in a notation similar to BNF.
Yacc used to be available as the default parser generator on most Unix systems. It has since been supplanted as the default by more recent, largely compatible, programs such as Berkeley Yacc
, GNU bison
, MKS yacc and Abraxas pcyacc. An updated version of the original AT&T version is included as part of Sun's
OpenSolaris
project. Each offers slight improvements and additional features over the original yacc, but the concept has remained the same. Yacc has also been rewritten for other languages, including Ratfor
, ML
, Ada, Pascal
, Java
, Python
, Ruby
and Common Lisp
.
The parser generated by yacc requires a lexical analyzer. Lexical analyzer generators, such as Lex
or Flex
are widely available. The IEEE POSIX
P1003.2 standard defines the functionality and requirements for both Lex and Yacc.
Some versions of AT&T Yacc have become open source
. For example, source code
(for different implementations) is available with the standard distributions of Plan 9
and OpenSolaris
.
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
yacc is a parser generator developed by Stephen C. Johnson
Stephen C. Johnson
Stephen Curtis Johnson spent nearly 20 years at Bell Labs and AT&T where he wrote yacc, lint, spell and the Portable C Compiler machine .Johnson earned his PhD in mathematics but has spent his entire career in computer science...
at AT&T
AT&T
AT&T Inc. is an American multinational telecommunications corporation headquartered in Whitacre Tower, Dallas, Texas, United States. It is the largest provider of mobile telephony and fixed telephony in the United States, and is also a provider of broadband and subscription television services...
for the Unix
Unix
Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
operating system. The name is an acronym for "Yet Another
Yet another
Among programmers, yet another is an idiomatic qualifier in the name of a computer program, organisation, or event that is confessedly unoriginal.Stephen C...
Compiler Compiler." It generates a parser
Parsing
In computer science and linguistics, parsing, or, more formally, syntactic analysis, is the process of analyzing a text, made of a sequence of tokens , to determine its grammatical structure with respect to a given formal grammar...
(the part of a compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
that tries to make syntactic sense of the source code
Source code
In computer science, source code is text written using the format and syntax of the programming language that it is being written in. Such a language is specially designed to facilitate the work of computer programmers, who specify the actions to be performed by a computer mostly by writing source...
) based on an analytic grammar
Formal grammar
A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...
written in a notation similar to BNF.
Yacc used to be available as the default parser generator on most Unix systems. It has since been supplanted as the default by more recent, largely compatible, programs such as Berkeley Yacc
Berkeley Yacc
Berkeley Yacc is a reimplementation of the Unix parser generator Yacc, originally written by Robert Corbett in 1990, designed for compatibility with Yacc. Due to its liberal license and because it was faster than the AT&T Yacc, it quickly became the most popular version of Yacc...
, GNU bison
GNU bison
GNU bison, commonly known as Bison, is a parser generator that is part of the GNU Project. Bison reads a specification of a context-free language, warns about any parsing ambiguities, and generates a parser which reads sequences of tokens and decides whether the sequence conforms to the syntax...
, MKS yacc and Abraxas pcyacc. An updated version of the original AT&T version is included as part of Sun's
Sun Microsystems
Sun Microsystems, Inc. was a company that sold :computers, computer components, :computer software, and :information technology services. Sun was founded on February 24, 1982...
OpenSolaris
OpenSolaris
OpenSolaris was an open source computer operating system based on Solaris created by Sun Microsystems. It was also the name of the project initiated by Sun to build a developer and user community around the software...
project. Each offers slight improvements and additional features over the original yacc, but the concept has remained the same. Yacc has also been rewritten for other languages, including Ratfor
Ratfor
Ratfor is a programming language implemented as a preprocessor for Fortran 66. It provided modern control structures, unavailable in Fortran 66, to replace GOTOs and statement numbers.- Features :...
, ML
ML programming language
ML is a general-purpose functional programming language developed by Robin Milner and others in the early 1970s at the University of Edinburgh, whose syntax is inspired by ISWIM...
, Ada, Pascal
Pascal (programming language)
Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring.A derivative known as Object Pascal...
, Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
, Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
, Ruby
Ruby (programming language)
Ruby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was first developed and designed by Yukihiro "Matz" Matsumoto...
and Common Lisp
Common Lisp
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
.
The parser generated by yacc requires a lexical analyzer. Lexical analyzer generators, such as Lex
Lex programming tool
Lex is a computer program that generates lexical analyzers . Lex is commonly used with the yacc parser generator. Lex, originally written by Mike Lesk and Eric Schmidt, is the standard lexical analyzer generator on many Unix systems, and a tool exhibiting its behavior is specified as part of the...
or Flex
Flex lexical analyser
flex is a free software alternative to lex. It is frequently used with the free Bison parser generator. Unlike Bison, flex is not part of the GNU Project. Flex was written in C by Vern Paxson around 1987...
are widely available. The IEEE POSIX
POSIX
POSIX , an acronym for "Portable Operating System Interface", is a family of standards specified by the IEEE for maintaining compatibility between operating systems...
P1003.2 standard defines the functionality and requirements for both Lex and Yacc.
Some versions of AT&T Yacc have become open source
Open source
The term open source describes practices in production and development that promote access to the end product's source materials. Some consider open source a philosophy, others consider it a pragmatic methodology...
. For example, source code
Source code
In computer science, source code is text written using the format and syntax of the programming language that it is being written in. Such a language is specially designed to facilitate the work of computer programmers, who specify the actions to be performed by a computer mostly by writing source...
(for different implementations) is available with the standard distributions of Plan 9
Plan 9 from Bell Labs
Plan 9 from Bell Labs is a distributed operating system. It was developed primarily for research purposes as the successor to Unix by the Computing Sciences Research Center at Bell Labs between the mid-1980s and 2002...
and OpenSolaris
OpenSolaris
OpenSolaris was an open source computer operating system based on Solaris created by Sun Microsystems. It was also the name of the project initiated by Sun to build a developer and user community around the software...
.
See also
- LALR parserLALR parserIn computer science, an LALR parser is a type of LR parser based on a finite-state-automata concept. The data structure used by an LALR parser is a pushdown automaton...
: The underlying parsing algorithm in Yacc. - BisonGNU bisonGNU bison, commonly known as Bison, is a parser generator that is part of the GNU Project. Bison reads a specification of a context-free language, warns about any parsing ambiguities, and generates a parser which reads sequences of tokens and decides whether the sequence conforms to the syntax...
: The GNU version of Yacc. - LexLex programming toolLex is a computer program that generates lexical analyzers . Lex is commonly used with the yacc parser generator. Lex, originally written by Mike Lesk and Eric Schmidt, is the standard lexical analyzer generator on many Unix systems, and a tool exhibiting its behavior is specified as part of the...
(and Flex lexical analyserFlex lexical analyserflex is a free software alternative to lex. It is frequently used with the free Bison parser generator. Unlike Bison, flex is not part of the GNU Project. Flex was written in C by Vern Paxson around 1987...
), the token parser commonly used in conjunction with yacc (and Bison). - BNF, is a metasyntaxMetasyntaxA metasyntax describes the allowable structure and composition of phrases and sentences of a metalanguage, which is used to describe either a natural language or a computer programming language...
used to express context-free grammarContext-free grammarIn formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....
: that is, a formal way to describe formal languages.
External links
- Computerworld Interview with Stephen C. Johnson on YACC
- ML-Yacc a yacc version for the Standard ML language.
- CL-Yacc, a LALR(1)parser generator for Common LispCommon LispCommon Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
. - PLY a yacc version for PythonPython (programming language)Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
- Yacc theory
- ocamlyacc a yacc version for Objective CamlObjective CamlOCaml , originally known as Objective Caml, is the main implementation of the Caml programming language, created by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Didier Rémy and others in 1996...
. - Racc a yacc version for RubyRuby (programming language)Ruby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was first developed and designed by Yukihiro "Matz" Matsumoto...
. - Paper "Parsing Non-LR(k) Grammars with Yacc" by Gary H. Merrill
- ANSI C yacc grammar