7. Context Free Languages

Jan 27, 2022

• context free languages is a more general class of languages:

  • contains all regular languages (strict subset), and others

  • e.g. $L=\{a^n{b}^n:n\ge 0\}$ and $L=\{w{w}^R\}$ are context free but not regular

• can be described with context free grammars or pushdown automata

• primarily interesting for parsers

---

A language $L$ is context free is there is a context free grammar $G$ with $L=L(G)$

---

Grammars

• grammars express languages using (a list of) production rules

• productions replace variables with other variables or terminals

• example: grammar for $L=\{a^n{b}^n:n\ge 0\}$

  • $S\to aSb$ | $ϵ$

• example: even length palindromes $L(G)=\{w{w}^R:w\in \{a,b{\}}^{\ast }\}$

  • $S\to aSb$ | $SS$ | $ϵ$

• odd length palindromes (different language)

  • $S\to aSb$ | $SS$ | $a$ | $b$ | $ϵ$

• notation hiding intermediate derivation steps $w_1\stackrel{\mathit{\ast }}{\to }{w}_n$

  • $\stackrel{\mathit{\ast }}{\to }$ means in zero or more derivation steps

  • trivially $w\stackrel{\mathit{\ast }}{\to }w$

Formal definition

Grammar $G=(V,T,S,P)$ where

• $V$ is s set of variables

• $T$ is a set of terminal symbols

• $S$ is a start variable ($S\in V$)

• $P$ is a set of productions

  • all in form $A\to s$ where $s$ is string of variables and terminals

Language of grammar $G$ with start variable $S$

• $L(G)=\{w:S\stackrel{\mathit{\ast }}{\to }w,w\in T^{\ast }\}$

• $w$ is string of terminals of $ϵ$

Derivation order and derivation trees

Example

Consider the grammar with 5 productions, and derivation of string $aab$:

$S\to AB$
$A\to aaA$ | $ϵ$
$B\to Bb$ | $ϵ$

Leftmost derivation:

$S\to AB\to aaAB\to aaB\to aaBb\to aab$

Rightmost derivation:

$S\to AB\to ABb\to Ab\to aaAb\to aab$

Sometimes derivation order does not matter, both give the same derivation tree:

(Take the leaf nodes to get $aab$)

         S
     ⭩      ⭨
   A          B
 ⭩ 🠧 ⭨      ⭩  ⭨
a  a  A     B     b
      🠧     🠧
      ε     ε

Ambiguity

• a context free grammar $G$ is ambiguous is there is a string $w\in L(G)$ which has two different derivation trees or two leftmost derivations

• ambiguity may cause problems in applications using derivation trees e.g. evaluating expressions; in general compilers

• Two ways to handle ambiguity:

  • (1) write non-ambiguous grammar (difficult)

  • (2) add rules to the parser to handle priority (practical solution)

• It is not possible to write all grammars as non-ambiguous

  • e.g. $L=\{a^n{b}^n{c}^m\}\cup \{a^n{b}^m{c}^m\},n,m\ge 0$ is inherently ambiguous
    the string $a^n{b}^n{c}^n\in L$ always has two different derivation trees for any grammar

Example

$E\to E+E$ | $E\ast E$ | $(E)$ | $a$

(A) leftmost derivation of $a+a\ast a$:

$E\to E+E\to a+E\to a+E\ast E\to a+a\ast E\to a+a\ast a$

         E
    ⭩    🠧   ⭨
   E     +      E
   🠧         ⭩  🠧  ⭨
   a        E   *    E
            🠧        🠧 
            a        a

(B) another leftmost derivation of $a+a\ast a$:

$E\to E\ast E\to E+E\ast E\to a+E\ast E\to a+a\ast E\to a+a\ast a$

             E
        ⭩    🠧   ⭨
       E     *     E
   ⭩  🠧  ⭨        🠧
   E   +   E       a
   🠧       🠧 
   a       a

Bottom up evaluation for a=2: (A) gives correct result 2+2*2=6 but (B) does not 2+2*2=8.

This grammar is ambiguous because there are two different leftmost derivations.