Context-Free Language

What?

It’s a type of Language with specific types of rules.

Contains:

A grammar $G=(S,N,T,P)$ where:

• Start symbol $S$: ( Exp in this case - $S\in N$ ) and
• Non-terminals $N$: ( Exp, Var, Num - $N$ ) ,
• Terminals $T$: (+, -, 0…9, (, ), x, etc - $\Sigma$),
• Rules / Productions $P$: ($P$ of the form $X\to \alpha$, where $X\in N$, $\alpha \in (\Sigma \cup N{)}^{\ast }$).
• Rules example:

   Exp → Exp + Exp
   Exp → Exp * Exp
   Exp → Var | Num | ( Exp )
   Var → x | y | z
   Num → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

• Example legal sentence tree (aka syntax tree, Parse Tree) of above:
  
• An Abstract Syntax Tree would be a more concise, high entropy version of that tree.

How do you build a tree from a sentence?

I’m glad you asked. Cue the CYK Algorithm!

Writing Languages Concisely (corresponds with Regex):

• x*: zero or more occurrences of x
• x+: one or more occurrences of x
• [x]: zero or one occurrence of x

We can rewrite RE as CFG with:

• Rewrite any occurrences of x*, x+ or [x] with $x_{\text{rep}}$, and add the following rules.
• x* → $x_{\text{rep}}=x{x}_{\text{rep}}|ϵ$
• x+ → $x_{\text{rep}}=x{x}_{\text{rep}}|x$
• [x] → $x_{\text{opt}}=x|ϵ$

Left Parsable Grammars:

Take a language with terms like:

• term_1 | ... | term_n
• fact_1, | ...| fact_n
• [exp], exp*

Left Parsable Grammars are ones where the terms do not share initial symbols. This makes life tremendously easier later one, cos we only need to (and now can) lookahead a single character in the parsing.