YACC

YACC, short for Yet Another Compiler Compiler, is a software tool used to generate parsers for programming languages and other formal languages. It reads a grammar specification and produces source code for a parser in the C programming language. The resulting parser typically implements a deterministic LR parser, specifically an LALR(1) parser, suitable for most practical grammars. YACC works best when paired with a separate lexical analyzer, often produced by Lex, with tokens supplied to the parser via a function named yylex and semantic values carried in yylval.

History: YACC was developed by Stephen C. Johnson at AT&T Bell Labs in the late 1970s and became a standard component of Unix development toolchains. It spawned several variants, including Berkeley Yacc and BSD Yacc. The GNU project later produced Bison, a compatible and more feature-rich alternative that largely adheres to the YACC interface.

Grammar input: A YACC specification includes declarations, grammar rules, and optional semantic actions written in C. Tokens are declared with %token; operator precedence and associativity with %left, %right, and %nonassoc; and the grammar rules may embed C code blocks to build semantic values. YACC resolves ambiguity by precedence declarations and can report conflicts.

Output and integration: Running YACC produces a parser implementation typically named y.tab.c (and sometimes y.tab.h for token constants) which must be compiled with a C compiler, linked with a lexer and runtime. The public interface usually provides int yyparse(void) and token mechanisms such as yylex and yylval.

Variations and compatibility: While compatible with many grammars, YACC differs from GNU Bison in some details. Bison is designed to be largely compatible with YACC grammars but adds extensions and stricter error handling. Other variants include BSD/Berkeley Yacc.