compiler

lexical analysis

follow

$$\begin{array}{rl}\text{follow}(c,\varnothing )& =\varnothing \\ \text{follow}(c,ϵ)& =\varnothing \\ \text{follow}(c,a)& =\varnothing \\ \text{follow}(c,r_1{r}_2)& =\{\begin{array}{ll}\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{array}\\ \text{follow}(c,r_1\mid r_2)& =\text{follow}(c,r_1)\cup \text{follow}(c,r_2)\\ \text{follow}(c,r\ast )& =\{\begin{array}{ll}\text{follow}(c,r)\cup \text{first}(r)& \text{if }c\in \text{last}(r)\\ \text{follow}(c,r)& \text{otherwise}\end{array}\end{array}$$

first

$$\begin{array}{rl}\text{first}(\varnothing )& =\varnothing \\ \text{first}(ϵ)& =\varnothing \\ \text{first}(a)& =\{a\}\\ \text{first}(r_1{r}_2)& =\{\begin{array}{ll}\text{first}(r_1)\cup \text{first}(r_2)& \text{if }\text{null}(r_1)\\ \text{first}(r_1)& \text{otherwise}\end{array}\\ \text{first}(r_1\mid r_2)& =\text{first}(r_1)\cup \text{first}(r_2)\\ \text{first}(r^{\ast })& =\text{first}(r)\end{array}$$

nullity

$$\begin{array}{rl}\text{null}(\varnothing )& =\text{false}\\ \text{null}(ϵ)& =\text{true}\\ \text{null}(a)& =\text{false}\\ \text{null}(r_1{r}_2)& =\text{null}(r_1)\wedge \text{null}(r_2)\\ \text{null}(r_1\mid r_2)& =\text{null}(r_1)\vee \text{null}(r_2)\\ \text{null}(r^{\ast })& =\text{true}\end{array}$$

regex to DFA

parser

arithmetic expressions

$$\begin{array}{rl}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{array}$$

example $$\begin{array}{rl}N& =\{E\}\\ T& =\{+,\ast ,(,),int\}\\ S& =E\\ R& =\{(E,E+E),(E,E\ast E),(E,(E)),(E,int)\}\end{array}$$

look like this

$$\begin{array}{rl}E\to & E+E\\ |& E\ast E\\ |& (E)\\ |& int\end{array}$$

Derivation

$$\begin{array}{rl}u& \in \{(N\cup T{)}^{\ast }\}\\ v& \in \{(N\cup T{)}^{\ast }\}\\ X& \in N\\ \beta & \in R\end{array}$$

$$\begin{array}{rl}u& =u_{1}X{u}_2\\ v& =u_1\beta u_2\end{array}$$

$$\begin{array}{rlrlrlrlrl}& \underset{u_1}{\underbrace{E\ast (}}& & \underset{X}{\underbrace{E}}& \underset{u_2}{\underbrace{)}}& \to E\ast (& & \underset{\beta }{\underbrace{E+E}}& & )\end{array}$$

context free grammar

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

$$\text{int}\ast (\text{int}+\text{int})\in L(G)$$

ambiguous grammar

give int + int * int

left derivation

$$\begin{array}{rl}E& \to E+E\\ & \to \text{int}+E\\ & \to \text{int}+E\ast E\\ & \to \text{int}+\text{int}\ast E\\ & \to \text{int}+\text{int}\ast \text{int}\end{array}$$

right derivation

$$\begin{array}{rl}E& \to E+E\\ & \to E+E\ast E\\ & \to E+E\ast \text{int}\\ & \to E+\text{int}\ast \text{int}\\ & \to \text{int}+\text{int}\ast \text{int}\end{array}$$

Non-ambiguous grammar

$$\begin{array}{rl}E& \to E+T\\ & \to t\\ T& \to T\ast F\\ & \to F\\ F& \to (E)\\ & \to \text{int}\end{array}$$

give int + int * int * int

$$\begin{array}{rl}E& \to E+T\\ & \to T+T\\ & \to F+T\\ & \to \text{int}+T\\ & \to \text{int}+T\ast F\\ & \to \text{int}+T\ast F\ast F\\ & \to \text{int}+T\ast F\ast F\ast F\\ & \to \text{int}+\text{int}\ast F\ast F\ast F\\ & \to \text{int}+\text{int}\ast \text{int}\ast F\ast F\\ & \to \text{int}+\text{int}\ast \text{int}\ast \text{int}\ast F\\ & \to \text{int}+\text{int}\ast \text{int}\ast \text{int}\ast \text{int}\end{array}$$

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 $\alpha \in (N\cup T{)}^{\ast }$.

$\text{NULL}(\alpha )$ holds if and only if we can derive $ϵ$ from $\alpha$, i.e., $\alpha {\Rightarrow }^{\ast }ϵ$

FIRST

Let $\alpha \in (N\cup T{)}^{\ast }$.

$\text{FIRST}(\alpha )$ is the set of all terminals starting words derived from $\alpha$, i.e., $\{a\in T\mid \exists w.\alpha {\Rightarrow }^{\ast }aw\}$

FOLLOW

Let $X\in N$.

$\text{FOLLOW}(X)$ is the set of all terminals that may appear after $X$ in a derivation, i.e., $\{a\in T\mid \exists u,w.S{\Rightarrow }^{\ast }uXaw\}$