OutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsCS421 Lecture 13: Introduction to Grammars1Mark [email protected] of Illinois at Urbana-ChampaignJuly 6, 20061Based on slides by Mattox Beckman, as updated by Vikram Adve, GulAgha, and Elsa GunterMark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsObjectives and ReviewContext-Free GrammarsProperties of GrammarsMark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsObjectivesYour goal for this lecture is to learn how to do the following things:◮Identify and explain the parts of a grammar.◮Define terminal, nonterminal, production, sentence,derivation, parse tree, left-recursive, ambiguous.◮Use a grammar to draw the parse tree of a sentence.◮Identify a grammar that is left-recursive.◮Know about ambiguous grammars:◮Be able to identify one when you see it.◮Be able to show ambiguity using derivations or parse trees.◮Know two strategies that could eliminate ambiguity.Mark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsReminder: The Problem◮Computer programs are entered as a stream of ASCIIcharacters.4 + if x > 4 then 5 else 0◮We want to convert them into an Abstract Syntax TreeML code1 PlusExp(2 IntExp 4,3 IfExp(4 GtExp(VarExp "x",5 IntExp 4),6 IntExp 5,7 IntExp 0))Plus4IfGtx45 0Mark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsReminder: The SolutionCharacters Lexer Tokens Parser TreeThe conversion from strings to trees is accomplished in two steps.◮First, convert the stream of characters into a stream oftokens.◮This is called lexing or scanning.◮Turns characters into words and categorizes them.◮We did this in the last few lectures!◮Second, convert the stream of tokens into an abstract syntaxtree.◮This is called parsing.◮Turns words into sentences.Mark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsCFGsExampleDerivations and Parse TreesAmbiguityContext-free GrammarsDef: A Context-free Grammar (CFG) is a 4-tuple:G = (N, Σ, P, S)where:1. N is a finite, nonempty set of symbols (non-terminals)2. Σ is a finite set of symbols (terminals)N ∩ Σ = ΦV ≡ N ∪ Σ (vocabulary)3. P is a finite subset of N × V∗(production rules)4. S ∈ N (Goal symbol or start symbol)Sometimes written as G = (V, Σ, P, S), N = V − ΣMark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsCFGsExampleDerivations and Parse TreesAmbiguityExample 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 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsCFGsExampleDerivations and Parse TreesAmbiguityDerivations of a GrammarDirectly Derives or =⇒ :If α and β are strings in V∗(vocabulary), then αdirectly derivesβ (written α =⇒ β) iff there is aproduction A → δ s.t.− A is a symbol in α− Substituting string δ for A in α produces thestring β.Canonical Derivation Step :The above derivation step is called rightmost if A isthe rightmost non-terminal in α. (Similarly,leftmost.)A rightmost derivation step is also called canonical.Mark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsCFGsExampleDerivations and Parse TreesAmbiguityDerivations and Sentential FormsDerivation :A sequence of steps α0⇒ α1⇒ . . . ⇒ αn, whereα0= S is called a derivation. It is written S ⇒∗αn.If every derivation step is rightmost, then this is acanonical derivation.Sentential Form :Each αiin a derivation is called a sentential formofG.Sentences and the Language L(G) :A sentential form αiconsisting only of tokens (i.e.,terminals) is called a sentence of G.The language generated by G is the set of allsentences of G. It is denoted L(G).Mark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsCFGsExampleDerivations and Parse TreesAmbiguityParse Trees of a GrammarA Parse Tree for a grammar G is any tree in which:◮The root is labeled with S.◮Each leaf is labeled with a token a (a ∈ Σ) or ǫ (the emptystring)◮Each interior node is labeled by a non-terminal.◮If an interior node is labeled A and has children labeledX1, . . . , Xn, then A → X1. . . Xnis a production of G.◮If A → ǫ is a production in G, then a node labeled A mayhave a single child labeled ǫThe string formed by the leaf labels (left to right) is the yield ofthe parse tree.Mark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsCFGsExampleDerivations and Parse TreesAmbiguityParse Trees (continued)◮An intermediate parse tree is the same as a parse treeexcept the leaves can be non-terminals.Notes:◮Every α ∈ L (G) is the yield of some parse tree. Why?◮Consider a derivation, α0⇒ α1⇒ . . . ⇒ αn, where αn∈L(G).For each αi, we can construct an intermediate parse tree.The last one will be the parse tree for the sentence αn.◮A parse tree ignores the order in which symbols are replacedto derive a string.Mark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsCFGsExampleDerivations and Parse TreesAmbiguityDerivations and Parse TreesExample: The rightmost derivation and the parse tree for:id * idE ⇒ T ⇒ T ∗ F ⇒ T ∗ id ⇒ F ∗ id ⇒ id ∗ idETT*FETTF*FidETTFid*FidMark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsCFGsExampleDerivations and Parse TreesAmbiguityUniqueness of DerivationsDerivations and Parse Trees◮Every parse tree has a unique derivation: Yes? No?◮Every parse tree has a unique rightmost derivation: Yes? No?◮Every parse tree has a unique leftmost derivation: Yes? No?Derivations and Parse Trees◮Every
View Full Document