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.

DFA stateNFA statesTransitions
impbiimporandnotlparrparatomExpAtom
s0A,A1,C,F1,G,K,O,S,Vs5s4s3g2g1
s1*W
s2*B,D,H,L,Ps8s7s9s6
s3*G1
s4A1,B1,C,F1,G,K,O,S,Vs5s4s3g10g1
s5A1,C,F1,G,K,O,S,T,Vs5s4s3g11g1
s6A1,C,F1,G,K,O,Q,S,Vs5s4s3g12g1
s7A1,C,F1,G,I,K,O,S,Vs5s4s3g13g1
s8A1,C,E,F1,G,K,O,S,Vs5s4s3g14g1
s9A1,C,F1,G,K,M,O,S,Vs5s4s3g15g1
s10C1,D,H,L,PC1,D,H,L,Ps8s7s9s6s16
s11*D,H,L,P,Us8s7s9s6
s12*D,H,L,P,Rs8s7s9s6
s13*D,H,J,L,Ps8s7s9s6
s14*D,F,H,L,Ps8s7s9s6
s15*D,H,L,N,Ps8s7s9s6
s16*D1

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)

We add the reduce and accept actions to the table along side a column for the end marker (terminal) $.

DFA stateNFA statesTransitions
impbiimporandnotlparrparatomExpAtom$
s0A,A1,C,F1,G,K,O,S,Vs5s4s3g2g1
s1*Wr6r6r6r6r6r6
s2*B,D,H,L,Ps8s7s9s6accept
s3*G1r8r8r8r8r8r8
s4A1,B1,C,F1,G,K,O,S,Vs5s4s3g10g1
s5A1,C,F1,G,K,O,S,T,Vs5s4s3g11g1
s6A1,C,F1,G,K,O,Q,S,Vs5s4s3g12g1
s7A1,C,F1,G,I,K,O,S,Vs5s4s3g13g1
s8A1,C,E,F1,G,K,O,S,Vs5s4s3g14g1
s9A1,C,F1,G,K,M,O,S,Vs5s4s3g15g1
s10C1,D,H,L,PC1,D,H,L,Ps8s7s9s6s16
s11*D,H,L,P,Us8/r5s7/r5s9/r5s6/r5r5r5
s12*D,H,L,P,Rs8/r4s7/r4s9/r4s6/r4r4r4
s13*D,H,J,L,Ps8/r2s7/r2s9/r2s6/r2r2r2
s14*D,F,H,L,Ps8/r1s7/r1s9/r1s6/r1r1r1
s15*D,H,L,N,Ps8/r3s7/r3s9/r3s6/r3r3r3
s16*D1r7r7r7r7r7r7

Solving Conflicts

In the new table we have what is called conflicts. In the row of state s11 to state s15 four of the terminals have a conflict between shift and reduce. For every conflicting action we choose according to the following. We have a last read input, which we obtain by looking for a terminal in the production the reduce action targets, and we have the next input which is the terminal named in the column. Now

  1. In the case where last and current has same precedence level, we have two situations
    1. The operators are left-associative: we keep reduce.
    2. The operators are right-associative: we keep shift.
  2. In the case we have a + b * c where * binds tighter than +, we keep the shift action.
  3. In the case we have a * b + c where again * binds tighter than +, we keep the reduce action.

In order for this to be of any use we need some formal syntax rules for propositional logic. I found some in the book Logic in Computer Science, Convention 1.3, page 5: ¬ binds tighter than ∧ and ∨ which binds tighter than →. To the implication level we just add ↔. Both implication and biimplication is right associative. The rest for now is left associative. Thus we have p \rightarrow (q \lrarrow r) and ((\not p) \land q) \rightarrow r

With this in mind let us have a look at the conflicts in s11*

We move on to s12* with reduction/preceding production prod(4) = Exp \rightarrow Exp and Exp

For s13* we have the preceding production prod(2) = Exp biimp Exp

For s14* we have the preceding production prod(1) = Exp \rightarrow Exp imp Exp

Lastly for s15* we have the preceding production prod(3) = Exp \rightarrow Exp or Exp

And we can create the final table

DFA stateNFA statesActionsGOTO
impbiimporandnotlparrparatom$ExpAtom
s0A,A1,C,F1,G,K,O,S,Vs5s4s3g2g1
s1*Wr6r6r6r6r6r6
s2*B,D,H,L,Ps8s7s9s6accept
s3*G1r8r8r8r8r8r8
s4A1,B1,C,F1,G,K,O,S,Vs5s4s3g10g1
s5A1,C,F1,G,K,O,S,T,Vs5s4s3g11g1
s6A1,C,F1,G,K,O,Q,S,Vs5s4s3g12g1
s7A1,C,F1,G,I,K,O,S,Vs5s4s3g13g1
s8A1,C,E,F1,G,K,O,S,Vs5s4s3g14g1
s9A1,C,F1,G,K,M,O,S,Vs5s4s3g15g1
s10C1,D,H,L,PC1,D,H,L,Ps8s7s9s6s16
s11*D,H,L,P,Ur5r5r5r5r5r5
s12*D,H,L,P,Rr4r4r4r4r4r4
s13*D,H,J,L,Ps8s7s9s6r2r2
s14*D,F,H,L,Ps8s7s9s6r1r1
s15*D,H,L,N,Pr3r3r3r3r3r3
s16*D1r7r7r7r7r7r7

I have rearranged so that $ is located after atom. And then marked the terminals as Actions and the non-terminals as GOTO.

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

StackInputAction
0p or (q imp r)$shift with 3
0 3or (q imp r)$reduce by 8: Atom -> atom
0 1or (q imp r)$reduce by 6: Exp -> Atom
0 2or (q imp r)$shift with 9
0 2 9(q imp r)$shift with 4
0 2 9 4q imp r)$shift with 3
0 2 9 4 3imp r)$reduce by 8: Atom -> atom
0 2 9 4 1imp r)$reduce by 6: Exp -> Atom
0 2 9 4 10imp r)$shift with 8
0 2 9 4 10 8r)$shift with 3
0 2 9 4 10 8 3)$reduce by 8: Atom -> atom
0 2 9 4 10 8 1)$reduce by 6: Exp -> Atom
0 2 9 4 10 8 14)$reduce by 1: Exp -> Exp imp Exp
0 2 9 4 10)$shift with 16
0 2 9 4 10 16$reduce with 7: Atom -> lpar Exp rpar
0 2 9 1$reduce by 6: Exp -> Exp imp Exp
0 2$accept

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.

Share