Chapter 3 Context-Free Grammars, Context-Free Languages ...

1 Chapter 3 Context-Free Grammars, Context-Free Languages , Parse Treesand Ogden s Context-Free GrammarsA Context-Free grammar basically consists of a finite set of grammar rules. In order to definegrammar rules, we assume that we have two kinds of symbols: the terminals, which are thesymbols of the alphabet underlying the Languages under consideration, and the nonterminals,which behave like variables ranging over strings of terminals. A rule is of the formA ,whereAis a single nonterminal, and the right-hand side is a string of terminal and/ornonterminal symbols. As usual, first we need to define what the object is (a context -freegrammar), and then we need to explain how it is used.

2 Unlike automata, grammars are usedtogeneratestrings, rather than recognize grammar (for short, CFG)is a quadrupleG=(V, ,P,S),where Vis a finite set of symbols called thevocabulary (or set of grammar symbols); Vis the set ofterminal symbols (for short, terminals); S (V ) is a designated symbol called thestart symbol; P (V ) V is a finite set ofproductions (or rewrite rules, or rules).The setN=V is called the set ofnonterminal symbols (for short, nonterminals).Thus,P N V , and every production A, is also denoted asA . A production of theformA is called anepsilon rule, or null 3.

3 Context-Free GRAMMARS AND LANGUAGESR emark: Context-Free grammars are sometimes defined asG=(VN,VT,P,S). Thecorrespondence with our definition is that =VTandN=VN,sothatV=VN ,in this other definition, it is necessary to assume thatVT VN= . ({E, a, b},{a, b},P,E), wherePis the set of rulesE aEb,E we will see shortly, this grammar generates the languageL1={anbn|n 1},whichis not ({E,+, ,(,),a},{+, ,(,),a},P,E), wherePis the set of rulesE E+E,E E E,E (E),E grammar generates a set of arithmetic Derivations and Context-Free LanguagesThe productions of a grammar are used to derive strings.

4 In this process, the productionsare used as rewrite rules. Formally, we define the derivation relation associated with acontext-free grammar . First, let us review the concepts of transitive closure and reflexiveand transitive closure of a binary a setA,abinary relationRonAis any set of ordered pairs, A , instead of binary relation, we often simply say relation. Given any two relationsR, SonA,theircompositionR Sis defined asR S={(x, y) A A| z A,(x, z) Rand (z, y) S}.Theidentity relationIAonAis the relationIAdefined such thatIA={(x, x)|x A}.For short, we often I=I R=Rfor every relationRonA.

5 Given a relationRonA, for anyn 0 we defineRnas follows:R0=I,Rn+1=Rn DERIVATIONS AND Context-Free LANGUAGES35It is obvious thatR1=R. It is also easily verified by induction thatRn R=R closureR+of the relationRis defined asR+= n is easily verified thatR+is the smallest transitive relation containingR,andthat(x, y) R+iff there is somen 1andsomex0,x1,..,xn Asuch thatx0=x,xn=y,and (xi,xi+1) Rfor alli,0 i n 1. Thetransitive and reflexive closureR of therelationRis defined asR = n ,R =R+ I. It is easily verified thatR is the smallest transitive and reflexiverelation a Context-Free grammarG=(V, ,P,S), the (one-step)derivationrelation= Gassociated withGis the binary relation = G V V defined as follows:for all , V ,wehave = G iff there exist , V , and some production (A ) P, such that = A and =.

6 The transitive closure of = Gis denoted as+= Gand the reflexive and transitive closure of= Gis denoted as = the grammarGis clear from the context , we usually omit the subscriptGin = G,+= G,and = string V such thatS = is called asentential form, and a stringw suchthatS = wis called asentence. A derivation = involvingnsteps is denoted as n= .Note that a derivation step = G is rather nondeterministic. Indeed, one can choose among various occurrences of nontermi-nalsAin , and also among various productionsA with left-hand example, using the grammarG1=({E, a, b},{a, b},P,E), wherePis the set of rulesE aEb,E ab,36 Chapter 3.

7 Context-Free GRAMMARS AND Languages every derivation fromEis of the formE = anEbn= anabbn=an+1bn+1,orE = anEbn= anaEbbn=an+1 Ebn+1,wheren very simple: every stringanbnhas a unique derivation. This is usuallynot the case. For example, using the grammarG2=({E,+, ,(,),a},{+, ,(,),a},P,E),wherePis the set of rulesE E+E,E E E,E (E),E a,the stringa+a ahas the following distinct derivations, where the boldface indicates whichoccurrence ofEis rewritten:E= E E= E+E E= a+E E= a+a E= a+a a,andE= E+E= a+E= a+E E= a+a E= a+a the above derivations, the leftmost occurrence of a nonterminal is chosen at each derivations are calledleftmost derivations.

8 We could systematically rewrite the right-most occurrence of a nonterminal, gettingrightmost derivations. The stringa+a aalsohas the following two rightmost derivations, where the boldface indicates which occurrenceofEis rewritten:E= E+E= E+E E= E+E a= E+a a= a+a a,andE= E E= E a= E+E a= E+a a= a+a language generated by a Context-Free grammar is defined as DERIVATIONS AND Context-Free LANGUAGES37 Definition a Context-Free grammarG=(V, ,P,S), thelanguage generatedbyGis the setL(G)={w |S+= w}.A languageL is acontext-free language (for short, CFL)iffL=L(G) for somecontext-free is technically very useful to consider derivations in which the leftmost nonterminal isalways selected for rewriting, and dually, derivations in which the rightmost nonterminal isalways selected for a Context-Free grammarG=(V, ,P,S), the (one-step)leftmostderivation relation= lmassociated withGis the binary relation = lm V V defined asfollows: for all , V ,wehave = lm iff there existu , V , and some production (A ) P, such that =uA and =u.

9 The transitive closure of = lmis denoted as+= lmand the reflexive and transitive closure of= lmis denoted as = lm. The (one-step)rightmost derivation relation= rmassociated withGis the binary relation = rm V V defined as follows: for all , V ,wehave = rm iff there exist V ,v , and some production (A ) P, such that = Avand = transitive closure of = rmis denoted as+= rmand the reflexive and transitive closure of= rmis denoted as = : It is customary to use the symbolsa, b, c, d, efor terminal symbols, and thesymbolsA, B, C, D, Efor nonterminal symbols. The symbolsu, v, w, x, y, zdenote terminalstrings, and the symbols , , , , , denote strings inV.

10 The symbolsX, Y, Zusuallydenote symbols a Context-Free grammarG=(V, ,P,S),parsing a stringwconsists in findingout whetherw L(G), and if so, in producing a derivation forw. The following lemma istechnically very important. It shows that leftmost and rightmost derivations are universal .This has some important practical implications for the complexity of parsing 3. Context-Free GRAMMARS AND LANGUAGESL emma (V, ,P,S)be a Context-Free grammar . For everyw ,forevery derivationS+= w, there is a leftmost derivationS+= lmw, and there is a rightmostderivationS+= Of course, we have to somehow use induction on derivations, but this is a littletricky, and it is necessary to prove a stronger fact.