Formal Language

Context-Free Language

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

• $V$ is a finite set of non-terminal symbols
• $\sum$ is a finite set of terminal symbols (the alphabet)
• $P$ is a finite set of productions, also called rules
• $S\in V$ is the start non-terminal

Each production in $P$ is of the form $A\to \alpha$, where $A\in V$ is a non-terminal symbol and $\alpha$ is a sequence of terminal and non-terminal symbols.

The language generated by the grammar $G=⟨V,\sum ,P,S⟩$ is $L(G)=\{w\in {\sum }^{\ast }\mid S\Rightarrow \ast 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 $\sum$
• 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 $\sum \cup V$
• variables $w,x,y$, and $z$ always refer to sequences of terminal symbols from $\sum$, i.e. to words, and
• variables $\alpha ,\beta ,\gamma$, and $\delta$ always refer to sequences of terminal or non-terminal symbols from $\sum \cup 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.