Programming Languages and Compilers (CS 421)Parse Tree Data StructuresSlide 40Slide 41Slide 42Ambiguous Grammars and LanguagesExample: Ambiguous GrammarSlide 45Slide 46Slide 47Slide 48Two Major Sources of AmbiguityHow to Enforce AssociativitySlide 51Operator PrecedencePrecedence Table - SampleFirst Example AgainPredence in GrammarAttribute GrammarsSlide 57Slide 58YACCParsing ProgramsRecursive Decent ParsingSlide 62Slide 63Slide 64Tokens as OCaml TypesParse Trees as DatatypesSlide 67Slide 68Parsing Lists of TokensParsing an ExpressionSlide 71Parsing a Plus ExpressionSlide 73Slide 74Building Plus Expression Parse TreeParsing a Minus ExpressionSlide 77Parsing an Expression as a TermParsing Factor as IdParsing Factor as Parenthesized ExpressionSlide 81Error Cases( a + b ) * c - dSlide 84( a + b ) * c – da + b * c – dSlide 87( a + b * c - da + b ) * c - d *)Streams in Place of ListsProblems for Recursive-Descent ParsingSlide 92Pairwise Disjointedness TestSlide 94Eliminating Left RecursionFactoring GrammarSlide 97LR ParsingExample: <Sum> = 0 | 1 | (<Sum>) | <Sum> + <Sum>Slide 100Slide 101Slide 102Slide 103Slide 104Slide 105Slide 106Slide 107Slide 108Slide 109Slide 110Slide 111Slide 112Slide 113Slide 114Slide 115Slide 116Slide 117Slide 118Slide 119Slide 120Slide 121Programming Languages and Compilers (CS 421)Elsa L Gunter2112 SC, UIUChttp://www.cs.uiuc.edu/class/fa05/cs421/current/Based in part on slides by Mattox Beckman, as updated by Vikram Adve and Gul AghaElsa L. Gunter Parse Tree Data Structures•Parse trees may be represented by SML datatypes•One datatype for each nonterminal•One constructor for each rule•Defined as mutually recursive collection of datatype declarationsElsa L. Gunter Example•Recall grammar:<exp> ::= <factor> | <factor> + <factor><factor> ::= <bin> | <bin> * <exp><bin> ::= 0 | 1•datatype exp = Factor2Exp of factor | Plus of factor * factor and factor = Bin2Factor of bin | Mult of bin * exp and bin = Zero | OneElsa L. Gunter Example cont.•1 * 1 + 0: <exp> <factor> <bin> * <exp> 1 <factor> + <factor> <bin> <bin> 1 0Elsa L. Gunter Example cont.•Can be represented asFactor2Exp(Mult(One, Plus(Bin2Factor One, Bin2Factor Zero)))Elsa L. Gunter Ambiguous Grammars and Languages•A BNF grammar is ambiguous if its language contains strings for which there is more than one parse tree•If all BNF’s for a language are ambiguous then the language is inherently ambiguousElsa L. Gunter Example: Ambiguous Grammar•0 + 1 + 0 <Sum> <Sum> <Sum> + <Sum> <Sum> + <Sum><Sum> + <Sum> 0 0 <Sum> + <Sum> 0 1 1 0Elsa L. Gunter Example•What is the result for:3 + 4 * 5 + 6Elsa L. Gunter Example•What is the result for:3 + 4 * 5 + 6•Possible answers:– 41 = ((3 + 4) * 5) + 6– 47 = 3 + (4 * (5 + 6))– 29 = (3 + (4 * 5)) + 6 = 3 + ((4 * 5) + 6)– 77 = (3 + 4) * (5 + 6)Elsa L. Gunter Example•What is the value of:7 – 5 – 2Elsa L. Gunter Example•What is the value of:7 – 5 – 2•Possible answers:–In Pascal, C++, SML assoc. left 7 – 5 – 2 = (7 – 5) – 2 = 0–In APL, associate to right 7 – 5 – 2 = 7 – (5 – 2) = 4Elsa L. Gunter Two Major Sources of Ambiguity•Lack of determination of operator precedence•Lack of determination of operator assoicativity•Not the only sources of ambiguityElsa L. Gunter How to Enforce Associativity•Have at most one recursive call per production•When two or more recursive calls would be natural, leave right-most one for right assoicativity, left-most one for left assoiciativityElsa L. Gunter Example•<Sum> ::= 0 | 1 | <Sum> + <Sum> | (<Sum>)•Becomes–<Sum> ::= <Num> | <Num> + <Sum>–<Num> ::= 0 | 1 | (<Sum>)Elsa L. Gunter Operator Precedence•Operators of highest precedence evaluated first (bind more tightly).•Precedence for infix binary operators given in following table•Needs to be reflected in grammarElsa L. Gunter Precedence Table - SampleFortan Pascal C/C++ Ada SMLhighest ** *, /, div, mod++, -- ** div, mod, /, **, / +, - *, /, % *, /, mod+, -, ^+, - +, - +, - ::Elsa L. Gunter First Example Again•In any above language, 3 + 4 * 5 + 6 = 29•In APL, all infix operators have same precedence–Thus we still don’t know what the value is (handled by associativity)•How do we handle precedence in grammar?Elsa L. Gunter Predence in Grammar•Higher precedence translates to longer derivation chain•Example:<exp> ::= <id> | <exp> + <exp> | <exp> * <exp>•Becomes<exp> ::= <mult_exp> | <exp> + <mult_exp><mult_exp> ::= <id> | <mult_exp> * <id>Elsa L. Gunter Attribute Grammars•Attribute grammars add to BNF grammars an additional field with a function describing the meaning (attributes) of the construct described by the BNF rule•Attributes can be used to describe an interpreter or even a simple compiler•Usually used to describe abstract syntax trees to be generatedElsa L. Gunter Example•<Sum> ::= 0–value(<Sum>) = 0•<Sum >::= 1–value(<Sum>) = 1•<Sum> ::= <Sum> + <Sum>–value(<Sum1>) = value(<Sum2>) + value(<Sum3>)•<Sum> ::= (<Sum>)–value (<Sum1>) = value(<Sum2>)Elsa L. Gunter Attribute Grammars•An inherited attribute describes the meaning of the nonterminals on the right in the rule in terms of the nonterminal on the left•A synthesized attribute describes the meaning of the left-hand nonterminal in terms of the nonterminals on the rightElsa L. Gunter YACC•The input to YACC (a parser generator for C) is basically an attribute grammar with only synthesized attributes (inherited attributes can be handled using global variables (typically tables))•ocamlyacc is a version of YACC that produces Ocaml code instead of C codeElsa L. Gunter Parsing Programs•Parsing is the process of tracing or constructing a parse tree for a given input string•Process usually broken into two phases:–Lexer: generating tokens from string or character stream–Parser: generating parse tree from token list or stream–Lexer called from parserElsa L. Gunter Recursive Decent Parsing•Recursive decent parsers are a class of parsers derived fairly directly from BNF grammar•A recursive descent parser traces out a parse tree in top-down order, corresponding to a left-most derivation (LL - lelt-to-right scanning, leftmost
View Full Document
Unlocking...