# Context-Free Language

A context-free grammar is a four-tuple $G=⟨V,∑,P,S⟩$ where:

- $V$ is a finite set of non-terminal symbols
- $∑$ is a finite set of terminal symbols (the alphabet)
- $P$ is a finite set of productions, also called rules
- $S∈V$ is the start non-terminal

Each production in $P$ is of the form $A→α$, where $A∈V$ is a non-terminal symbol and $α$ is a sequence of terminal and non-terminal symbols.

The language generated by the grammar $G=⟨V,∑,P,S⟩$ is $L(G)={w∈∑_{∗}∣S⇒∗w}$

A language is context-free if there exists a context-free grammar that generates it. There may be multiple grammars that generate the same language.

### Convention for CS241E

So much notation, it’s actually so confusing.

- In the rest of this module, we will use the convention that:
- variables $a,b,c$, and $d$ always refer to terminal symbols in $∑$
- variables $A,B,C,D,$ and $S$ always refer to non-terminal symbols in $V$
- variables $W,X,Y$, and $Z$ always refer to terminal or non-terminal symbols in $∑∪V$
- variables $w,x,y$, and $z$ always refer to sequences of terminal symbols from $∑$, i.e. to words, and
- variables $α,β,γ$, and $δ$ always refer to sequences of terminal or non-terminal symbols from $∑∪V$

### Related

After we do this Parsing, we move up by doing Parsing, we move up by doing Context-Sensitive Analysis, since a valid Lacs program is not only context free, but context-sensitive, because we need to make sure about type checking and name resolution.