Notes:Parsing

$\newcommand{\first}[1]{\text{First}(#1)}\newcommand{\nullable}[1]{\text{Nullable}(#1)} \newcommand{\follow}[1]{\text{Follow}(#1)}$

Algorithms

These algorithms apply to CFGs:

• $\alpha,\beta,\gamma,\ldots$ denote sequences (possibly empty) of terminals and nonTerminals Caution:Done from memory, still to do, check this
  • EXCEPT: $\varepsilon$ - which means "the empty string"
• $\text{a},\text{b},\text{c}$ terminal symbols Caution:Check
• $a,b,c$ terminal or non terminal symbols Caution:Check

$\text{Nullable}$

Definition of $\nullable{\alpha}$ (a predicate):

• $\nullable{\alpha}\iff[\alpha\dot\implies\varepsilon]$

The algorithm for $\text{Nullable}$ is defined by structural induction:

1. $\nullable{\varepsilon}=\text{true}$
2. $\nullable{a\text{a} }=\text{false}$
3. $\nullable{\alpha\beta}=\nullable{\alpha}\wedge\nullable{\beta}$
4. $\nullable{N}=\nullable{\alpha_1}\vee\cdots\vee\nullable{\alpha_n}$
   • Where $N$ consists of $n$ productions, $N\rightarrow \alpha_1$ to $N\rightarrow\alpha_n$

$\text{First}$

Definition of $\text{First}(\alpha)$ (a set):

• $c\in\first{\alpha}\iff\exists\beta\ \text{(possibly empty)}[\alpha\dot\implies c\beta]$

The algorithm for $\text{First}$ is also defined by structural induction:

1. $\first{\varepsilon}$ $=$ $\emptyset$
2. $\first{\text{a} }=\{\text{a}\}$
3. $\first{\alpha\beta}=\left\{\begin{array}{lr}\first{\alpha}\cup\first{\beta}&\text{if }\nullable{\alpha}\\ \first{\alpha} & \text{if not }\nullable{\alpha} \end{array}\right.$
4. $\first{N}=\first{\alpha_1}\cup\cdots\cup\first{\alpha_n}$
   • Where $N$ has $n$ productions, $N\rightarrow\alpha_1$ to $N\rightarrow\alpha_n$

$\text{Follow}$

Definition of $\follow{N}$ (a set (of terminals)):

• $\text{a}\in\follow{\alpha}\iff\exists$ (a derivation from the start symbol, $S$, such that $S\dot\implies\alpha N\text{a}\beta$ for $\alpha,\beta$ (possibly empty) sequences of grammar symbols)

Note that unlike the others given this is not a property directly from the argument, but a property based on all productions that use $N$ (directly or not)

Algorithm to come.