DOC PREVIEW
Princeton COS 320 - ML-YACC

This preview shows page 1-2-3-22-23-24-44-45-46 out of 46 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Princeton COS 320 - ML-YACC

Download ML-YACC
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view ML-YACC and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view ML-YACC 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?