Hubbry Logo
search
logo
Yacc avatar
Yacc
Yacc
current hub
Y

Yacc

logo
Community Hub0 Subscribers

Wikipedia

Yacc
View on Wikipedia
from Wikipedia
Yacc
Other namesBell Labs Yacc; AT&T Yacc
Original authorStephen C. Johnson
Repository
Written inC
Operating systemUnix, Unix-like, Plan 9, Inferno
PlatformCross-platform
TypeCommand
LicensePlan 9: MIT License

Yacc (Yet Another Compiler-Compiler) is a computer program for the Unix operating system developed by Stephen C. Johnson. It is a lookahead left-to-right rightmost derivation (LALR) parser generator, generating a LALR parser (the part of a compiler that tries to make syntactic sense of the source code) based on a formal grammar, written in a notation similar to Backus–Naur form (BNF).[1] Yacc is supplied as a standard utility on BSD and AT&T Unix.[2] GNU-based Linux distributions include Bison, a forward-compatible Yacc replacement.[3]

History

[edit]

In the early 1970s, Stephen C. Johnson, a computer scientist at Bell Labs / AT&T, developed Yacc because he wanted to insert an exclusive or operator into a B language compiler[4] (developed using McIlroy's TMG compiler-compiler[5]), but it turned out to be a hard task. As a result, he was directed by his colleague at Bell Labs Al Aho to Donald Knuth's work on LR parsing, which served as the basis for Yacc.[4] Yacc was influenced by[6] and received its name in reference to TMG compiler-compiler.[7]

Yacc was originally written in the B programming language, but was soon rewritten in C by Alan Snyder.[5] It appeared as part of Version 3 Unix,[8] and a full description of Yacc was published in 1975.[6]

Johnson used Yacc to create the Portable C Compiler.[8] Bjarne Stroustrup also attempted to use Yacc to create a formal specification of C++, but "was defeated by C's syntax".[9] While finding it unsuitable for a formal specification of the language, Stroustrup did proceed to use Yacc to implement Cfront, the first implementation of C++.[10]

In a 2008 interview, Johnson reflected that "the contribution Yacc made to the spread of Unix and C is what I'm proudest of".[11]

Description

[edit]

The input to Yacc is a grammar with snippets of C code (called "actions") attached to its rules. Its output is a shift-reduce parser in C that executes the C snippets associated with each rule as soon as the rule is recognized. Typical actions involve the construction of parse trees. Using an example from Johnson, if the call node(label, left, right) constructs a binary parse tree node with the specified label and children, then the rule 

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

recognizes summation expressions and constructs nodes for them. The special identifiers $$, $1 and $3 refer to items on the parser's stack.[6]

Yacc produces only a parser (phrase analyzer) which can be used alone in the case of scannerless parsing however, full syntactic analysis typically requires an external lexical analyzer to perform a tokenization stage first (word analysis), which is then followed by the parsing stage proper.[6] Lexical analyzer generators, such as Lex or Flex, are widely available for this purpose. The IEEE POSIX P1003.2 standard defines the functionality and requirements for both Lex and Yacc.[12]

Some versions of AT&T Yacc have become open source. For example, source code is available with the standard distributions of Plan 9.[13]

Impact

[edit]

Yacc and similar programs (largely reimplementations) have been very popular. Yacc itself used to be available as the default parser generator on most Unix systems, though it has since been supplanted 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 Yacc is included as part of Sun's OpenSolaris project. Each offers slight improvements and additional features over the original Yacc, but the concept and basic syntax have remained the same.[14]

Yacc was also one of several UNIX tools available for Charles River Data Systems' UNOS operating system under Bell Laboratories license.[15]

Among the languages that were first implemented with Yacc are AWK, C++,[10] eqn and Pic.[16][11] Yacc was also used on Unix to implement the Portable C Compiler, as well as parsers for such programming languages as FORTRAN 77, Ratfor, APL, bc, m4, etc.[8][17]

Yacc has also been rewritten for other languages, including OCaml,[18] Ratfor, ML, Ada, Pascal, Java, PHP, Python, Ruby, Go,[19] Common Lisp[20] and Erlang.[21]

  • Berkeley Yacc: The Berkeley implementation of Yacc quickly became more popular than AT&T Yacc itself because of its performance and lack of reuse restrictions.[22]
  • LALR parser: The underlying parsing algorithm in Yacc-generated parsers.
  • Bison: The GNU version of Yacc.
  • Lex (and Flex lexical analyser), a token parser commonly used in conjunction with Yacc (and Bison).
  • BNF is a metasyntax used to express context-free grammars: that is a formal way to describe context-free languages.
  • PLY (Python Lex-Yacc) is an alternative implementation of Lex and Yacc in Python.

See also

[edit]

References

[edit]
[edit]

Grokipedia

Yacc

View on Grokipedia
from Grokipedia
Yacc, short for Yet Another Compiler-Compiler, is a computer program that generates parsers for structured input languages, enabling the automatic recognition and processing of syntactic structures defined by context-free grammars.[1] Developed by Stephen C. Johnson at Bell Laboratories in the early 1970s, initially in the B programming language and later rewritten in C, Yacc takes as input a specification file containing grammar rules, semantic actions in C code, and declarations, from which it produces a C subroutine called yyparse() that implements an LALR(1) parser.[2][1] This parser works in tandem with a user-provided lexical analyzer, typically generated by Lex, to tokenize input and apply reduction rules, executing associated actions to build an abstract syntax tree or perform computations.[1] As a foundational tool in compiler construction and software development, Yacc became a standard utility in the Unix operating system following its inclusion in the Seventh Edition Unix Programmer's Manual in 1979, facilitating the creation of compilers for languages like C and Pascal, as well as domain-specific tools such as desk calculators and data format processors.[3] Its design emphasizes portability and efficiency, supporting disambiguating rules to resolve parsing conflicts in ambiguous grammars, and it has influenced subsequent parser generators like Bison, which extends Yacc for broader compatibility.[1][2] By automating the tedious process of hand-coding parsers, Yacc significantly accelerated the development of language processors during the formative years of Unix and C at Bell Labs.[4]

Introduction

Definition and Purpose

Yacc, short for Yet Another Compiler-Compiler, is a computer program designed to generate parsers from formal grammars, particularly those specified as LALR(1) context-free grammars.[5] It serves as a tool for automating the creation of syntactic analyzers, transforming user-defined grammar rules into executable code that can process structured input.[5] Initially developed in the B programming language and later rewritten in portable C at Bell Laboratories, Yacc produces parser subroutines capable of recognizing valid input patterns based on the provided specifications.[5][2] The primary purpose of Yacc is to simplify the development of parsers for compilers, interpreters, and other language-processing applications by converting high-level descriptions of grammar structures into efficient, low-level C code for parsing input streams.[5] This process involves specifying production rules and associated actions, which Yacc compiles into a shift-reduce parser that systematically analyzes input from left to right.[5] By handling the complexities of parsing logic automatically, Yacc enables developers to focus on defining the language syntax rather than implementing intricate state machines manually.[5] Key benefits of Yacc include a significant reduction in the manual coding required for parsing algorithms, support for semantic actions that execute code during the parsing process, and the ability to detect input errors as early as possible through lookahead mechanisms.[5] These features make it particularly valuable for constructing efficient analyzers for programming languages and data formats.[5] Yacc was created to address the challenges of compiler construction, with its technical report first published in July 1975.[3]

Basic Concepts

A context-free grammar (CFG) is a formal grammar consisting of a 4-tuple (V,T,P,S)(V, T, P, S), where VV is a finite set of variables (nonterminals), TT is a finite set of terminals, PP is a finite set of productions of the form A→αA \to \alpha with A∈VA \in V and α∈(V∪T)∗\alpha \in (V \cup T)^*, and S∈VS \in V is the start symbol.[6] These productions allow nonterminals to derive strings composed of terminals and other nonterminals, enabling the description of hierarchical syntactic structures in programming languages, such as arithmetic expressions where an expression nonterminal EE can derive E+TE + T or simply TT.[6] CFGs generate context-free languages through repeated application of productions, starting from the start symbol to produce terminal strings, and are foundational for syntax specification because they capture recursive and nested constructs without contextual dependencies.[6] In parsing, bottom-up parsers construct the parse tree from the leaves (terminals) to the root (start symbol), effectively reversing a rightmost derivation by scanning the input left to right.[6] The shift-reduce mechanism implements this using a stack: the shift operation pushes the next input symbol onto the stack, while the reduce operation identifies a handle—a right-hand side of a production at the top of the stack—and replaces it with the corresponding nonterminal, ensuring the stack always holds a viable prefix of some right-sentential form.[6] Handles appear only at the stack's top in valid parses, preventing erroneous reductions and maintaining progress toward the start symbol.[6] To handle ambiguities, LALR(1) parsers, a practical variant of LR parsers, incorporate one-token lookahead to resolve parsing decisions.[6] The lookahead examines the next input symbol to distinguish between possible actions, such as shifting or reducing, particularly in shift-reduce conflicts where multiple reductions or a shift might apply.[6] This mechanism merges states with identical cores from LR(1) item sets, reducing table size while preserving parsing power for most practical grammars, and resolves ambiguities by enforcing operator precedence and associativity through grammar design or table entries.[6] The compiler front-end comprises key components like the lexer and parser to process source code into a structured form.[6] The lexer, or lexical analyzer, performs tokenization by grouping input characters into meaningful tokens—such as identifiers, keywords, or operators—using regular expressions, effectively filtering out whitespace and comments to produce a sequence of tokens for further analysis.[6] The parser then consumes these tokens to verify syntactic correctness according to the CFG and constructs a parse tree or abstract syntax tree, identifying the hierarchical structure of the program.[6] Semantic actions extend parsing by embedding executable code fragments within grammar productions, triggered during reductions to perform computations beyond syntax checking.[6] These actions, part of syntax-directed translation, compute attributes like types or addresses at reduction points—for instance, generating intermediate code when an expression is reduced—and enable tasks such as symbol table updates or error reporting without altering the parse tree construction.[6] Yacc automates the integration of these concepts by generating parsers that execute such actions efficiently.[6]

History

Origins at Bell Labs

Yacc, short for "Yet Another Compiler-Compiler," was developed by Stephen C. Johnson at Bell Laboratories in the early 1970s (invented in 1971 and reaching a recognizable form by 1973) as a key component of the Portable C Compiler (PCC) project.[7] Johnson, a computer scientist focused on compiler technology, created Yacc to facilitate the construction of parsers for the emerging C programming language, which was being formalized during this period at Bell Labs.[8] This tool was initially documented in Johnson's Computing Science Technical Report No. 32, marking its formal introduction within the Unix research environment.[9] The primary motivation for Yacc stemmed from the increasing complexity of programming language syntaxes, particularly for C, which demanded robust and automated methods for handling input structures in compilers.[1] Manual parser implementation had become error-prone and time-consuming amid the need to support features like operator precedence and associativity, prompting Johnson to design a generator that could produce efficient parsing code from high-level grammar specifications.[1] By automating the translation of context-free grammars into executable C code, Yacc addressed these challenges, enabling developers to focus on semantic actions rather than low-level parsing logic.[4] Yacc first appeared in Version 3 Unix in 1973 and was included as a standard utility in Version 7 Unix, released in 1979, alongside the lexical analyzer generator Lex, developed by Mike Lesk and Eric Schmidt.[10][11] This inclusion in the official Unix distribution, as detailed in the Seventh Edition UNIX Programmer's Manual, facilitated its widespread adoption within the Unix ecosystem and beyond.[9] Early development of Yacc encountered challenges in managing ambiguous grammars, such as the classic if-then-else dangling else problem, which could lead to shift/reduce conflicts in the generated parser.[1] To balance power and efficiency, Johnson opted for LALR(1) parsing, a subset of full LR(1) that reduced table sizes and computation overhead while still handling most practical grammars effectively.[1] This design choice prioritized usability on the resource-constrained hardware of the era, though it required users to resolve ambiguities through precedence declarations or restructuring.[1]

Key Developments and Variants

In the 1980s, significant enhancements to Yacc emerged from academic and open-source efforts, notably Berkeley Yacc (byacc), originated in 1985 by Robert Corbett at the University of California, Berkeley.[12] This variant improved upon the original AT&T Yacc by offering better error handling mechanisms, such as more informative diagnostics during parsing conflicts, and introduced the %expect directive to specify the anticipated number of shift-reduce conflicts, allowing developers to suppress warnings for known ambiguities in grammars.[13] These additions made it more user-friendly for complex language specifications while maintaining compatibility with standard Yacc input formats.[12] Standardization efforts in the late 1980s and early 1990s aimed to ensure portability across Unix-like systems. Yacc was incorporated into the POSIX.2 standard (IEEE Std 1003.2-1992), which defined a consistent interface for parser generation utilities, including requirements for input grammar specifications, output C code conformance to ISO C, and options like -d for symbol table generation and -v for verbose reports.[14] This inclusion, building on earlier drafts from the POSIX working group, facilitated widespread adoption in compliant environments by standardizing behavior and reducing vendor-specific variations.[14] The transition to open-source availability accelerated in the early 2000s. In 2002, Caldera International released the source code for historical Unix versions, including the original AT&T Yacc from V7 and 32V editions, under more permissive terms as part of efforts to open legacy Unix materials.[7] This release enabled broader examination, modification, and integration into modern projects, fostering further adaptations while preserving the tool's core algorithms. By the 2000s, proprietary use of the original Bell Labs-derived Yacc declined due to licensing restrictions imposed by AT&T, which required paid agreements for commercial deployment.[7] Developers increasingly shifted to free alternatives like GNU Bison and Berkeley Yacc, which offered equivalent functionality under open licenses such as the BSD License, avoiding the costs and legal complexities of AT&T's terms.[13] This move aligned with the growing open-source ecosystem, ensuring Yacc's principles endured without proprietary barriers.

Technical Overview

Grammar Specification

Yacc input files, conventionally named with a .y extension, consist of three primary sections: a declarations section, a rules section, and a user code section.[15] The declarations section begins with C code enclosed between %{ and %} delimiters, allowing inclusion of headers and variable definitions, followed by Yacc-specific directives such as %token for declaring terminal symbols, %type for specifying nonterminal types, %start to define the grammar's start symbol, and precedence directives like %left, %right, and %nonassoc.[16] The rules section contains the context-free grammar productions, each formatted as a nonterminal followed by a colon, one or more alternatives separated by vertical bars, and optional C actions enclosed in braces.[17] The user code section, placed at the end, includes additional C functions and subroutines that support the generated parser.[15] Terminal symbols represent the basic lexical units of the input and are declared using %token, which assigns numeric values to identifiers, often in uppercase by convention to distinguish them from nonterminals.[16] Nonterminal symbols, which derive further productions, are implicitly any identifiers not declared as tokens and are typically named in lowercase; their value types can be specified with %type to associate them with C data structures via a %union declaration.[15] Precedence and associativity for terminals, particularly operators, are defined in declaration groups using %left for left-associative, %right for right-associative, and %nonassoc for non-associative operations, with later declarations indicating higher precedence levels to guide ambiguity resolution.[18] These directives ensure that tokens declared in precedence statements need not repeat %token declarations, though they may for clarity.[1] In generating LALR(1) parsers, Yacc may encounter shift-reduce conflicts, where the parser must choose between shifting the next token onto the stack or reducing a completed production, and reduce-reduce conflicts, where multiple productions are viable for reduction; by default, shift-reduce conflicts favor shifting, while reduce-reduce conflicts prefer the earlier-listed rule.[19] Precedence rules resolve many shift-reduce conflicts by comparing the precedence of the lookahead token against the production being reduced, selecting the higher-precedence action or the shift for equal precedence based on associativity.[20] The %expect directive allows users to specify an anticipated number of shift-reduce conflicts, suppressing warnings if the count matches exactly, which is useful for grammars with intentional ambiguities like those in expression parsing.[15] Error handling in Yacc grammars employs a reserved nonterminal token named error, which can be incorporated into productions to specify recovery points, enabling the parser to discard input tokens until a valid follow token appears after an error detection.[21] Upon encountering a syntax error, the parser invokes the yyerror function, enters an error state by skipping input for up to three tokens, and attempts to resume parsing via error productions; the yyerrok macro, placed within an action, clears the error flag to allow immediate resumption of normal parsing without further skips.[22] This mechanism supports robust error recovery while maintaining the grammar's structure.[15]

Parser Generation Process

The parser generation process in Yacc involves constructing an LALR(1) parsing table from the input grammar specification, which enables the produced parser to recognize valid input strings efficiently. This process begins by augmenting the grammar with a new start rule and computing a set of valid LR(1) items, but Yacc optimizes by using LR(0) item sets as cores and propagating lookaheads to form LALR(1) states. The core algorithm, as described by Johnson, relies on building a deterministic finite automaton (DFA) that models the parser's decisions for shifting, reducing, or accepting input tokens.[1] LALR(1) parsing table construction starts with the creation of item sets, where each item represents a production rule with a dot indicating the position of the parse (e.g., A → α • β). The initial state consists of the augmented start production with the dot at the beginning. The closure operation expands an item set by adding all productions for nonterminals immediately following the dot in existing items, ensuring all possible next steps are considered. For instance, if an item A → α • B β is in the set, the closure includes B → • γ for all productions of B. The goto function then computes transitions: for a symbol X (terminal or nonterminal), the goto set is the closure of items where the dot has advanced over X from the current set. These steps build the canonical collection of LR(0) item sets, forming the states of the automaton. Lookahead propagation refines this for LALR(1) by merging states with identical cores and computing precise lookahead sets using relations like direct reads (DR), reads, and includes, ensuring reduces only occur when the lookahead matches expected terminals. This propagation avoids unnecessary conflicts by unioning follow sets across merged states, as formalized in the efficient algorithm that operates in linear time relative to the DFA size.[1][23] The state machine creation generates a finite automaton where each state corresponds to an item set, and transitions define shift actions for terminals (pushing the next state onto the stack) and goto actions for nonterminals after reductions (also pushing the computed state). Reduce actions pop the stack by the length of the production's right-hand side and apply the corresponding semantic action, while the lookahead symbol determines if a reduce is valid. Conflicts, such as shift-reduce or reduce-reduce, are detected during table filling and reported if the grammar is ambiguous for LALR(1). The automaton processes input left-to-right, using one token of lookahead to decide actions, enabling bottom-up parsing of deterministic context-free grammars.[1][23] The generated C code includes compact tables to encode the automaton's behavior. The yytable array stores action values (positive for shifts/gotos indicating next states, negative for reduces indicating rule numbers) and error codes, indexed by state and symbol. The yycheck array validates yytable entries, containing the symbol index only for valid combinations to prevent spurious actions and reduce table size. Additional tables like yydefred handle default reduces in states with no conflicts, and yypact or yysindex/yyrindex support sparse table lookups for efficiency. During parsing, the driver routine indexes these tables with the current state and lookahead to fetch actions.[1] Optimization techniques in Yacc's generation process include state merging for LALR(1), which combines LR(1) states sharing the same LR(0) core, significantly reducing the number of states compared to full LR(1) (e.g., from hundreds to dozens for typical grammars) while retaining most lookahead precision over simpler SLR(1) methods that use only follow sets. This merging propagates lookaheads via the includes relation to avoid introducing reduce-reduce conflicts, though it may create shift-reduce conflicts not present in LR(1). Default actions further compact tables by specifying a single reduce (or error) for states where all undefined symbols share the same outcome, omitting explicit entries and using yydefred for quick resolution. These techniques ensure the parser is both space-efficient and fast, suitable for embedded use in compilers.[1][23]

Output and Code Integration

When Yacc processes a grammar specification file, it generates a C source file named y.tab.c containing the parser implementation, including the primary entry point function yyparse(). This function is integer-valued and returns 0 on successful parsing or a non-zero value indicating an error.[15] If the -d option is specified during invocation, Yacc also produces a header file y.tab.h that declares tokens and types for use in the lexical analyzer and other parts of the program.[15] To integrate the generated parser into a larger C program, the application must provide a main() function that invokes yyparse(), along with implementations of the yylex() lexical analyzer function—which supplies tokens to the parser—and the yyerror() error-handling routine. The yyparse() function calls yylex() repeatedly to obtain tokens until the input is fully processed or an error occurs, at which point yyerror() is invoked to report issues such as syntax errors. A minimal complete program might define main() to simply call yyparse() after setting up input sources for yylex(), ensuring all components are linked together during compilation of y.tab.c.[15][24] For handling semantic values during parsing, Yacc employs a value stack parallel to its state stack, where values associated with grammar symbols are stored and manipulated. These values are of type YYSTYPE, which the user defines in the grammar file using the %union directive to specify a C union encompassing possible data types such as integers, pointers, or strings for terminals and non-terminals. During reduction actions, semantic values from child symbols are accessed via constructs like $1, $2, etc., and assigned to the value of the reduced non-terminal (e.g., $$), enabling the propagation of attributes like expression results or symbol table entries up the parse tree.[15][16] Yacc provides debugging support through the -v command-line option, which generates a file named y.output containing a detailed description of the parser's finite state machine, including state transitions, actions, and any detected shift/reduce or reduce/reduce conflicts. This file aids in diagnosing ambiguities or errors in the grammar by listing the lookahead tokens that trigger conflicts in specific states, allowing developers to refine rules for deterministic parsing.[17][25]

Usage and Examples

Writing Yacc Input Files

Yacc input files are structured into three primary sections to facilitate the specification of a context-free grammar and associated code: a prologue containing declarations and initial C code, the grammar rules section, and an epilogue for additional programs. The prologue begins with optional C code enclosed in %{ ... %} delimiters, followed by declarations using directives such as %token to define terminal symbols, %type for non-terminal value types, %union for variant types, and %start to specify the initial non-terminal. These declarations prepare the environment for parsing by defining symbols and their attributes, ensuring compatibility with the generated C code. The grammar rules section then follows, marked by a single %% if the prologue contains C code, where productions are written in the form non_terminal : body ;, with multiple alternatives separated by |. The epilogue, also delimited by %% if present, includes user-supplied C functions such as the lexical analyzer yylex() and main program, which integrate with the parser. This organization allows for modular development, where declarations handle setup, rules define syntax, and the epilogue manages execution and input handling.[26][1] To resolve ambiguities in grammars, particularly for expressions with operators, Yacc employs precedence and associativity directives in the declarations section: %left for left-associative operators like addition and subtraction, %right for right-associative ones like exponentiation, and %nonassoc for non-associative relations like equality comparisons. These directives are listed in order of increasing precedence, with earlier lines having lower precedence; for instance, %left '+' '-' followed by %left '*' '/' ensures multiplication binds tighter than addition. Associativity determines shift/reduce conflict resolution: left-associativity favors reduction first to group operators to the left, mimicking standard arithmetic conventions. Rules can override these with %prec token to assign a specific precedence, such as treating unary minus as higher than multiplication. This mechanism systematically disambiguates grammars without altering the underlying LALR(1) parsing, promoting clarity in operator-heavy languages.[26][1] For efficient bottom-up parsing, Yacc grammars should prefer left-recursive rules, especially in sequences or lists, as the LALR(1) algorithm processes input from left to right and reduces as soon as possible. A left-recursive form like list : item | list ',' item ; allows the parser to handle left-to-right evaluation without excessive stack growth, avoiding the left-to-right descent issues that plague right-recursive alternatives in recursive-descent parsers. This structure aligns with the shift-reduce mechanism, enabling compact state tables and faster recognition of left-associated constructs. Developers are advised to refactor right-recursive rules to left-recursive equivalents where feasible, as the generated parser's performance benefits from this orientation without increasing grammar complexity.[1] Common pitfalls in writing Yacc input files include shift/reduce or reduce/reduce conflicts arising from ambiguous grammars, which can manifest as infinite loops if error recovery is mishandled, particularly in left-recursive rules without proper termination. Left recursion itself is safe in Yacc but requires careful bounding, such as ensuring lists end with a non-recursive base case, to prevent stack overflows during parsing of deeply nested inputs. Nullable non-terminals, defined by empty bodies like optional : | elements ;, introduce epsilon productions that may lead to conflicts if the parser cannot determine when to apply them; these should be used sparingly and verified through Yacc's conflict reporting to avoid spurious reductions. Best practices recommend running Yacc with verbose output (-v flag) to inspect generated states and iteratively refining rules, grouping productions by left-hand side, and using uppercase for terminals and lowercase for non-terminals to enhance readability.[26][1]

Simple Parser Example

To illustrate the practical use of Yacc in constructing a parser, consider a minimal example that evaluates simple arithmetic expressions involving addition and subtraction of integers, such as "3 + 4 - 2". This example draws from the foundational desk calculator specification in the original Yacc documentation, adapted to focus on basic binary operators without variables or multi-digit accumulation for brevity.[1] The Yacc input file, named simple.y, defines a context-free grammar for expressions and includes semantic actions in C to compute values during parsing. The grammar uses a start symbol list to handle multiple statements, with expr as the core non-terminal for arithmetic. Precedence is specified to treat addition and subtraction as left-associative and equal in priority. 
%{
#include <stdio.h>
int yylex(void);
void yyerror(char *);
%}

%token NUMBER

%left '+' '-'

%%

list: /* empty */
    | list stat '\n'
    | list [error](/page/Error) '\n'   { yyerrok; }
    ;

stat: expr             { [printf](/page/Printf)("Result: %d\n", $1); }
    ;

expr: expr '+' expr    { $$ = $1 + $3; }
    | expr '-' expr    { $$ = $1 - $3; }
    | NUMBER           { $$ = $1; }
    | '(' expr ')'     { $$ = $2; }
    ;

%%

int main(void) {
    return yyparse();
}

void yyerror(char *s) {
    fprintf(stderr, "%s\n", s);
}
A corresponding Lex input file, simple.l, tokenizes the input by recognizing integers as NUMBER tokens and operators as single characters. It sets yylval to the integer value for numbers and ignores whitespace. 
%{
#include "y.tab.h"
%}

%%

[0-9]+     { yylval = atoi(yytext); return NUMBER; }
[ \t]      ; /* ignore whitespace */
\n         return '\n';
.          return yytext[0];
%%
To build and run the parser, process the files with Yacc and Lex, then compile the generated C code. The commands are: yacc -d simple.y, lex simple.l, and cc y.tab.c lex.yy.c -o simple_parser -ll. Execute with ./simple_parser, providing input like 3 + 4 - 2\n interactively; the output will be Result: 5. This setup links against the Lex library (-ll) for the lexical analyzer.[1] During parsing, Yacc employs a shift-reduce algorithm to build and evaluate the expression. Tokens are shifted onto the parse stack (e.g., NUMBER for 3, '+', NUMBER for 4). When a complete right-hand side matches a rule, a reduction occurs: for expr : expr '+' expr, the action { $$ = $1 + $3; } computes the sum (e.g., 3 + 4 = 7) and replaces the matched symbols with the result value on the stack. Subsequent reductions, such as subtracting 2 from 7, propagate the final value to the stat rule, triggering the print action. Parentheses ensure grouping by treating them as transparent in the grammar, allowing nested reductions without altering precedence. This on-the-fly evaluation constructs a simple computation tree implicitly through the stack, avoiding an explicit abstract syntax tree.[1]

Implementations and Extensions

GNU Bison

GNU Bison is the primary modern implementation of Yacc developed as part of the GNU Project. It was originally written by Robert Corbett in 1985, with Richard Stallman contributing to make it compatible with Yacc syntax. Since its inception, Bison has been maintained by the free software community through volunteer efforts, with current maintainers including Akim Demaille and Paul Eggert, and development hosted on the GNU Savannah platform.[27] Bison introduces several enhancements over the original Yacc, including support for generating parsers in multiple languages such as C, C++, and Java via the %language directive, which specifies the target programming language for the output code.[28] It also features push parsing mode, enabled by %define api.push-pull push, allowing the parser to process tokens incrementally in an event-driven manner, which is particularly useful for integrating with graphical user interfaces or real-time applications. Additionally, location tracking is supported through the %locations directive, which enables the parser to record file positions (line and column) for tokens and rules, facilitating error reporting and debugging. Bison maintains full backward compatibility with Yacc input syntax, ensuring that existing Yacc grammars can be processed without modification.[27] It extends this compatibility with directives like %define api.pure, which generates a reentrant (pure) parser suitable for multithreaded environments by avoiding global variables.[29] Bison is distributed under the GNU General Public License version 3 or later, with a special exception permitting the use and distribution of generated parser code under any license, even proprietary ones.[30] As a core component of the GNU toolchain, it is included in most Linux distributions and other Unix-like systems, making it widely accessible for free software development.[27]

Other Variants

Berkeley Yacc (byacc), developed around 1990 by Robert Corbett, serves as a compatible alternative to the original AT&T Yacc, generating LALR(1) parsers with enhanced diagnostics for better error reporting during grammar specification.[13] It was distributed under a BSD license and integrated into BSD Unix distributions, including FreeBSD, where community contributions, such as those from Xin LI in 2009, have sustained its maintenance as an open-source tool.[13] This variant prioritizes portability across Unix-like systems while maintaining close adherence to Yacc's syntax, making it suitable for environments requiring lightweight, non-GNU parser generation without reentrancy extensions.[13] For non-Unix environments, commercial ports like those in the PTC MKS Toolkit provide Yacc implementations adapted for Windows, enabling Unix application porting by supporting AT&T-style grammar processing in a native Windows development workflow.[31] These tools, including add-ins for Microsoft Visual Studio, facilitate parser integration into Windows-based compilers and utilities, emphasizing compatibility for legacy Unix code migration rather than new feature additions.[32] Such ports address niche portability needs in enterprise settings where full Unix emulation is impractical. Embedded and minimalist systems benefit from lightweight Yacc variants, such as the Plan 9 implementation, which generates LR(1) parser tables optimized for resource-constrained environments like distributed operating systems.[33] Similarly, Miniyacc offers a single-file, subset-compliant version of POSIX Yacc that compiles grammars into compact C code, ideal for small devices by reducing overhead through simplified table generation and excluding advanced features like ambiguous grammar handling.[34] Language-specific adaptations include Ayacc, an Ada-based LALR(1) parser generator originally developed in the 1990s at the University of California, Irvine, by David Taback and Deepak Tolani, which produces type-safe Ada code for actions, ensuring runtime checks and integration with Ada's strong typing for safety-critical applications.[35] For Pascal, TP Yacc (part of the TP Lex and Yacc toolkit) extends Yacc semantics to Turbo Pascal, generating parsers with Pascal actions that leverage the language's structured types for reliable semantic processing in educational and legacy compiler tools.[36] These forks target domain-specific portability, allowing developers to embed parser logic directly in type-safe host languages without C intermediaries.

Impact and Legacy

Influence on Compiler Tools

Yacc played a pivotal role in popularizing LALR(1) parsing, a bottom-up shift-reduce technique that efficiently handles a broad class of context-free grammars with deterministic parsing tables. By generating LALR(1) parsers from grammar specifications augmented with disambiguating rules, Yacc standardized the construction of efficient syntactic analyzers for compilers and language processors, influencing the design of subsequent tools that adopted similar bottom-up strategies. This approach became foundational in early compiler toolchains, including precursors to modern parser generators, where LALR(1)'s balance of power and practicality set a benchmark for parsing complex languages without excessive computational overhead.[1] The pairing of Yacc with Lex, a lexical analyzer generator, established a workflow that became the de facto standard for front-end development in compiler construction during the 1980s and 1990s. This lex-yacc pipeline automated the separation of lexical analysis (tokenization via regular expressions) from syntactic analysis (grammar-based parsing), enabling developers to rapidly prototype and refine language front-ends with modular, generated code in C. Widely adopted in Unix-based environments and beyond, this combination streamlined the implementation of parsers for languages like C and Pascal, influencing tool design practices that emphasized automation and separation of concerns in compiler engineering.[37] In education, Yacc has profoundly shaped the teaching of formal languages and compiler design, serving as a core tool in university courses and textbooks for decades. Its use in assignments involving parser generation has introduced generations of students to concepts like grammar specification, parsing conflicts, and code integration, fostering a deep understanding of syntactic analysis. Surveys of top compiler construction courses confirm Yacc's enduring prevalence, with it remaining the most frequently employed parser generator despite newer alternatives, thereby influencing countless compiler writers who apply its principles in professional development. Yacc's reliance on LALR(1) parsing, while powerful, exposed limitations in handling ambiguous or complex grammars prone to shift-reduce or reduce-reduce conflicts, often requiring manual resolution through precedence rules or grammar restructuring. These challenges inspired the development and adoption of top-down alternatives, such as recursive descent parsers, which offer greater flexibility for left-recursive grammars and easier integration of semantic actions without table-driven conflicts. By highlighting the trade-offs of bottom-up methods, Yacc indirectly advanced hybrid and top-down tools, like those in ANTLR, that prioritize grammar expressiveness and error handling in modern language processing.

Adoption in Modern Software

Despite a shift toward alternative parsing approaches in many contemporary programming languages, Yacc and its extensions like GNU Bison continue to see persistent adoption in performance-critical and legacy systems, particularly those written in C and C++. For instance, the Bash shell employs a Bison-generated parser to handle command input parsing, as defined in its core grammar file parse.y.[38] Similarly, MySQL relies on Bison for SQL statement parsing, with ongoing development tasks integrating Bison features like location tracking for query elements.[39] In the Linux kernel, Bison is essential for generating parsers during the build process, including for Kconfig configuration handling, making it a build dependency since kernel version 4.16. Yacc and Bison integrate seamlessly with modern build systems, facilitating their use in large-scale software projects. GNU Make provides built-in implicit rules for processing Yacc files (.y), automatically invoking Bison to generate C code and compiling it into object files. CMake offers dedicated support through the FindBison module, which locates the Bison executable and provides the BISON_TARGET macro to define custom build rules for grammar files, enabling out-of-source builds and dependency management in cross-platform environments.[40] While Yacc's dominance has declined in favor of more flexible alternatives, it remains relevant for specific domains. A survey of major programming language implementations reveals a trend toward hand-written recursive descent parsers in languages like Rust and Go for better error recovery and maintainability, and parser combinators—such as Parsec in Haskell or Nom in Rust—for declarative parsing in functional paradigms.[41] However, Yacc and Bison persist in performance-sensitive C/C++ codebases where generated LALR parsers offer efficient, deterministic performance without runtime overhead from backtracking. As of 2025, GNU Bison's version 3.8 series includes enhancements for legacy maintenance, such as the %define parse.error detailed directive for customizable syntax error messages with support for non-ASCII token aliases, and improved internationalization via integration with GNU gettext.[42] These updates aid in adapting older Yacc grammars to modern requirements like better diagnostics in diverse encoding environments.

References

  1. Yacc Yet Another Compiler Compiler by Stephen C. Johnson
  2. The Development of the C Language - Nokia
  3. yacc(1) - OpenBSD manual pages
  4. Stephen Curtis Johnson: Geek of the Week - Simple Talk
  5. [PDF] Yacc: Yet Another Compiler-Compiler - ePaperPress
  6. [PDF] lJNIX PROGRAMMER'S MANUAL - Bitsavers.org
  7. [PDF] Dragon-book.pdf - School of Information Science and Technology
  8. Yacc (Bison 3.8.1) - GNU
  9. [PDF] The Development of the C Language - Nokia
  10. [PDF] v7vol2b.pdf - Amazon S3
  11. Byacc (Bison 3.8.1) - GNU.org
  12. BYACC – Berkeley Yacc – generate LALR(1) parsers
  13. yacc
  14. yacc
  15. yacc grammar file declarations - IBM
  16. Chapter 3 yacc -- A Compiler Compiler
  17. Precedence
  18. Ambiguity and Conflicts
  19. Rules to help remove ambiguities - IBM
  20. yacc program error handling - IBM
  21. Error Handling
  22. Efficient Computation of LALR(1) Look-Ahead Sets
  23. The yacc Environment
  24. Use the yacc compiler - IBM
  25. yacc(1p) - Linux manual page - man7.org
  26. Bison - GNU Project - Free Software Foundation
  27. Decl Summary (Bison 3.8.1) - GNU.org
  28. %define Summary (Bison 3.8.1) - GNU.org
  29. Conditions for Using Bison - GNU.org
  30. PTC MKS Toolkit Customer Support
  31. PTC MKS Toolkit Customer Support
  32. yacc(1) - Plan 9 from User Space
  33. Miniyacc - A Lightweight Yacc for C - c9x.me
  34. Ada-France/ayacc: Ayacc - An Ada LALR(1) parser generator - GitHub
  35. [PDF] TP Lex and Yacc – The Compiler Writer's Tools for Turbo Pascal ...
  36. [PDF] Tools for lexical analysis and parsing - The Caml language
  37. https://git.savannah.gnu.org/cgit/bash.git/tree/parse.y
  38. WL#5967: Use Bison 'locations' for accessing statement text elements
  39. FindBISON — CMake 4.2.0-rc2 Documentation
  40. Parser generators vs. handwritten parsers: surveying major ...
  41. https://git.savannah.gnu.org/cgit/bison.git/tree/NEWS
User Avatar
No comments yet.