View source for The YACC Parser Generator

{{NAVCompiladores}}
{{TOCright}}

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 ==

* [[The YACC Parser Generator/Example: Calculator with Variables|Calculator with Variables]]

== Exercises ==

* [[The YACC Parser Generator/Exercise 1|Exercise 1]]
* [[The YACC Parser Generator/Exercise 2|Exercise 2]]
* [[The YACC Parser Generator/Exercise 3|Exercise 3]]
* [[The YACC Parser Generator/Exercise 4|Exercise 4]]
* [[The YACC Parser Generator/Exercise 5|Exercise 5]]
* [[The YACC Parser Generator/Exercise 6|Exercise 6]] -- maximum interval -- Test 2 2016/06/17
* [[The YACC Parser Generator/Exercise 7|Exercise 7]] -- minimum interval -- Test 2 2016/06/17
* [[The YACC Parser Generator/Exercise 8|Exercise 8]] -- number sequences
* [[The YACC Parser Generator/Exercise 9|Exercise 9]] -- more number sequences

== See Also ==

* [[Attribute Grammars]]
* [[Bottom-Up Parsing]]

[[category:Compiladores]]
[[category:Ensino]]