OutlineObjectives and ReviewQuick reviewParsingParser Generation with OCamlOutlineObjectives and ReviewQuick reviewParsingParser Generation with OCamlCS421 Lecture 14: Parsing1Mark [email protected] of Illinois at Urbana-ChampaignJuly 10, 20061Based on slides by Mattox Beckman, as updated by Vikram Adve, GulAgha, and Elsa GunterMark Hills CS421 Lecture 14: ParsingOutlineObjectives and ReviewQuick reviewParsingParser Generation with OCamlObjectives and ReviewQuick reviewParsingParser Generation with OCamlMark Hills CS421 Lecture 14: ParsingOutlineObjectives and ReviewQuick reviewParsingParser Generation with OCamlObjectivesAt the end of this lecture, you should be able to◮Explain two different style of parsing◮Top-down parsing◮Bottom-up parsing◮Understand when you would use one versus the other◮Use ocamlyacc to write parser definitionsMark Hills CS421 Lecture 14: ParsingOutlineObjectives and ReviewQuick reviewParsingParser Generation with OCamlCFGs, Derivations, Parse TreesExampleContext-free GrammarsDef: A Context-free Grammar (CFG) is a 4-tuple:G = (N, Σ, P, S)where:1. N is the set of nonterminals2. Σ is the set of terminals (tokens)3. P is the set of productions (rules)4. S is the start symbol, and is one of the nonterminals in NMark Hills CS421 Lecture 14: ParsingOutlineObjectives and ReviewQuick reviewParsingParser Generation with OCamlCFGs, Derivations, Parse TreesExampleDerivations and Parse Trees◮A Derivation is a sequence of steps that, starting with thestart symbol, leads to a sentence in the language (a stringwith only terminals). Each derivation step replaces onenonterminal with the right-hand side of one production.◮A Parse Tree is a tree representation of a derivation, withnonterminals as nodes and either nonterminals or terminals asleaves (only terminals for a derivation, both while building thetree). A node’s children are based directly on the terminalsand nonterminals on the right-hand side of the rule used toconstruct them.Mark Hills CS421 Lecture 14: ParsingOutlineObjectives and ReviewQuick reviewParsingParser Generation with OCamlCFGs, Derivations, Parse TreesExampleAST versus Parse TreeWhile a parse tree keeps track of all productions used to build theparse tree, an AST is a condensed form of this with just theinformation needed in later stages of compilation or interpretation.Mark Hills CS421 Lecture 14: ParsingOutlineObjectives and ReviewQuick reviewParsingParser Generation with OCamlCFGs, Derivations, Parse TreesExampleAST vs Parse Tree – Exampleexpexp+expexp∗term termtermfactor3factor4factor5+∗53 4Mark Hills CS421 Lecture 14: ParsingOutlineObjectives and ReviewQuick reviewParsingParser Generation with OCamlCFGs, Derivations, Parse TreesExampleExample Grammar: Arithmetic ExpressionsG = (N, Σ, P, S) where:N = {E , T , F }Σ = {(, ), +, ∗, id}P = {E → TE → E + TT → FT → T ∗ FF → idF → (E )}S = E.Note: P ⊆ N × V∗, whereV = N ∪ Σ ={E , T , F , (, ), +, ∗, id}Note: (A, α) ∈ P is usually writ-ten:A → αor A ::= αor A : αMark Hills CS421 Lecture 14: ParsingOutlineObjectives and ReviewQuick reviewParsingParser Generation with OCamlParsing MethodsLL ParsingLR ParsingParsing OptionsWe can use CFGs and Backus-Naur form to describe context-freelanguages, but how do we take a stream of tokens and figure outwhich derivation/parse tree is correct?◮General parsing algorithms: CYK◮Restricted parsing methods: LL, LRMark Hills CS421 Lecture 14: ParsingOutlineObjectives and ReviewQuick reviewParsingParser Generation with OCamlParsing MethodsLL ParsingLR ParsingCYK AlgorithmThis algorithm, named after Cocke, Younger, and Kasami, is ageneral algorithm for testing membership in a context-freelanguage.Advantage Algorithm works for any unambiguous grammarDisadvantage Running time is O(n3), much too slow for practicaluse (n is the length of the input)For more information, see §7.4.4 in Hopcroft, Motwani, andUllman.Mark Hills CS421 Lecture 14: ParsingOutlineObjectives and ReviewQuick reviewParsingParser Generation with OCamlParsing MethodsLL ParsingLR ParsingLL ParsingLL parsing methods are faster than the CYK algorithm, but workonly on grammars with some restrictions. LL stands for◮L – Left-to-right scan of input◮L – Leftmost derivationLL methods are categorized by the number of tokens lookaheadneeded. So, LL(1)-methods are left-to-right methods using aleftmost derivation and one token lookahead.Mark Hills CS421 Lecture 14: ParsingOutlineObjectives and ReviewQuick reviewParsingParser Generation with OCamlParsing MethodsLL ParsingLR ParsingLR ParsingLR parsing methods are also faster than the CYK algorithm, butalso work only on grammars with some restrictions. LR stands for◮L – Left-to-right scan of input◮L – Rightmost derivationSimilarly to LL, LR also has lookahead – LR(1) means one token oflookahead. LR methods are more flexible than LL methods – theyhandle a wider class of languages.Mark Hills CS421 Lecture 14: ParsingOutlineObjectives and ReviewQuick reviewParsingParser Generation with OCamlParsing MethodsLL ParsingLR ParsingLL ParsingLL parsing is often called recursive-descent parsing or predictiveparsing (predictive parsing is resursive-descent parsing withoutbacktracking).◮Most hand-written parsers are LL parsers, since they are easierto write than LR parsers◮Few tools use LL techniques – the most notable i s ANTLR,which works over LL(n) grammars (grammars that allowarbitrary lookahead)These are top-down parsing techniques, since they start byexpanding the start symbol and then expand out nonterminalsbased on the input, building the parse tree from the top down.Mark Hills CS421 Lecture 14: ParsingOutlineObjectives and ReviewQuick reviewParsingParser Generation with OCamlParsing MethodsLL ParsingLR ParsingFIRST SetsFIRST sets specify the first terminals that can be part of amember of the vocabulary, based on the productions. Essentially,they tell us when an element of our language vocabulary isstarting. From §4.4, Dragon book:◮If X is a terminal, then FIRST(X ) is {X }◮If X → ǫ is a production, add ǫ to FIRST(X )◮If X → Y1Y2· · · Ynis a production, add token a if a is inFIRST(Yj) and for all i < j ǫ is in FIRST(Yi); if for all iFIRST(Yi) includes ǫ, add ǫ to FIRST(X )Mark Hills CS421 Lecture 14: ParsingOutlineObjectives and ReviewQuick reviewParsingParser Generation with OCamlParsing MethodsLL ParsingLR ParsingFOLLOW SetsFOLLOW sets specify the first
View Full Document
Unlocking...