The YACC Parser Generator

From Wiki**3

Compiladores
Introdução ao Desenvolvimento de Compiladores
Aspectos Teóricos de Análise Lexical
A Ferramenta Flex
Introdução à Sintaxe
Análise Sintáctica Descendente
Gramáticas Atributivas
A Ferramenta YACC
Análise Sintáctica Ascendente
Análise Semântica
Geração de Código
Tópicos de Optimização

YACC (yet another compiler compiler) is a grammar parser and parser generator. That is, it is a program that reads a grammar specification and generates code that is able to organize input tokens in a syntactic tree in accordance with the grammar. In addition, the grammar specification has semantic content (in the form of actions associated with grammar rules) that are also organized to be executed when tree nodes are built ("reduced" is the actual term).

The parser generated by YACC is an LALR(1) parser with a few pragmatic extensions to deal with non-LALR(1) grammars and other problems having to do with the fact that grammars sometimes are wrong and YACC must signal those problems in a useful way, so that the grammar creator can improve it. Examples of these extensions are error handling (e.g. in case of conflicts). Theoretically, in the presence of conflicts, the parser could be said not to exist, but YACC solves the problem by coding default behavior when needed. These behaviors may be what is needed, but, in general, it is an error using grammars that give rise to conflicts in the parser. These matters will be discussed below.

After a successful run, YACC will produce, at least, the yyparse() function, which runs the parser and produces the syntax-driven evaluation of the semantic actions in the rules. This function, when the appropriate actions are coded, produces the syntactic tree as a data structure (a tree, which may not come as much of a surprise).

Basic Concepts

YACC source files have three main sections divided by %%. The first section contains definitions and declarations used by YACC and the generated C code. The second section contains the grammar rules and associated semantic actions. The third section can contain additional C code to be copied directly to the output file (it is usually empty).

When YACC runs, it reads the source file and generates a C source file (usually named y.tab.c), which contains the parsing function yyparse(). This function, when called, reads tokens, parses them according to the grammar rules, and executes the associated actions. This will usually result in building a parse tree, interpreting the program, or translating it into another language.

Error Recovery

Conflicts

How to debug

Do:

export YYDEBUG=1

Add this to the rules section of the scanner file (.l) (without any rule at the beginning of the line):

   { yydebug = 1; }

Examples

Exercises

See Also