Description

(CS 753)
Samit Biswas
samit@cs.iiests.ac.in
Department of Computer Science and Technology,
Indian Institute of Engineering Science and Technology, Shibpur
YACC
YACC Parser — Overview
Parser generator
I Takes a specification for a context-free grammar.
I Produces code for a parser.
Output: C Code
Input: a set ofImplementing a Parser
function: yyparse()
grammar rules + Actions
file [default]: y.tab.c
Scanner-Parser interaction
I Parser assumes int yylex() implements the scanner.
I Scanner:
I return value indicates the type of token found;
I other values communicated using yytext, yylval .
I YACC determines integer representations for tokens:
I Communicated to scanner in file y.tab.h use yacc -d to produce y.tab.h I Token encodings:
I “end of file” represented by 0;
I a character literal: its ASCII value;
Scanner-Parser interaction

flex input format
A YACC input file consists of three parts:
definitions required %%
rules optional
%% user code
I Shortest possible legal YACC input:
%%
Definition Section
There are three things that can go in the definitions section:
I C code: Code between %{ and %} is copied to the C file.
I Definitions:
I Associativity Rules: These handle associativity and priority of operators.
Information about Tokens I token names:
I declared using ‘%token’.
I single-character tokens don’t have to be declared.
I any name not declared as a token is assumed to be a nonterminal.
I start symbol of grammar, using %start [optional] I operator info:
I precedence, associativity.
Rules section
The rules section contains the grammar of the language you want to parse. This looks like

I Rule RHS can have arbitrary C code embedded, within {
… }.
Conflicts
I Conflicts arise when there is more than one way to proceed with parsing.
I Two types:
I shift-reduce [default action: shift]
I reduce-reduce [default: reduce with the first rule listed] I Removing conflicts:
I specify operator precedence, associativity;
I restructure the grammar
User code section
The minimal main program is:

Assignment
Write YACC specification to design a parser for a subset of the C language. Consider the following programming language constructs:
I Main function
I Statements
I Statements like local/global declarations.
I Assignment Statements.
I Conditional Statements.
I Iterative Statements
I Function Call
I User defined functions
Consider the assumptions for the language previously considered in last lab sessions. Variables of data types allowed in the subset can be defined at the very beginning of any function / block. A variable must be defined before it is used.