Analyzing Ambiguity of ContextFree Grammars.ppt

September 26, 2004 [ xsugar ] - Reversible Stylesheets Analyzing Ambiguity of Context-Free Grammars BRICS, Department of Computer Science University of Aarhus, Denmark // Abstract // Outline Introduction Vertical / Horizontal Ambiguity Characterization of Ambiguity (Over-)Approximation Approximation (AMN) Examples and Assessment Related Work Conclusion // Context-Free Grammar N finite set of nonterminals ? finite set of terminals s ? N start nonterminal ? : N ? P(E*) production function, E = N ? ? // CFG Decision Problems Decidable: Membership: ? ? L(GCFG) ! Emptiness: L(GCFG) = ? ! Intersection (w/ REG): L(GCFG) ? L(RREG) = ? ! … Undecidable: Intersection (w/ CFG): L(GCFG) ? L(G’CFG) = ? ? … // Ambiguity: Undecidable! Undecidable! However… // “Side-Stepping Undecidability” Unsafe approximation: Safe approximation: // Motivation Use safe (over-)approximation: “Yes!” ? “G guaranteed unambiguous”!!! Safely use any GLR parser on G Because: we never get two parses at runtime! Hence: dynamic parse ambiguity ? static parse ambiguity // Motivation (cont’d) Undecidability means: “there’ll always be a slack”: However, still useful! Possible interpretations of “No?”: Treat as error (reject grammar): “Please redesign your grammar” (as in LR(k)) Treat as warning: “Here are some potential problems” // Vertical Unambiguity “Vertical unambiguity”: Example: // Horizontal Unambiguity “Horizontal unambiguity”: where: Example: // Characterization of Ambiguity Theorem 1: Lemma 1a: (“?”) Lemma 1b: (“?”) // Proof (Lemma 1a): “?” Lemma 1a: …contrapositively: Proof: Assume G ambiguous (i.e. ? 2 der. trees for ?) Show: by induction in max height of the 2 derivation trees // Proof (Lemma 1a): “?” (Base) Base case (height ? 1): The ambiguity means that: However, this means that ? = t0 t1 ... t|?|-1 = ?(i.e. the two trees must be the same); and so the result holds vacuously // Proof (