COMP 481 John Greiner - UNT Computer Science

COMP 481 John Greiner - UNT Computer Science

CFGs: Formal Definition G = (V, , P, S) V = variables a finite set = alphabet or terminals a finite set P = productions a finite set S = start variable SV Productions form, where AV, (V)*: A 1 CFGs: Derivations Derivations in one step: A G A P x*, ,,(V)* Can choose any variable for use for derivation step. Derivations in zero-or-more steps: G* is the reflexive and transitive closure of G . Language of a grammar: L(G) = {x* | S G* x}

2 Parse Trees S A|AB A |a|Ab|AA B b|bc|Bc|bB Sample derivations: S AB AAB aAB aaB aabB aabb S AB AbB Abb AAbb Aabb aabb These two derivations use same productions, but in different orders. S A Root label = start node. B A A b B a a b Each interior label = variable.

Each parent/child relation = derivation step. Each leaf label = terminal or . All leaf labels together = derived string = yield. 3 Left- & Rightmost Derivations Sample derivations: S A|AB A |a|Ab|AA B b|bc|Bc|bB S A These two derivations are special. B A A b B a a S AB AAB aAB aaB aabB aabb S AB AbB Abb AAbb Aabb aabb

b 1st derivation is leftmost. Always picks leftmost variable. 2nd derivation is rightmost. Always picks rightmost variable. 4 Left / Rightmost Derivations In proofs Restrict attention to left- or rightmost derivations. In parsing algorithms Restrict attention to left- or rightmost derivations. E.g., recursive descent uses leftmost; yacc uses

rightmost. 5 Derivation Trees S A|AB A |a|Ab|AA B b|bc|Bc|bB S A Other derivation trees for this string? w = aabb S B A S B

A A b B A A a a a A b A A a a A b b b A A A

A a b Infinitely many others possible. 6 Ambiguity CFG ambiguous any of following equivalent statements: string w with multiple derivation trees. string w with multiple leftmost derivations. string w with multiple rightmost derivations. Defining ambiguity of grammar, not language. 7

Ambiguity & Disambiguation Given ambiguous grammar, would like an equivalent unambiguous grammar. Allows more knowledge about structure of derivation. Simplifies inductive proofs on derivations. Can lead to more efficient parsing algorithms. In programming languages, want to impose a canonical structure on derivations. E.g., for 1+23. Strategy: Force an ordering on all derivations. 8 Disambiguation Example Exp n | Exp + Exp | Exp Exp What is an equivalent unambiguous

grammar? Exp Term | Term + Exp Term n | n Term Uses operator precedence left-associativity 9 Parsing Designations Major parsing algorithm classes are LL and LR The first letter indicates what order the input is read L means left to right Second letter is direction in the parsing tree the derivation goes, L = top down, R = bottom up

K of LL(k) or LR(k) is number of symbols lookahead in input during parsing Power of parsing techniques LL(k) < LR(k) LL(n) < LL(n+1), LR(n) < LR(n+1) Choice of LL or LR largely religious 10

Recently Viewed Presentations

  • The most recognized signature on the Declaration of

    The most recognized signature on the Declaration of

    During the 1920's these women wore short dresses, went dancing, smoked and drank alcohol. He said people had id, ego and superego. Linked sexuality to many problems. A section of New York City, song writers and musical ideas mixed together...
  • Starter - WordPress.com

    Starter - WordPress.com

    What did Yang and Raine (2009) do and find? What is a meta-analysis? A type of research method that pools data from many other studies to look for overall trends. What did . Tiihonen. et al (2015) do and find?
  • Mood Disorders - Genetic Data

    Mood Disorders - Genetic Data

    www.psychlotron.org.uk Mood Disorders - Genetic Zubenko et al (2001) Family history - 50% of FD relatives, 25% of SD relatives also had mood disorder Relatives had increased risk of suicide & liver disease McGuffin et al (1996) MZ 46%, DZ...
  • Business Information Warehouse This Session provides you with:

    Business Information Warehouse This Session provides you with:

    CO/PA Data Extraction: This method is specific to the extraction of data from the CO/PA application component from SAP R/3. It collects all of the OLTP data for calculative margins (sales, cost of sales, overhead costs). LIS and LO Data...
  • Design Of A Brushless Doubly-fed Induction Motor For ...

    Design Of A Brushless Doubly-fed Induction Motor For ...

    Design of a Brushless Doubly-fed Induction Motor For Adjustable Speed Drive Applications ... A multiphase slip ring assembly is used to transfer power to the rotating winding set and to allow independent control of the rotor winding set.
  • Art as an Investment: The Market for Modern Prints

    Art as an Investment: The Market for Modern Prints

    Topic #5. Application of Portfolio Diversification Theories Art as an Investment: The Market for Modern Prints J. D. Han King's College UWO Returns and Risks *Remark The art prints have the lower rate of return at a given risk, compared...
  • Webinar Participation Tips.. 1. Please enter your Attendee

    Webinar Participation Tips.. 1. Please enter your Attendee

    - Keefe Here is the regional organizational structure for Keefe Group, you will be dealing with Keefe through one of the below individuals: Jim Perry (Western Region VP & main contact) [email protected] Jeff Harris (Eastern Region VP) [email protected] Bill Bosco...
  • Slide pack: Illinois State University Awarding Case Study ...

    Slide pack: Illinois State University Awarding Case Study ...

    Solutions to recognise skills achievement:Using digital credentials to bridge the gap between higher level, technical and professional students and the jobs marketChris Kirk MD of Digitalme, A City & Guilds Group Business 22nd November 2018