Context Free Grammars:

Is a tuple $G = (V_{N}, V_{T}, P, S)$

• $V_{n}$: Set of non terminals
• $V_{T}$: Set of terminals
• $S$: $S \in V_{N}$ Start Symbol
• $P$: $P \subseteq V_{N} \times (V_{N} \cup V_{T})^*$ Are set of rules that map non-terminals to a set of terminals and non-terminals

Reduced and Extended CFGs:

A non terminal $A$ is

• reachable iff: there exists $\varphi_{1}, \varphi_{2}$ such that $S \Longrightarrow \varphi_{1} A \varphi_{2}$
• productive iff: $A \Longrightarrow w \ |\ w \in V_{T}^*$

A grammar is a reduced grammar if it has neither unreachable nor non-productive non-terminals.

A grammar is said to be an extended grammar if we add a non terminal $S'$ and add the production $S' \rightarrow S$.

Derivations:

Expanding a nonterminal according to the productions defined by the grammar is derivation

$\varphi \Longrightarrow \psi$ ($\varphi, \psi \in (V_{N}\times V_{T})^*$ and $\varphi$ derives $\psi$) iff there exists $\varphi_{1}, \varphi_{2} \in (V_{N} \times V_{T})^*$ and $A \in V_{N}$ such that $\varphi = \varphi_{1}A \varphi_{2}$ $A \rightarrow \alpha \in P$ $\psi = \varphi_{1} \alpha \varphi_{2}$

Using this we can write for a Language defined by G

Leftmost and Rightmost derivations:

Given a context free grammar $G = (V_{N}, V_{T}, P, S)$

In left most derivation we derive the left most non-terminal $\varphi \Longrightarrow_{lm} \psi$ ($\varphi, \psi \in (V_{N}\times V_{T})^*$ and $\varphi$ left derives $\psi$) iff there exists $\varphi_{1} \in V_{T}^*$; $\varphi_{2} \in (V_{N} \times V_{T})^*$; and $A \in V_{N}$ such that $\varphi = \varphi_{1}A \varphi_{2}$ $A \rightarrow \alpha \in P$ $\psi = \varphi_{1} \alpha \varphi_{2}$

In right most derivation we derive the right most non-terminal $\varphi \Longrightarrow_{rm} \psi$ ($\varphi, \psi \in (V_{N}\times V_{T})^*$ and $\varphi$ right derives $\psi$) iff there exists $\varphi_{1} \in (V_{N} \times V_{T})^*$; $\varphi_{2} \in V_{T}^*$; ; and $A \in V_{N}$ such that $\varphi = \varphi_{1}A \varphi_{1}$ $A \rightarrow \alpha \in P$ $\psi = \varphi_{1} \alpha \varphi_{2}$

Ambiguous Grammar:

A grammar that has

• two left most derivation for the same string
• two right most derivation for the same string
• two syntax trees for the same string is called ambiguous.

It is undecidable if the grammar is ambiguous.

Pushdown Automata:

A PDA is defined using a tuple $P = (V, Q, \Delta, q_{0}, F)$

• $V$: Input alphabet
• $Q$: Finite set of states (Stack Symbols)
• $q_{0}$: Initial State
• $F$: Set of Final states
• $\Delta$: $\Delta \subseteq (Q^+ \times (V \cup \epsilon)) \times Q^*$ (Reads one input alphabet and pops multiple items from the stack, pushes none or multiple items on the stack)

for $\gamma \in Q^+$, $w \in V^*$, $(\gamma, w)$ is a configuration The binary relation step on configuration is defined by: $(\gamma, aw) \vdash_{P} (\gamma', w)$ if there exists $\gamma_{1}$ such that

• $\gamma = \gamma_{1}\gamma_{2}$
• $\gamma' = \gamma_{1}\gamma_{3}$
• $(\gamma_{2}, a, \gamma_{3}) \in \Delta$

The language accepted by PDA can be then defined as

$L(P) = \{ w \in V^* | \exists q_{f}\in F: (q_{0}, w) \vdash_{M}^* (q_{f}, \epsilon) \}$

Context Free Items and Item pushdown automata:

An item $(A, \alpha, \beta)$ is denoted as $[A \rightarrow \alpha.\beta]$ $[A \rightarrow \alpha.]$ is a complete item

Item Pushdown Automata: Given a CFG $G = (V_{N}, V_{T}, P, S)$ we create its extended version by adding the nonterminal $S'$ and adding a production $S' \rightarrow S$

Then the item pushdown automata can be defined as $P_{G} = (V_{T}, IT_{G}, \delta, [S' \rightarrow .S], \{[S' \rightarrow S.]\})$

TOP DOWN Parser:

Read input from left to right. Construct the syntax tree in a top-down manner sstarting with a node labeled with the start symbol.

Recursive Descent Parsing: Uses $\text{Fifo}$ sets to make expansion deterministic

$\oplus_{k}$: returns the k-length prefix of the concatenation of its operand strings

The $\text{Fifo}$ set for a particular production contains the set of 1-length prefix of the string that they can generate. This allows us to use make deterministic choice as to which production to use while parsing a given string.

In cases where the given production may also generate an empty-string $\epsilon$ we also have to consider which character might follow the string that can be generated by the production, and thus $\text{Follow}_{1}$ is also used.

LL(k) Grammar:

Given a grammar $G = (V_{N}, V_{T}, P, S)$ is an $\text{LL}(k)$ where $k$ is a natural number, iff the following holds

if $k:x = k:y$ then $\beta = \gamma$

In simple terms we dont want two distinct productions for a non-terminal to yield two strings that have a same k-length prefix.

Recursive and LL(K): A non-terminal $A$ is called left recursive if $A \Longrightarrow^+ Aa$ A CFG $G$ is left-recursive if it contains at least one left-recursive non-terminal $G$ is not $\text{LL}(k)$ if it is left-recursive

BOTTOM UP PARSER:

Bottom up parsing by pruning handles:

Handle:

Leftmost set of adjacent leaves forming a complete branch.

Suppose $A \rightarrow \alpha \in P ; \alpha \in (V_{N} \cup V_{T})^*$, then while parsing a string that was generated using the above production, there will come an instance where the AST has the non-terminal $A$ having children $\alpha$. This $\alpha$ is then an handle.

While parsing we will recursively prune handles. This corresponds to a reverse rightmost derivation.

Now we need a way that by successively reading the input we want to identify the handles, which will allow us to do reduction.

For this we create a characteristic FSM of $G$.

Characteristic FSM of $G$:

a characteristic FSM of $G$ is a NFSM $ch(G) = \{Q, V, \Delta, q_{0}, F\}$

• $Q$: $Q = \text{IT}_{G}$ the states of the FSM are the items of the $G$
• $V$: $V = (V_{N} \cup V_{T})$ the alphabet is the set of non-terminals and terminals
• $q_{0}:$ is the initial state and $q_{0} = [S' \rightarrow .S]$
• $F:$ $F$ is a set of complete items. Used to identify handles

To draw the $ch(G)$:

We will first write the extended version of the grammar. Then we write each production in $P$ in item format.

Ex: for a production $S \rightarrow aSb \mid \epsilon$ we will draw the states for this production as

Then we will add epsilon transitions from the item of the form $[X \rightarrow \alpha.Y\beta]$ to all the states of $[Y \rightarrow .\gamma]$

We will then make the NFSM into DFSM by using subset construction. This deterministic version is denoted as $LR_{0}(G) = (Q_{d}, V, \delta_{d}, q_{0}, F_{d})$

When we do subset construction some of the items will be merged into a single state.

Building the LR(0) Pushdown Automaton:

$LR_{0}(G)$ interpreted as a PDA $P_{0}(G) = (\Gamma, V_{T}, \Delta, q_{0}, \{q_{f}\})$

• $\Gamma$: Stack Alphabet $\Gamma = Q_{d}$
• $V_{T}$: Input Alphabet
• $q_{0}$: $[S' \rightarrow .S]$ the start state of $LR_{0}(G)$
• $q_{f}$: ${[S’ \rightarrow S.]}$ the final state of $LR_{0}(G)$
• $\Delta$: $\Delta \subseteq \Gamma^* \times (V_{T} \cup \{\epsilon\}) \times \Gamma^*$

shift:

$(q, a, q\delta_{d}(q, a)) \in \Delta$ if $\delta_{d}(q, a)$ is defined Consume the input $a$ and push the successor state of $q$ under $a$.

reduce:

$(q, q_{1}\cdots q_{n}, \epsilon, q, \delta_{d}(q, X)) \in \Delta$, if $[X \rightarrow \alpha.]$ at top of the stack. $|\alpha| = n$ We pop $|\alpha|$ elements from the stack and push the new stack under $X$ onto the stack.

Non determinism in $P_{0}(G)$:

States with shift-reduce conflict:

Have atleast one read item $[X \rightarrow \alpha.a\beta]$ and one complete item $[Y \rightarrow \gamma.]$

States with reduce-reduce conflict:

Have atleast two complete items $[X \rightarrow .\alpha], [Y \rightarrow .\beta]$

A state with conflicts is inadequate.

Adding Lookahead:

a $\text{LR}_{0}$ item is $[X \rightarrow \alpha.\beta]$, a $\text{LR}_{k}$ item is $[X \rightarrow \alpha.\beta, L]$, the $L$ here is the lookahead set.

LR Parser:

Take their decision to shift or reduce by consulting:

1. Top of the stack
2. Lookahead

These are used as an input for the Action table and the appropriate action is given by $\text{Action}[\gamma, L]$

A goto table records the transition function of a characteristic automaton $\delta_{d}(G)$.