Grammars and Normal FormsDisjunctive Normal Form for QueriesNormal Forms for GrammarsTop Down ParsingEGrammars and Normal Forms Read K & S 3.7.Recognizing Context-Free LanguagesTwo notions of recognition:(1) Say yes or no, just like with FSMs(2) Say yes or no, ANDif yes, describe the structure a + b * cNow it's time to worry about extracting structure (and doing so efficiently).Optimizing Context-Free LanguagesFor regular languages:Computation = operation of FSMs. So,Optimization = Operations on FSMs:Conversion to deterministic FSMsMinimization of FSMsFor context-free languages:Computation = operation of parsers. So, Optimization = Operations on languagesOperations on grammarsParser designBefore We Start: Operations on GrammarsThere are lots of ways to transform grammars so that they are more useful for a particular purpose.the basic idea:1. Apply transformation 1 to G to get of undesirable property 1. Show that the language generated by G is unchanged.2. Apply transformation 2 to G to get rid of undesirable property 2. Show that the language generated by G is unchanged AND that undesirable property 1 has not been reintroduced.3. Continue until the grammar is in the desired form.Examples:- Getting rid of - rules (nullable rules)- Getting rid of sets of rules with a common initial terminal, e.g.,- A - aB, A - aC become A - aD, D - B | C- Conversion to normal formsLecture Notes 16 Grammars and Normal Forms 1Normal FormsIf you want to design algorithms, it is often useful to have a limited number of input forms that you have to deal with.Normal forms are designed to do just that. Various ones have been developed for various purposes. Examples:- Clause form for logical expressions to be used in resolution theorem proving- Disjunctive normal form for database queries so that they can be entered in a query by example grid.- Various normal forms for grammars to support specific parsing techniques.Clause Form for Logical Expressions-x : [Roman(x) - know(x, Marcus)] - [hate(x, Caesar) - (-y : -z : hate(y, z) - thinkcrazy(x, y))]becomes-Roman(x) - -know(x, Marcus) - hate(x, Caesar) - -hate(y, z) - thinkcrazy(x, z)Disjunctive Normal Form for Queries(category = fruit or category = vegetable)and(supplier = A or supplier = B)becomes(category = fruit and supplier = A) or(category = fruit and supplier = B) or(category = vegetable and supplier = A) or(category = vegetable and supplier = B)Category Supplier Pricefruit Afruit Bvegetable Avegetable BNormal Forms for GrammarsTwo of the most common are: - Chomsky Normal Form, in which all rules are of one of the following two forms: - X - a, where a - -, or- X - BC, where B and C are nonterminals in G- Greibach Normal Form, in which all rules are of the following form:- X - a -, where a - - and - is a (possibly empty) string of nonterminalsIf L is a context-free language that does not contain -, then if G is a grammar for L, G can be rewritten into both of these normal forms.Lecture Notes 16 Grammars and Normal Forms 2What Are Normal Forms Good For?Examples:- Chomsky Normal Form:- X - a, where a - -, or- X - BC, where B and C are nonterminals in G- The branching factor is precisely 2. Tree building algorithms can take advantage of that.- Greibach Normal Form- X - a -, where a - - and - is a (possibly empty) string of nonterminals-Precisely one nonterminal is generated for each rule application. This means that we can put a bound on the number of rule applications in any successful derivation.Conversion to Chomsky Normal FormLet G be a grammar for the context-free language L where - - L.We construct G', an equivalent grammar in Chomsky Normal Form by:0. Initially, let G' = G.1. Remove from G' all - productions:1.1. If there is a rule A - -B- and B is nullable, add the rule A - -- and delete the rule B - -.Example:S - aA A - B | CDB - -B - aC - BDD - b D - -Conversion to Chomsky Normal Form2. Remove from G' all unit productions (rules of the form A - B, where B is a nonterminal):2.1. Remove from G' all unit productions of the form A - A.2.2. For all nonterminals A, find all nonterminals B such that A -* B, A - B.2.3. Create G'' and add to it all rules in G' that are not unit productions.2.4. For all A and B satisfying 3.2, add to G'' A - y1 | y2 | … where B - y1 | y2 | is in G".2.5. Set G' to G''.Example: A - aA - BA - EFB - AB - CDB - CC - abAt this point, all rules whose right hand sides have length 1 are in Chomsky Normal Form.Lecture Notes 16 Grammars and Normal Forms 3Conversion to Chomsky Normal Form3. Remove from G' all productions P whose right hand sides have length greater than 1 and include a terminal (e.g., A - aB or A - BaC):3.1. Create a new nonterminal Ta for each terminal a in -.3.2. Modify each production P by substituting Ta for each terminal a.3.3. Add to G', for each Ta, the rule Ta - aExample:A - aBA - BaCA - BbCTa - a Tb - bConversion to Chomsky Normal Form4. Remove from G' all productions P whose right hand sides have length greater than 2 (e.g., A - BCDE)4.1. For each P of the form A - N1N2N3N4…Nn, n > 2, create new nonterminals M2, M3, … Mn-1.4.2. Replace P with the rule A - N1M2.4.3. Add the rules M2 - N2M3, M3 - N3M4, … Mn-1 - Nn-1NnExample:A - BCDE (n = 4)A - BM2M2 - C M3M3 - DELecture Notes 16 Grammars and Normal Forms 4Top Down ParsingRead K & S 3.8.Read Supplementary Materials: Context-Free Languages and Pushdown Automata: Parsing, Sections 1 and 2.Do Homework 15.ParsingTwo basic approaches:Top DownE - E - E E + T . + T..idBottom Up EET TF F Fid + id - id + id - id + idA Simple Parsing ExampleA simple top-down parser for arithmetic expressions, given the grammar[1] E - E + T[2] E - T[3] T - T * F[4] T - F[5] F - (E)[6] F - id[7] F - id(E)A PDA that does a top down parse:(0) (1, -, -), (2, E)(1) (2, -, E), (2, E+T)(2) (2, -, E), (2, T)(3) (2, -, T), (2, T*F)(4) (2, -, T), (2, F)(5) (2, -, F), (2, (E) )(6) (2, -, F), (2, id) (7) (2, -, F), (2, id(E))(8) (2, id, id), (2, -)(9) (2, (, ( ), (2, -)(10) (2, ), ) ), (2, -)(11) (2, +, +), (2, -)(12) (2, *, *), (2, -)Lecture Notes 17 Top Down Parsing 0How Does It Work?Example: id + id * id(id)Stack: EWhat Does It Produce?The leftmost derivation of the string. Why?E - E + T - T + T - F + T - id + T - id + T * F - id + F * F - id + id * F - id + id * id(E) - id + id
View Full Document
Unlocking...