# Parsing input (SLR parser)

For this projects I'm going to construct a SLR parser. These differs from LL(1) parsing in that we do not have to rewrite the grammar before we can create the parser. Furthermore we do not have to incorporate precedence and associativity in the grammar. These attributes can be set afterwards.

## Lexing

For the parser we need a set of tokens

imp = "=>" | "->" biimp = "<=>" | "<->" or = "||" | "\/" and = "&&" | "/\" not = "~" lpar = "(" rpar = ")" atom = [a-z] | "T" | "F"

An atom can be a variable or one of the constants T,F. The operators are called connectives. The first four can be expressed in two different ways. This is so as to accommodate the syntax of most programming languages along the syntax of the Coq Proof Assistant

## Grammar

The grammar is as follows. Again we do not need to care about precedence and associativity for now.

Exp \rightarrow Exp imp Exp Exp \rightarrow Exp biimp Exp Exp \rightarrow Exp or Exp Exp \rightarrow Exp and Exp Exp \rightarrow not Exp Exp \rightarrow Atom Atom \rightarrow lpar Exp rpar Atom \rightarrow atom

## SLR parsing

When I started building this parser I skipped all the theory of SLR-parsing and just followed the recipe. I think this might be a good approach. The recipe is

1. Add the production S' \rightarrow S to the grammar. Here S is the start production.
2. Construct a NFA for the right hand side of each production.
3. In the NFA: if a state has an outgoing transition on a non-terminal, add ε-transitions to every production of this non-terminal.
4. Convert the NFA to a DFA.
5. Build a table from the DFA.
6. Calculate Follow on the grammar obtained in (1). Use this Follow-set to add reduce actions to the table obtained in 5.
7. Solve conflicts in the table.

This is the outline. Lets now go into depth.

## NFA and DFA

The inner machinery of a SLR-parser is a parse table, and this table is constructed using a DFA. We construct the DFA by writing an NFA. For this to happen we first add a start production. Furthermore we number the productions:

(0) Exp' \rightarrow Exp (1) Exp \rightarrow Exp imp Exp (2) Exp \rightarrow Exp biimp Exp (3) Exp \rightarrow Exp or Exp (4) Exp \rightarrow Exp and Exp (5) Exp \rightarrow not Exp (6) Exp \rightarrow Atom (7) Atom \rightarrow lpar Exp rpar (8) Atom \rightarrow atom

Then for each production we add transitions based on the right sides as thus (using syntax of nfa2dfa converter):

#Transitions # [0] Exp' -> Exp (A) -Exp>(B) ((B)) # [1] Exp -> Exp imp Exp (C) -Exp>(D) (D) -imp>(E) (E) -Exp>(F) ((F)) # [2] Exp -> Exp biimp Exp (G) -Exp>(H) (H) -biimp>(I) (I) -Exp>(J) ((J)) # [3] Exp -> Exp or Exp (K) -Exp>(L) (L) -or>(M) (M) -Exp>(N) ((N)) # [4] Exp -> Exp and Exp (O) -Exp>(P) (P) -and>(Q) (Q) -Exp>(R) ((R)) # [5] Exp -> not Exp (S) -not>(T) (T) -Exp>(U) ((U)) # [6] Exp -> Atom (V) -Atom>(W) ((W)) # [7] Atom -> lpar Exp rpar (A1) -lpar> (B1) (B1) -Exp>(C1) (C1) -rpar>(D1) ((D1)) # [8] Atom -> atom (F1) -atom>(G1) ((G1))

The alphabet ran empty, so I have started over with the naming. The names are not important. To this we add every transition a state can make to a non-terminal, as an ε-transition. Ex. from (A) we have the transition Exp, so we add an ε-transition to every production of Exp, that is [1],[2],[3],[4],[5],[6]. We get

# [0] Exp' -> Exp start(A) -eps>(C) -eps>(G) -eps>(K) -eps>(O) -eps>(S) -eps>(V) -Exp>(B) ((B)) # [1] Exp -> Exp imp Exp (C) -eps>(G) -eps>(K) -eps>(O) -eps>(S) -eps>(V) -Exp>(D) (D) -imp>(E) (E) -eps>(C) -eps>(G) -eps>(K) -eps>(O) -eps>(S) -eps>(V) -Exp>(F) ((F)) # [2] Exp -> Exp biimp Exp (G) -eps>(C) -eps>(K) -eps>(O) -eps>(S) -eps>(V) -Exp>(H) (H) -biimp>(I) (I) -eps>(C) -eps>(G) -eps>(K) -eps>(O) -eps>(S) -eps>(V) -Exp>(J) ((J)) # [3] Exp -> Exp or Exp (K) -eps>(C) -eps>(G) -eps>(O) -eps>(S) -eps>(V) -Exp>(L) (L) -or>(M) (M) -eps>(C) -eps>(G) -eps>(K) -eps>(O) -eps>(S) -eps>(V) -Exp>(N) ((N)) # [4] Exp -> Exp and Exp (O) -eps>(C) -eps>(G) -eps>(K) -eps>(S) -eps>(V) -Exp>(P) (P) -and>(Q) (Q) -eps>(C) -eps>(G) -eps>(K) -eps>(O) -eps>(S) -eps>(V) -Exp>(R) ((R)) # [4] Exp -> not Exp (S) -not>(T) (T) -eps>(C) -eps>(G) -eps>(K) -eps>(O) -eps>(S) -eps>(V) -Exp>(U) ((U)) # [6] Exp -> Atom (V) -eps>(A1) -eps>(F1) -Atom>(W) ((W)) # [7] Atom -> lpar Exp rpar (A1) -lpar> (B1) (B1) -eps>(C) -eps>(G) -eps>(K) -eps>(O) -eps>(S) -eps>(V) -Exp>(C1) (C1) -rpar>(D1) ((D1)) # [8] Atom -> atom (F1) -atom>(G1) ((G1))

To convert the above epsilon riddled NFA we just use the nfa2dfa converter. We obtain the following

start (s0) = {A,A1,C,F1,G,K,O,S,V} -Atom>(s1) -Exp>(s2) -atom>(s3) -lpar>(s4) -not>(s5) ((s1)) = {W} ((s2)) = {B,D,H,L,P} -and>(s6) -biimp>(s7) -imp>(s8) -or>(s9) ((s3)) = {G1} (s4) = {A1,B1,C,F1,G,K,O,S,V} -Atom>(s1) -Exp>(s10) -atom>(s3) -lpar>(s4) -not>(s5) (s5) = {A1,C,F1,G,K,O,S,T,V} -Atom>(s1) -Exp>(s11) -atom>(s3) -lpar>(s4) -not>(s5) (s6) = {A1,C,F1,G,K,O,Q,S,V} -Atom>(s1) -Exp>(s12) -atom>(s3) -lpar>(s4) -not>(s5) (s7) = {A1,C,F1,G,I,K,O,S,V} -Atom>(s1) -Exp>(s13) -atom>(s3) -lpar>(s4) -not>(s5) (s8) = {A1,C,E,F1,G,K,O,S,V} -Atom>(s1) -Exp>(s14) -atom>(s3) -lpar>(s4) -not>(s5) (s9) = {A1,C,F1,G,K,M,O,S,V} -Atom>(s1) -Exp>(s15) -atom>(s3) -lpar>(s4) -not>(s5) (s10) = {C1,D,H,L,P} -and>(s6) -biimp>(s7) -imp>(s8) -or>(s9) -rpar>(s16) ((s11)) = {D,H,L,P,U} -and>(s6) -biimp>(s7) -imp>(s8) -or>(s9) ((s12)) = {D,H,L,P,R} -and>(s6) -biimp>(s7) -imp>(s8) -or>(s9) ((s13)) = {D,H,J,L,P} -and>(s6) -biimp>(s7) -imp>(s8) -or>(s9) ((s14)) = {D,F,H,L,P} -and>(s6) -biimp>(s7) -imp>(s8) -or>(s9) ((s15)) = {D,H,L,N,P} -and>(s6) -biimp>(s7) -imp>(s8) -or>(s9) ((s16)) = {D1}

## Parsing Table

The above DFA we list as a table (* is for contains accepting). For every transition on a terminal in the above DFA we add the sn (where n is a state number). These are called shift actions. For every non-terminal we add gn (n is again a state number). These are called goto actions. In the obtained table the names of NFA-states are only there to help our understanding. These are of no practical use.

## Reduce

We need the Follow-set of the expanded grammar in order to calculate what is called reduce actions. Let's use grammar2set with the input

prod Exp' -> Exp prod Exp -> Exp "imp" Exp prod Exp -> Exp "biimp" Exp prod Exp -> Exp "or" Exp prod Exp -> Exp "and" Exp prod Exp -> "not" Exp prod Exp -> Atom prod Atom -> "(" Exp ")" prod Atom -> "atom"

For which we obtain

Follow(Exp') = {$} Follow(Exp) = {),and,or,biimp,imp,$} Follow(Atom) = {),and,or,biimp,imp,$} Say we have some production, N \rightarrow \alpha, with production number p. When a DFA state contains an accepting NFA state marked with p, add a reduce p action on alle symbols in Follow(N) in the table. If p = 0, then add an accept action instead. Hence where shift and goto target states, reduce target productions. Here we go accepting(s1) = {W} W.p = 6 prod(6) = Exp \rightarrow Atom Follow(Exp) = {),and,or,biimp,imp,$} (reduce) accepting(s2) = {B} B.p = 0 prod(0) = Exp' \rightarrow Exp Follow(Exp') = {$} (accept) accepting(s3) = {G1} G1.p = 8 prod(9) = Atom \rightarrow atom Follow(Atom) = {),and,or,biimp,imp,$} (reduce) accepting(s11) = {U} U.p = 5 prod(5) = Exp \rightarrow not Exp Follow(Exp) = {),and,or,biimp,imp,$} (reduce) accepting(s12) = {R} R.p = 4 prod(4) = Exp \rightarrow Exp and Exp Follow(Exp) = {),and,or,biimp,imp,$} (reduce) accepting(s13) = {J} J.p = 2 prod(2) = Exp \rightarrow Exp biimp Exp Follow(Exp) = {),and,or,biimp,imp,$} (reduce) accepting(s14) = {F} F.p = 1 prod(1) = Exp \rightarrow Exp imp Exp Follow(Exp) = {),and,or,biimp,imp,$} (reduce) accepting(s15) = {N} N.p = 3 prod(3) = Exp \rightarrow Exp or Exp Follow(Exp) = {),and,or,biimp,imp,$} (reduce) accepting(s16) = {D1} D1.p = 7 prod(7) = Atom \rightarrow lpar Exp rpar Follow(Atom) = {),and,or,biimp,imp,$} (reduce)

## Pseudo Code

For the sake of our understanding we can try to run the parser on some string by hand. The parser works by maintaining a stack. We have for shift, reduce, accept and error the following

1. Shift: Shift/push the next input symbol onto the stack.
2. Reduce: The right end of the string must be located on top of the stack. Locate the left end of the string within the stack and decide with what non-terminal to replace the string. This is done by popping the length of the right hand side of the non-terminal from the stack. Then read the top of the stack, use this read to locate a goto on the non-terminal, and push this on top of stack.
3. Accept: Announce successful completion of the parsing.
4. Error: Happens in any of the blank fields in the table. Decide on some proper error handling.

So lets say we have the input p or (q imp r)\$ - where p,q,r are atom. Initialize the stack with state 0. We write the stack on the right side, the input string in the middle and the chosen action on the right side as follows

The whole algorithm is found in the dragon book. Initialize the stack with state0. In pseudo code we now get:

let a = first symbol of input while (true) let s = top of stack if action[s,a] == shift t: push t onto the stack let a = next input symbol elif action[s,a] == reduce (prod A -> B): pop |B| symbols off the stack let t = top of stack push goto[s,A] onto stack handle production A -> B elif action[s,a] == accept: break else handle error

In practice both t and prod (A -> B) are number/indexes into the table. As are every entry of the GOTO-table. Thus the stack is of type int.