ML-YACCOutlineParser ImplementationSlide 4Slide 5ML-Yacc specificationML-Yacc declarations (preliminaries)Simple ML-Yacc Exampleattribute-grammarsSlide 10ML-Yacc with Semantic ActionsSlide 12A simpler grammarSlide 14a simpler grammarRecall how LR parsing works:Slide 17Slide 18Slide 19Slide 20Slide 21The alternative parseSlide 23Slide 24Slide 25SummaryExample 2Slide 28Slide 29Slide 30Example 2: Summaryprecedence and associativitySlide 33Slide 34Slide 35Slide 36Slide 37Slide 38one more exampleSlide 40the fixSlide 42the dangling else problemSlide 44default behavior of ML-YaccNote: To enter ML-Yacc hell, use a parser to catch type errorsML-YACCDavid WalkerCOS 320Outline•Last Week–Introduction to Lexing, CFGs, and Parsing•Today:–More parsing:•automatic parser generation via ML-Yacc–Reading: Chapter 3 of AppelParser Implementation•Implementation Options:1. Write a Parser from scratch–not as boring as writing a lexer, but not exactly a weekend in the Bahamas2. Use a Parser Generator–Very general & robust. sometimes not quite as efficient as hand-written parsers. Nevertheless, good for lazy compiler writers.Parser SpecificationParser Implementation•Implementation Options:1. Write a Parser from scratch–not as boring as writing a lexer, but not exactly a weekend in the Bahamas2. Use a Parser Generator–Very general & robust. sometimes not quite as efficient as hand-written parsers. Nevertheless, good for lazy compiler writers.Parser SpecificationparsergeneratorParserParser Implementation•Implementation Options:1. Write a Parser from scratch–not as boring as writing a lexer, but not exactly a weekend in the Bahamas2. Use a Parser Generator–Very general & robust. sometimes not quite as efficient as hand-written parsers. Nevertheless, good for lazy compiler writers.Parser SpecificationparsergeneratorParserabstract syntaxstream oftokensML-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 syntaxML-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 progSimple ML-Yacc Example%%%term NUM | PLUS | MUL | LPAR | RPAR%nonterm exp | fact | base%pos int%start exp%eop EOF%%exp : fact () | fact PLUS exp ()fact : base () | base MUL factor ()base : NUM () | LPAR exp RPAR ()grammar rulessemantic actions(currentlydo nothing)grammarsymbolsattribute-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 treeattribute-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 ruleML-Yacc 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%%exp : fact (fact) | fact PLUS exp (fact + exp)fact : base (base) | base MUL base (base1 * base2)base : NUM (NUM) | LPAR exp RPAR (exp)grammar ruleswithsemantic actionsgrammarsymbolswithtypedeclarationscomputinginteger resultvia semanticactionsML-Yacc with Semantic Actionsdatatype exp = Int of int | Add of exp * exp | Mul of exp * exp%%...%%exp : fact (fact) | fact PLUS exp (Add (fact, exp))fact : base (base) | base MUL exp (Mul (base, exp))base : NUM (Int NUM) | LPAR exp RPAR (exp)computingabstract syntaxvia semanticactionsA simpler grammardatatype exp = Int of int | Add of exp * exp | Mul of exp * exp%%...%%exp : NUM (Int NUM) | exp PLUS exp (Add (exp1, exp2)) | exp MUL exp (Mul (exp1, exp2)) | LPAR exp RPAR (exp)why don’t we just use this simpler grammar?A simpler grammardatatype exp = Int of int | Add of exp * exp | Mul of exp * exp%%...%%exp : NUM (Int NUM) | exp PLUS exp (Add (exp1, exp2)) | exp MUL exp (Mul (exp1, exp2)) | LPAR exp RPAR (exp)this grammar isambiguous! NUM + NUM * NUMNUMNUMNUM+*EEEE ENUMNUMNUM*+EEEE Ea simpler grammardatatype exp = Int of int | Add of exp * exp | Mul of exp * exp%%...%%exp : NUM (Int NUM) | exp PLUS exp (Add (exp1, exp2)) | exp MUL exp (Mul (exp1, exp2)) | LPAR exp RPAR (exp)But it is so cleanthat it would be nice to use. Moreover, weknow which parsetree we want. Wejust need a mechanism to specify it!NUM + NUM * NUMNUMNUMNUM+*EEEE ENUMNUMNUM*+EEEE ERecall how LR parsing works:exp ::= NUM | exp PLUS exp | exp MUL exp | LPAR exp RPAR NUM + NUM * NUMState of parse so far:Input from lexer:E + E yet to readNUMNUMNUM*+EEEE Edesired parse tree:We have a shift-reduce conflict.What should we do to get the right parse?elements ofdesired parseparsed so farRecall how LR parsing works:exp ::= NUM | exp PLUS exp | exp MUL exp | LPAR exp RPAR NUM + NUM * NUMState of parse so far:Input from lexer:E + E * yet to readNUMNUMNUM*+EEEE Edesired parse tree:We have a shift-reduce conflict.What should we do to get the right parse?SHIFTelements ofdesired parseparsed so farRecall how LR parsing works:exp ::= NUM | exp PLUS exp | exp MUL exp | LPAR exp RPAR NUM + NUM * NUMState of parse so far:Input from lexer:E + E * NUM yet to readNUMNUMNUM*+EEEE Edesired parse tree:elements ofdesired parseparsed so farSHIFT SHIFTRecall how LR parsing works:exp ::= NUM | exp PLUS exp | exp MUL exp | LPAR exp RPAR NUM + NUM * NUMState of parse so far:Input from lexer:E + E * E yet to readNUMNUMNUM*+EEEE Edesired parse tree:elements ofdesired parseparsed so farREDUCERecall how LR parsing works:exp ::= NUM | exp PLUS exp | exp MUL exp | LPAR exp RPAR NUM + NUM * NUMState of parse so far:Input from lexer:E + E yet to readNUMNUMNUM*+EEEE Edesired parse tree:elements ofdesired parseparsed so farREDUCERecall how LR parsing
View Full Document