compiler lexical analysis follow first nullity regex to DFA parser arithmetic expressions Derivation context free grammar ambiguous grammar left derivation right derivation Non-ambiguous grammar bottom-up parsing LR parsing (Knuth, 1965) LR table Construction of the automation and the table NULL FIRST FOLLOW

compiler

lexical analysis

follow

follow(c,∅)=∅follow(c,ϵ)=∅follow(c,a)=∅follow(c,r1r2)={follow(c,r1)∪follow(c,r2)∪first(r2)if c∈last(r1)follow(c,r1)∪follow(c,r2)otherwisefollow(c,r1∣r2)=follow(c,r1)∪follow(c,r2)follow(c,r∗)={follow(c,r)∪first(r)if c∈last(r)follow(c,r)otherwise\begin{align*} \text{follow}(c, \emptyset) &= \emptyset \\ \text{follow}(c, \epsilon) &= \emptyset \\ \text{follow}(c, a) &= \emptyset \\ \text{follow}(c, r_1 r_2) &= \begin{cases} \text{follow}(c, r_1) \cup \text{follow}(c, r_2) \cup \text{first}(r_2) & \text{if } c \in \text{last}(r_1) \\ \text{follow}(c, r_1) \cup \text{follow}(c, r_2) & \text{otherwise} \end{cases} \\ \text{follow}(c, r_1 \mid r_2) &= \text{follow}(c, r_1) \cup \text{follow}(c, r_2) \\ \text{follow}(c, r*) &= \begin{cases} \text{follow}(c, r) \cup \text{first}(r) & \text{if } c \in \text{last}(r) \\ \text{follow}(c, r) & \text{otherwise} \end{cases} \end{align*}

first

first(∅)=∅first(ϵ)=∅first(a)={a}first(r1r2)={first(r1)∪first(r2)if null(r1)first(r1)otherwisefirst(r1∣r2)=first(r1)∪first(r2)first(r∗)=first(r)\begin{align*} \text{first}(\emptyset) &= \emptyset \\ \text{first}(\epsilon) &= \emptyset \\ \text{first}(a) &= \{a\} \\ \text{first}(r_1 r_2) &= \begin{cases} \text{first}(r_1) \cup \text{first}(r_2) & \text{if } \text{null}(r_1) \\ \text{first}(r_1) & \text{otherwise} \end{cases} \\ \text{first}(r_1 \mid r_2) &= \text{first}(r_1) \cup \text{first}(r_2) \\ \text{first}(r^*) &= \text{first}(r) \end{align*}

nullity

null(∅)=falsenull(ϵ)=truenull(a)=falsenull(r1r2)=null(r1)∧null(r2)null(r1∣r2)=null(r1)∨null(r2)null(r∗)=true\begin{align*} \text{null}(\emptyset) &= \text{false} \\ \text{null}(\epsilon) &= \text{true} \\ \text{null}(a) &= \text{false} \\ \text{null}(r_1 r_2) &= \text{null}(r_1) \land \text{null}(r_2) \\ \text{null}(r_1 \mid r_2) &= \text{null}(r_1) \lor \text{null}(r_2) \\ \text{null}(r^*) &= \text{true} \end{align*}

regex to DFA

parser

arithmetic expressions

N= is finite set of non-terminal symbolsT= is finite set of terminal symbolsS∈N= is the start symbol (the axiom)R⊆N×(N∪T)= is a finite set of production rules\begin{align*} N &= \text{ is finite set of non-terminal symbols}\\ T &= \text{ is finite set of terminal symbols}\\ S \in N & =\text{ is the start symbol (the axiom)}\\ R \subseteq N \times (N \cup T) &= \text{ is a finite set of production rules}\\ \end{align*}\\

example

N={E}T={+,∗,(,),int}S=ER={(E,E+E),(E,E∗E),(E,(E)),(E,int)}\begin{align*} N&=\{E\}\\ T&=\{+,*,(,),int\}\\ S&=E\\ R&=\{(E,E+E), (E,E*E), (E,(E)), (E,int) \}\\ \end{align*}\\

look like this

E→E+E ∣ E∗E ∣ (E) ∣ int\begin{align*} E \rightarrow & E+E \\ \ | \ & E*E \\ \ | \ &(E) \\ \ | \ & int \\ \end{align*}\\

Derivation

u∈{(N∪T)∗}v∈{(N∪T)∗}X∈Nβ∈R\begin{align*} u&\in \{(N\cup T)^* \}\\ v&\in \{(N\cup T)^* \}\\ X&\in N\\ \beta &\in R \\ \end{align*}\\ u=u1Xu2v=u1βu2\begin{align*} u&=u_1 X u_2\\ v&=u_1 \beta u_2\\ \end{align*}\\ E∗( ⏟u1E⏟X )⏟u2→E∗(E+E⏟β)\begin{align*} &\underbrace{E* ( \ }_{u_1} &&\underbrace{E}_{X} &\underbrace{ \ )}_{u_2} &\rightarrow E*( && \underbrace{ E+E }_{\beta} &&) \end{align*}\\

context free grammar

The language defined by a context-free grammar G=(N,T,S,R)G = (N, T , S, R)

int∗(int+int)∈L(G)\text{int} * ( \text{int} + \text{int} ) ∈ L(G)

ambiguous grammar

give int + int * int

left derivation
E→E+E→int+E→int+E∗E→int+int∗E→int+int∗int\begin{align*} E & \rightarrow E+E\\ & \rightarrow \text{int}+E\\ & \rightarrow \text{int}+E*E\\ & \rightarrow \text{int}+\text{int}*E\\ & \rightarrow \text{int}+\text{int}*\text{int}\\ \end{align*}\\
right derivation
E→E+E→E+E∗E→E+E∗int→E+int∗int→int+int∗int\begin{align*} E & \rightarrow E+E\\ & \rightarrow E + E * E\\ & \rightarrow E + E * \text{int}\\ & \rightarrow E + \text{int} * \text{int}\\ & \rightarrow \text{int} + \text{int} * \text{int}\\ \end{align*}\\

Non-ambiguous grammar

E→E+T→tT→T∗F→FF→(E)→int\begin{align*} E & \rightarrow E + T \\ & \rightarrow t\\ T & \rightarrow T * F \\ & \rightarrow F\\ F & \rightarrow (E) \\ & \rightarrow \text{int}\\ \end{align*}\\

give int + int * int * int

E→E+T→T+T→F+T→int+T→int+T∗F→int+T∗F∗F→int+T∗F∗F∗F→int+int∗F∗F∗F→int+int∗int∗F∗F→int+int∗int∗int∗F→int+int∗int∗int∗int\begin{align*} E & \rightarrow E + T\\ & \rightarrow T + T \\ & \rightarrow F + T \\ & \rightarrow \text{int} + T \\ & \rightarrow \text{int} + T * F \\ & \rightarrow \text{int} + T * F * F \\ & \rightarrow \text{int} + T * F * F * F \\ & \rightarrow \text{int} + \text{int} * F * F * F \\ & \rightarrow \text{int} + \text{int} * \text{int} * F * F \\ & \rightarrow \text{int} + \text{int} * \text{int} * \text{int} * F \\ & \rightarrow \text{int} + \text{int} * \text{int} * \text{int} * \text{int} \\ \end{align*}\\

bottom-up parsing

  • scan the input from left to right
  • look for right-hand sides of production rules to build the derivation tree from bottom to top

LR parsing (Knuth, 1965)

Using an automaton and considering the first k tokens of the input; this is called LR(k) analysis (LR means “Left to right scanning, Rightmost derivation”)

LR table

example

Construction of the automation and the table

NULL

Let α∈(N∪T)∗\alpha \in (N \cup T)^*.

NULL(α)\text{NULL}(\alpha) holds if and only if we can derive ϵ\epsilon from α\alpha, i.e., α⇒∗ϵ\alpha \Rightarrow^* \epsilon

FIRST

Let α∈(N∪T)∗\alpha \in (N \cup T)^*.

FIRST(α)\text{FIRST}(\alpha) is the set of all terminals starting words derived from α\alpha, i.e., {a∈T∣∃w.α⇒∗aw}\{a \in T \mid \exists w . \alpha \Rightarrow^* aw \}

FOLLOW

Let X∈NX \in N.

FOLLOW(X)\text{FOLLOW}(X) is the set of all terminals that may appear after XX in a derivation, i.e., {a∈T∣∃u,w.S⇒∗uXaw}\{a \in T \mid \exists u, w . S \Rightarrow^* uXaw \}