Context-Free LanguagesRegular languages:• keywords in a programminglanguage• names of identifiers• integers• allmiscsymbols: = ;Not Regular languages:• {ancbn|n>0}•expressions - ((a + b) − c)• block structures ({} in C++ andbegin ... end in pascal)1Definition: A grammar G=(V,T,S,P)is context-free if all productions are ofthe formA → xWhere A∈Vandx∈(V∪T)∗.Definition: L is a context-freelanguage (CFL) iff ∃ context-freegrammar (CFG) G s.t. L=L(G).2Example: G=({S},{a,b},S,P)S → aSb | abDerivation of aaabbb:S ⇒ aSb ⇒ aaSbb ⇒ aaabbbL(G) =3Example: G=({S},{a,b},S,P)S → aSa | bSb | a | b | λDerivation of ababa:S ⇒ aSa ⇒ abSba ⇒ ababaΣ={a, b},L(G)=4Example: G=({S,A,B},{a,b,c},S,P)S → AcBA → aAa | λB → Bbb | λL(G) =Derivations of aacbb:1. S ⇒ AcB ⇒ aAacB ⇒ aacB ⇒aacBbb ⇒ aacbb2. S ⇒ AcB⇒ AcBbb ⇒ Acbb ⇒aAacbb ⇒ aacbbNote: Next variable to be replacedis underlined.5Definition: Leftmost derivation - ineach step of a derivation, replace theleftmost variable. (see derivation 1above).Definition: Rightmost derivation - ineach step of a derivation, replace therightmost variable. (see derivation 2above).Derivation Trees (also known as“parse trees”)A derivation tree represents aderivation but does not show theorder productions were applied.6A derivation tree for G=(V,T,S,P):• root is labeled S• leaves labeled x, where x∈T∪{λ}• nonleaf vertices labeled A, A∈V• For rule A→a1a2a3...an,whereA∈V, ai∈(T∪V∪{λ}),a1aa3aA2n7Example: G=({S,A,B},{a,b,c},S,P)S → AcBA → aAa | λB → Bbb | λ8Definitions Partial derivation tree -subtree of derivation tree.If partial derivation tree has root Sthen it represents a sentential form.Leaves from left to right in aderivation tree form the yield of thetree.Yield (w) of derivation tree is suchthat w∈L(G).The yield for the example above is9Example of partial derivation treethat has root S:The yield of this example iswhich is a sententialform.10Example of partial derivation treethat does not have root S:11Membership Given CFG G and stringw∈ Σ∗,isw∈L(G)?If we can find a derivation of w, thenwe would know that w is in L(G).MotivationG is grammar for C++.w is C++ program.Is w syntactically correct?12ExampleG=({S}, {a,b},S,P),P=S→SS | aSa | b | λL1=L(G) =Is abbab ∈ L(G)?13Exhaustive Search AlgorithmFor all i=1,2,3,...Examine all sentential forms yieldedby i substitutionsExample: Is abbab ∈ L(G)?14Theorem If CFG G does not containrules of the formA → λA → Bwhere A,B∈V, then we can determineif w∈ L(G) or if w6∈ L(G).• Proof: Consider1. length of sentential forms2. number of terminal symbols in asentential form15Example: Let L2= L1−{λ}. L2=L(G)where G is:S → SS | aa | aSa | bShow baaba 6∈ L(G).i=11. S ⇒ SS2. S ⇒ aSa3. S ⇒ aa4. S ⇒ bi=21. S ⇒ SS ⇒ SSS2. S ⇒ SS ⇒ aSaS3. S ⇒ SS ⇒ aaS4. S ⇒ SS ⇒ bS5. S ⇒ aSa ⇒ aSSa6. S ⇒ aSa ⇒ aaSaa7. S ⇒ aSa ⇒ aaaa8. S ⇒ aSa ⇒ aba16Definition Simple grammar (ors-grammar) has all productions of theform:A → axwhere A∈V, a∈T, and x∈V∗AND anypair (A,a) can occur in at most onerule.AmbiguityDefinition: A CFG G is ambiguous if∃ some w∈ L(G) which has twodistinct derivation trees.17Example Expression grammarG=({E,I}, {a,b,+,∗,(,)},E,P),P=E→E+E | E∗E | (E) | II → a | bDerivation of a+b∗ais:E⇒E+E ⇒ I+E ⇒ a+E ⇒ a+E∗E ⇒a+I∗E ⇒ a+b∗E ⇒ a+b∗I ⇒ a+b∗aCorresponding derivation tree is:18Another derivation of a+b∗ais:E⇒E∗E⇒E+E∗E ⇒ I+E∗E ⇒a+E∗E ⇒ a+I∗E ⇒ a+b∗E ⇒ a+b∗I ⇒a+b∗aCorresponding derivation tree is:19Rewrite the grammar as anunambiguous grammar. (withmeaning that multiplication hashigher precedence than addition)E → E+T | TT → T∗F | FF → I | (E)I → a | bThere is only one derivation tree fora+b∗c:20Definition If L is CFL and G is anunambiguous CFG s.t. L=L(G), thenL is unambiguous.Backus-Naur Form of a grammar:• Nonterminals are enclosed inbrackets <>• For “→” use instead “::=”Sample C++ Program:main (){int a; int b; int sum;a = 40; b = 6; sum = a + b;cout << "sum is "<< sum << endl;}21“Attempt” to write a CFG for C++in BNF (Note: <program> is startsymbol of grammar.)<program> ::= main () <block><block> ::= { <stmt-list> }<stmt-list> ::= <stmt> | <stmt><stmt-list><decl> | <decl><stmt-list><decl> ::= int <id> ; | double <id> ;<stmt> ::= <asgn-stmt> | <cout-stmt><asgn-stmt>::= <id> = <expr> ;<expr> ::= <expr> + <expr>| <expr> ∗ <expr>| ( <expr> ) | <id><cout-stmt>::= cout <out-list> ;etc., Must expand all nonterminals!22So a derivation of the program testwould look like:<program>⇒ main () <block>⇒ main () { <stmt-list> }⇒ main () { <decl><stmt-list>}⇒ main () { int <id>; <stmt-list>⇒ main () { int a ; <stmt-list> }∗⇒ complete C++ program23More on CFG for C++We can write a CFG G s.t.L(G)={syntactically correct C++programs}.But note that {semantically correctC++ programs}⊂L(G).Can’t recognize redeclared variables:int x;double x;Can’t recognize if formal parametersmatch actual parameters in numberand types:declar: int Sum(int a, int b, int c) ...call: newsum =