Overview of Bison YACC compatible Bottom up specifically LALR 1 parser generator Interfaces with scanner generated by Flex Scanner called as a subroutine when parser needs the next token file tab c file tab h file y Bison Parser Generator Adapted from material by Charles Donnelly and Richard Stallman John Levine CS780 Prasad L8Bison Bison 1 Bison input file format L8Bison CS780 Prasad L8Bison 2 Bison Declarations define terminals and nonterminals define attributes and their associations with terminals and nonterminals specify precedence and associativity The input file consists of three sections separated by a line with just on it C declarations types variables functions preprocessor commands Bison declarations grammar symbols operator precedence decl attribute data type Grammar rules Additional C code incl scanner yylex CS780 Prasad yyparse routine generated others included from input bison format input file incl code for yylex yyerror and main union int val char varname type val exp token varname NAME right left left 3 CS780 Prasad L8Bison 4 1 Rules Semantic Values and Actions General form of a rule LHS rule1 RHS action 1 rule2 RHS action 2 Actions can manipulate semantic values associated with a nonterminal n refers to the semantic value synthesized attribute of the n th symbol on the RHS refers to the semantic value of the LHS nonterminal Typically an action is of the form f 1 2 m LHS is a nonterminal rule RHS is a sequence of nonterminals and terminals An action can contain C code possibly involving attributes which is executed when the associated grammar rule is reduced exp The types for the semantic values are specified in the declaration section exp exp 1 3 CS780 Prasad L8Bison 5 A Simple Bison Example calc y expr NUMBER expr NUMBER NUMBER 1 3 1 3 1 L8Bison 6 include stdio h union int val char var token val NUMBER token var NAME type val expr Grammar Rules yyerror char s printf s n s main yyparse User code CS780 Prasad L8Bison cont d Bison Declarations stmt NAME expr printf c d n 1 3 expr printf d n 1 expr CS780 Prasad 7 CS780 Prasad L8Bison 8 2 calc flex Generating Parser include calc tab h extern YYSTYPE yylval 0 9 t a zA Z n yylval val return yylval var return EG y contains yyerror and main bison generates EG tab c EG tab h atoi yytext NUMBER ignore whitespaces yytext 0 NAME flex EG flex EG flex includes EG tab h flex generates lex yy c return 0 logical EOF return yytext 0 CS780 Prasad L8Bison 9 Compile generated C files Execute the application eg p 23 5 4 p 22 CS780 Prasad 10 type val stmt right left nonassoc UMINUS stmt NAME stmt 3 printf s d n 1 3 expr 257 258 expr extern YYSTYPE yylval CS780 Prasad L8Bison Precedence and Associativity typedef union int val char var YYSTYPE NUMBER NAME gcc o eg EG tab c lex yy c lfl calc tab h define define Create EG y and EG flex files Run bison and flex in that order bison d EG y L8Bison 11 CS780 Prasad expr expr expr expr NUMBER NUMBER prec UMINUS L8Bison 1 3 1 3 1 2 12 3 Sample Run egAdv j k l 56 l 56 k 56 j 56 egAdv p 1 2 3 4 p 4 CS780 Prasad A Cool Parser egAdv q 3 4 q 7 Check for correct syntax Write Bison grammar rules which match the Cool grammar in CoolAid 2 Build an Abstract Syntax tree AST Write actions in C C to build the Syntax tree Semantic values for the grammar symbols will be pointers to AST nodes AST is output from parsetest program in outline form Use C classes for the three nodes provided in Cool support code 3 Perform Error recovery for common cases Use Bison error token 1 egAdv q 4 parse error L8Bison 13 CS780 Prasad L8Bison 14 4