1CS780(Prasad) L8Bison 1BisonParser GeneratorAdapted from material by:Charles Donnelly and Richard StallmanJohn LevineCS780(Prasad) L8Bison 2<file>.tab.c<file>.tab.h(yyparse() routinegenerated; others included from input)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.Bison<file>.y(bison format input file, incl. code for yylex, yyerror, andmain.)CS780(Prasad) L8Bison 3Bison input file format• 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) L8Bison 4Bison Declarations• define terminals and nonterminals• define attributes and their associations with terminals and nonterminals• specify precedence and associativity%union {int val;char *varname;}%type <val> exp%token <varname> NAME%right =%left + -%left * /2CS780(Prasad) L8Bison 5Rules• General form of a ruleLHS: rule1-RHS... { action 1}| rule2-RHS... { action 2} ...;¾ 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: ...| exp '+' exp { $$ = $1 + $3; };CS780(Prasad) L8Bison 6Semantic Values and Actions• 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)The types for the semantic values are specified in the declaration section.CS780(Prasad) L8Bison 7A Simple Bison Example : calc.y. . . Bison Declarations . . .%%stmt: NAME ‘=‘ expr { printf(“%c = %d\n”, $1, $3); }| expr { printf(“= %d\n”, $1); };expr: expr ‘+’ NUMBER { $$ = $1 + $3; }|expr ‘-’ NUMBER { $$ = $1 - $3; }| NUMBER { $$ = $1; }%%. . . User code . . .CS780(Prasad) L8Bison 8(cont’d)%{#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();}3CS780(Prasad) L8Bison 9calc.flex%{#include "calc.tab.h"extern YYSTYPE yylval;%}%%[0-9]+ {yylval.val = atoi(yytext); return NUMBER;}[ \t]+ ; /* ignore whitespaces */[a-zA-Z] {yylval.var = yytext[0]; return NAME;}\n return 0; /* logical EOF */. return yytext[0];%% CS780(Prasad) L8Bison 10Generating Parser•Create <EG>.y and <EG>.flex files • Run bison and flex (in that order)bison -d <EG>.y <EG>.y contains yyerror() and main() bison generates <EG>.tab.c <EG>.tab.hflex <EG>.flex <EG>.flex includes <EG>.tab.h;  flex generates lex.yy.c• Compile generated C filesgcc –o eg <EG>.tab.c lex.yy.c –lfl• Execute the applicationegp = 23 – 5 + 4p = 22CS780(Prasad) L8Bison 11calc.tab.htypedef union {int val;char var;} YYSTYPE;#define NUMBER 257#define NAME 258extern YYSTYPE yylval;CS780(Prasad) L8Bison 12Precedence and Associativity. . .%type <val> stmt%right ‘=’%left ‘-’ ‘+’%nonassoc UMINUS%%stmt: NAME ‘=‘ stmt {$$ = $3; printf(“%s = %d\n”, $1, $3); }| expr {};expr: expr ‘+’ expr { $$ = $1 + $3; }| expr ‘-’ expr { $$ = $1 - $3; }| NUMBER { $$ = $1; }| ‘-’ NUMBER %prec UMINUS { $$ = - $2; }4CS780(Prasad) L8Bison 13Sample RunegAdvj = k = l = 56l = 56k = 56j = 56egAdvp = 1 + 2 – 3 – 4p = -4egAdvq = –3 –4q = – 7egAdvq = – – 4parse errorCS780(Prasad) L8Bison 14A Cool Parser1. Check for correct syntax¾ Write Bison grammar rules which match the Cool grammar in CoolAid2. 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 code3. Perform Error recovery for common cases¾ Use Bison error