Yacc Tutorial

Details of Ya

1

AN EXAMPLE As a rst exer ise, we shall develop a parser for the following expression language: exp

!

j j j j

num exp + exp exp exp exp ( exp )



/*C de larations*/ %{ %} /* YACC De larations */ %union { int tokenval; } %token NUM %left '-' '+' %left NEG /* negation--unary minus */

2

/* Grammar follows */ %% exp:

NUM | exp | exp | '-' | '(' ;

{printf("rule '+' exp {printf("rule '-' exp {printf("rule exp %pre NEG {printf("rule exp ')' {printf("rule

1\n");} 2\n");} 3\n");} 4\n");} 5\n");}

%% yyerror(s)

har* s; { printf("%s\n", s); } main () { yyparse (); }

Assume that this ya

s ript is in the le example1.y. If the lex s ript for the language is in example1.l, then the parser for the language is generated by the following: # lex example1.l # ya

-d example1.y #

-o example1 lex.yy. y.tab. -ll

Now suppose that the le junk ontains: 23.4+6.2--2.5+(1.0+2) 3

then the ommand # example1 < junk

will produ e: rule rule rule rule rule rule rule rule rule rule rule

1 1 2 1 4 3 1 1 2 5 2

It is instru tive to tra e the parse tree for this example.

4

Some observations:  Just like a lex s ript, a ya

s ript has three parts:

. . . de nition se tion. . . %%

. . . rules se tion. . .

%%

. . . user de ned fun tions. . .  The de nition se tion is divided into two parts, C

de nitions and ya

de nitions. The C de nitions

are pla ed verbatim in the early part of the generated parser.

 A rule is a produ tion { a tion pair. A produ tion

a tion pair is of the form: A : B C D C-statement; E : G H C-statement; I : J C-statement;

Or if the the left hand side of the produ tion are the same, then A : B C D C-statement | G H C-statement | J C-statement ;

Large YACC DEFINITION SECTION The ya

de nition se tion aloows token de nition, pre eden e and asso iativity de nition, start nonterminal definition, and type de laration of token attributes. 5

 The line %token NUM

announ es the fa t NUM is a token. This helps in

ommuni ation with the lexi al analyser. The lines %left '-' '+' %left NEG

also de lare NEG to be a token. Note that single

hara ter tokens do not have to be de lared to be tokens, However, the above lines also onvey more information.  A single hara ter  These de larations say that '-' and '+' are left as-

so iative and have the same pre eden e. Also that NEG has a higher pre eden e than either of them.

 The token NEG is a hypotheti al token. Its purpose

is to give unary '-' a higher pre eden e than either '-' or '+' through the

exp:

'-' exp %pre NEG {printf("rule 4\n");}

grammar rule.

6

YACC DISAMBIGUATING RULES In absen e of any asso iativity and pre eden e information: 1. In ase of a shift-redu e on i t, shift. 2. In ase of a redu e-redu e on i t, redu e with the earlier rule. From the pre eden e and asso iativity information of tokens, asso iate pre eden e and asso iativity to grammar rules; it is the pre eden e and asso iativity of the last token in the body of the grammar rule. In ase of a shift-redu e on i t, ompare the pre eden e of the symbol to be shifted with the pre eden e of the rule to be used for redu tion. 3. If pre eden e of symbol is higher then shift, else redu e, if the pre eden es of both are the same, then: 4. If the symbol (and the grammar rule) is left asso iative then redu e, else shift.

7

ILLUSTRATING DISAMBIGUATION We shall illustrate the disambiguating rules by using the debugging fa ilities of ya

. To do this, hange the main program to set a variable yydebug to a non-zero value. Also run ya

using the -t swit h. EXAMPLE 1 For the ya

grammar: %start A %% D: 'b' ' '; A: %%

'a' D | 'a' 'b' ' ' ;

the output for the string ab is: Starting parse Entering state 0 Reading a token: Next token is 97 Shifting token 97 ('a'), Entering Reading a token: Next token is 98 Shifting token 98 ('b'), Entering Reading a token: Next token is 99 Shifting token 99 (' '), Entering Redu ing via rule 1 (line 6), 'b' state sta k now 0 1 Entering state 3 Redu ing via rule 2 (line 8), 'a' 8

('a') state 1 ('b') state 2 (' ') state 4 ' ' -> D D -> A

state sta k now 0 Entering state 5 Reading a token: Now at end of input. Shifting token 0 ($), Entering state 6 Now at end of input.

EXAMPLE 2 Consider an example in whi h no asso iativity and pre eden e information is given. %token NUM %% exp:

%%

NUM | exp | exp | '-' | '(' ;

'+' exp '-' exp exp exp ')'

For the input 23.4+6.2-2.5, the output is: Starting parse Entering state 0 Reading a token: Next token is 258 (NUM) Shifting token 258 (NUM), Entering state 1 Redu ing via rule 1 (line 11), NUM -> exp redu ing by rule 1 state sta k now 0 9

Entering state 4 Reading a token: Next token is 43 ('+') Shifting token 43 ('+'), Entering state 8 Reading a token: Next token is 258 (NUM) Shifting token 258 (NUM), Entering state 1 Redu ing via rule 1 (line 11), NUM -> exp redu ing by rule 1 state sta k now 0 4 8 Entering state 11 Reading a token: Next token is 45 ('-') Shifting token 45 ('-'), Entering state 7 Reading a token: Next token is 258 (NUM) Shifting token 258 (NUM), Entering state 1 Redu ing via rule 1 (line 11), NUM -> exp redu ing by rule 1 state sta k now 0 4 8 11 7 Entering state 10 Reading a token: Now at end of input. Redu ing via rule 3 (line 13), exp '-' exp -> exp redu ing by rule 3 state sta k now 0 4 8 Entering state 11 Now at end of input. Redu ing via rule 2 (line 12), exp '+' exp -> exp redu ing by rule 2 state sta k now 0 Entering state 4 Now at end of input. Shifting token 0 ($), Entering state 12 Now at end of input. 10

EXAMPLE 3 For our original example, for the same input, the output will be: Starting parse Entering state 0 Reading a token: Next token is 258 (NUM) Shifting token 258 (NUM), Entering state 1 Redu ing via rule 1 (line 14), NUM -> exp redu ing by rule 1 state sta k now 0 Entering state 4 Reading a token: Next token is 43 ('+') Shifting token 43 ('+'), Entering state 8 Reading a token: Next token is 258 (NUM) Shifting token 258 (NUM), Entering state 1 Redu ing via rule 1 (line 14), NUM -> exp redu ing by rule 1 state sta k now 0 4 8 Entering state 11 Redu ing via rule 2 (line 15), exp '+' exp -> exp redu ing by rule 2 state sta k now 0 Entering state 4 Reading a token: Next token is 45 ('-') Shifting token 45 ('-'), Entering state 7 Reading a token: Next token is 258 (NUM) Shifting token 258 (NUM), Entering state 1 Redu ing via rule 1 (line 14), NUM -> exp redu ing by rule 1 11

state sta k now 0 4 7 Entering state 10 Redu ing via rule 3 (line 16), exp '-' exp -> exp redu ing by rule 3 state sta k now 0 Entering state 4 Reading a token: Now at end of input. Shifting token 0 ($), Entering state 12 Now at end of input.

12

INTERACTION

How does the parser intera t with the parser. One way is to physi ally insert the yylex() fun tion in the generated parser. Then the de larations in the generated parser are available to the lexer. A better way is to ommuni ate through the ya

generated header le y.tab.h, using the swit h -d. Here is y.tab.h for a variation of the rst example. Only the de laration part is shown: example. /* YACC De larations */ %union { double tokenval; } %token NUM %type exp %left '-' '+' %left '*' '/' %left NEG /* negation--unary minus */ /* Grammar follows */ %% exp:

NUM | exp '+' exp | exp '-' exp 13

; %%

The generated y.tab.h le is: typedef union { int double; } YYSTYPE; #define NUM 258 #define NEG 259 extern YYSTYPE yylval;

 For single hara ter tokens, ea h hara ter has a

ordinal number whi h is agreed to between the lexer and the parser. So no ommuni ation is ne essary

 For other tokens, ya

generates a number starting

from 256. This information goes in the y.tab.h le.

 ya

also de nes the type YYSTYPE based on the

de laration and de lares the variable yylval to be of this type. yylval is variable used for passing token attributes, also alled semanti values. %union

This le y.tab.h is in luded in the lexer. The lexer for this example looks like: %{ #in lude "example1.tab.h" 14

%} ws [ \t\n℄+ letter [A-Za-z℄ digit [0-9℄ number {digit}+(\.{digit}+)?(E[+\-℄?{digit}+)? %% {ws} {number} "+" "-" "(" ")"

{/*no a tion, no return*/} {yylval.tokenval=atof(yytext); return(NUM);} {return('+');} {return('-');} {return('(');} {return(')');}

%%

15