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. 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).

2 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. 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. 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.

3 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. 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 =.

4 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. 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.

5 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.

6 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 . 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.

7 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. We treat leftmost derivations, rightmostderivations being handled in a similar : For everyw , for every V+, for everyn 1, if n= w, then there is aleftmost derivation n= claim is proved by induction ,thereexistsome , V and some productionA , such that = A andw= .Sincewis a terminal string, , ,and , are terminal strings. Thus,Ais theonly nonterminal in , and the derivation step 1= wis a leftmost step (and a rightmoststep!).Ifn>1, then the derivation n= wis of the form = 1n 1= are two If the derivation step = 1is a leftmost step = lm 1, by the inductionhypothesis, there is a leftmost derivation 1n 1= lmw, and we get the leftmost derivation = lm 1n 1= The derivation step = 1is a not a leftmost step.

8 In this case, there mustbe someu , , V , some nonterminalsAandB, and some productionB ,suchthat =uA B and 1=uA ,whereAis the leftmost nonterminal in . Since we have a derivation 1n 1= wof lengthn 1, by the induction hypothesis, there is a leftmost derivation 1n 1= 1=uA whereAis the leftmost terminal in 1, the first step in the leftmostderivation 1n 1= lmwis of the formuA = lmu , DERIVATIONS AND Context-Free LANGUAGES39for some productionA . Thus, we have a derivation of the form =uA B = uA = lmu n 2= can commute the first two steps involving the productionsB andA ,andweget the derivation =uA B = lmu B = u n 2= may no longer be a leftmost derivation, but the first step is leftmost, and we areback in case 1. Thus, we conclude by applying the induction hypothesis to the derivationu B n 1= w, implies thatL(G)={w |S+= lmw}={w |S+= rmw}.We observed that if we consider 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 two distinct leftmost derivations, where the boldfaceindicates which occurrence 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 this happens, we say that we have an ambiguous grammars.

9 In some cases, it ispossible to modify a grammar to make it unambiguous. For example, the grammarG2canbe modified as ({E, T, F,+, ,(,),a},{+, ,(,),a},P,E), wherePis the set of rulesE E+T,E T,T T F,T F,F (E),F 3. Context-Free GRAMMARS AND LANGUAGESWe leave as an exercise to show thatL(G3)=L(G2), and that every string inL(G3)hasa unique leftmost derivation. Unfortunately, it is not always possible to modify a Context-Free grammar to make it unambiguous. There exist Context-Free Languages that have nounambiguous Context-Free grammars. For example, the languageL3={ambmcn|m, n 1} {ambncn|m, n 1}is Context-Free , since it is generated by the following Context-Free grammar:S S1,S S2,S1 XC,S2 AY,X aXb,X ab,Y bY c,Y bc,A aA,A a,C cC,C , it can be shown thatL3has no unambiguous grammars. All this motivates thefollowing Context-Free grammarG=(V, ,P,S)isambiguousif there is somestringw L(G) that has two distinct leftmost derivations (or two distinct rightmost deriva-tions).

10 Thus, a grammarGisunambiguousif every stringw L(G) has a unique leftmostderivation (or a unique rightmost derivation). A Context-Free languageLisinherently am-biguousif every CFGGforLis or not a grammar is ambiguous affects the complexity of parsing. Parsing algo-rithms for unambiguous grammars are more efficient than parsing algorithms for now consider various normal forms for Context-Free Normal Forms for Context-Free Grammars, Chom-sky Normal FormOne of the main goals of this section is to show that every CFGG canbeconvertedtoanequivalent grammar inChomsky Normal Form (for short, CNF). A Context-Free NORMAL FORMS FOR Context-Free GRAMMARS41G=(V, ,P,S) is in Chomsky Normal Form iff its productions are of the formA BC,A a,orS ,whereA, B, C N,a ,S is inPiff L(G), andSdoes not occur on theright-hand side of any that a grammar in Chomsky Normal Form does not have -rules, , rules of theformA , except when L(G), in which caseS is the only -rule. It also does nothavechain rules, , rules of the formA B,whereA, B N.