ML YACC David Walker COS 320 Outline Last Week Introduction to Lexing CFGs and Parsing Today More parsing automatic parser generation via ML Yacc Reading Chapter 3 of Appel Parser Implementation Implementation Options 1 Write a Parser from scratch not as boring as writing a lexer but not exactly a weekend in the Bahamas 2 Use a Parser Generator Very general robust sometimes not quite as efficient as hand written parsers Nevertheless good for lazy compiler writers Parser Specification Parser Implementation Implementation Options 1 Write a Parser from scratch not as boring as writing a lexer but not exactly a weekend in the Bahamas 2 Use a Parser Generator Very general robust sometimes not quite as efficient as hand written parsers Nevertheless good for lazy compiler writers Parser Specification Parser parser generator Parser Implementation Implementation Options 1 Write a Parser from scratch not as boring as writing a lexer but not exactly a weekend in the Bahamas 2 Use a Parser Generator Very general robust sometimes not quite as efficient as hand written parsers Nevertheless good for lazy compiler writers stream of tokens Parser Specification Parser parser generator abstract syntax ML Yacc specification three parts User Declarations declare values available in the rule actions ML Yacc Definitions declare terminals and non terminals special declarations to resolve conflicts Rules parser specified by CFG rules and associated semantic action that generate abstract syntax ML Yacc declarations preliminaries specify type of positions pos int int specify terminal and nonterminal symbols term IF THEN ELSE PLUS MINUS nonterm prog exp op specify end of parse token eop EOF specify start symbol by default non terminal in LHS of first rule start prog Simple ML Yacc Example grammar symbols term NUM PLUS MUL LPAR RPAR nonterm exp fact base grammar rules pos int start exp eop EOF semantic actions currently do nothing exp fact fact PLUS exp fact base base MUL factor base NUM LPAR exp RPAR attribute grammars ML Yacc uses an attribute grammar scheme each nonterminal may have a semantic value associated with it when the parser reduces with X s a semantic action will be executed uses semantic values from symbols in s when parsing is completed successfully parser returns semantic value associated with the start symbol usually a parse tree attribute grammars semantic actions typically build the abstract syntax for the internal language to use semantic values during parsing we must declare symbol types terminal NUM of int PLUS MUL nonterminal exp of int fact of int base of int type of semantic action must match type declared for LHS nonterminal in rule ML Yacc with Semantic Actions grammar symbols with type declarations grammar rules with semantic actions term NUM of int PLUS MUL LPAR RPAR nonterm exp of int fact of int base of int pos int start exp eop EOF computing integer result via semantic actions exp fact fact PLUS exp fact fact exp fact base base MUL base base base1 base2 base NUM LPAR exp RPAR NUM exp ML Yacc with Semantic Actions datatype exp Int of int Add of exp exp Mul of exp exp exp fact fact PLUS exp fact Add fact exp fact base base MUL exp base Mul base exp base NUM LPAR exp RPAR Int NUM exp computing abstract syntax via semantic actions A simpler grammar datatype exp Int of int Add of exp exp Mul of exp exp exp NUM exp PLUS exp exp MUL exp LPAR exp RPAR why don t we just use this simpler grammar Int NUM Add exp1 exp2 Mul exp1 exp2 exp A simpler grammar datatype exp Int of int Add of exp exp Mul of exp exp exp NUM exp PLUS exp exp MUL exp LPAR exp RPAR this grammar is ambiguous Int NUM Add exp1 exp2 Mul exp1 exp2 exp E E NUM NUM NUM NUM E E NUM E E E NUM E NUM E E NUM NUM a simpler grammar datatype exp Int of int Add of exp exp Mul of exp exp But it is so clean that it would be nice to use Moreover we know which parse tree we want We just need a mechanism to specify it exp NUM exp PLUS exp exp MUL exp LPAR exp RPAR Int NUM Add exp1 exp2 Mul exp1 exp2 exp E E NUM NUM NUM NUM E E NUM E E E NUM E NUM E E NUM NUM Recall how LR parsing works desired parse tree exp NUM exp PLUS exp exp MUL exp LPAR exp RPAR E E yet to read Input from lexer NUM NUM NUM State of parse so far NUM E E NUM E NUM E E We have a shift reduce conflict What should we do to get the right parse elements of desired parse parsed so far Recall how LR parsing works desired parse tree exp NUM exp PLUS exp exp MUL exp LPAR exp RPAR E E yet to read Input from lexer NUM NUM NUM State of parse so far NUM E E NUM E NUM E E We have a shift reduce conflict What should we do to get the right parse SHIFT elements of desired parse parsed so far Recall how LR parsing works desired parse tree exp NUM exp PLUS exp exp MUL exp LPAR exp RPAR E E yet to read Input from lexer NUM NUM NUM State of parse so far NUM E E NUM E NUM E E NUM elements of desired parse parsed so far SHIFT SHIFT Recall how LR parsing works desired parse tree exp NUM exp PLUS exp exp MUL exp LPAR exp RPAR E E yet to read Input from lexer NUM NUM NUM State of parse so far NUM E E NUM E NUM E E E elements of desired parse parsed so far REDUCE Recall how LR parsing works desired parse tree exp NUM exp PLUS exp exp MUL exp LPAR exp RPAR E E yet to read Input from lexer NUM NUM NUM State of parse so far NUM E E NUM E NUM E E elements of desired parse parsed so far REDUCE Recall how LR parsing works desired parse tree exp NUM exp PLUS exp exp MUL exp LPAR exp RPAR E E yet to read Input from lexer NUM NUM NUM State of parse so far NUM E E NUM E NUM E elements of desired parse parsed so far REDUCE The alternative parse exp NUM exp PLUS exp exp MUL exp LPAR exp RPAR E yet to read NUM E NUM Input from lexer NUM NUM NUM State of parse so far E E We have a shift reduce conflict Suppose we REDUCE next elements parsed so far The alternative parse exp NUM exp PLUS exp exp MUL exp LPAR exp RPAR E E yet to read NUM E NUM Input from lexer NUM NUM NUM State of parse so far REDUCE E elements parsed so far The alternative parse exp NUM exp PLUS exp exp MUL exp LPAR exp RPAR E E yet to read NUM E NUM Input from lexer NUM NUM NUM State of parse so far E E Now SHIFT SHIFT REDUCE …