Parsing input (SLR parser)

• Preface
• Parsing input (SLR parser)
• Parser F# code
• Well-formed syntax
• Semantics of propositional logic
• Constructing tables
• The application

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

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.

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:

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

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

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

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

For which we obtain

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

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

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*

• Under imp we look up the accepting state (U) in prod(5) = Exp \rightarrow not Exp. Hence we see a not before the imp. This is a matter of precedence, we want it to be parsed as (not p) imp q. We are in case 3, we keep the reduce.
• Under biimp we have the same situation as above. We keep reduce.
• Under or we have the same situation as above. We keep reduce.
• Under and we have the same situation. We keep reduce.

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

• Under imp we have that the preceding and binds tighter: (p and q) imp r. Thus we are in case 3. We keep reduce.
• Under biimp we have as above. We keep reduce.
• Under or we have the situation where the two binds with same strength, and that the operators are left associative: (p and q) or r. We are in case 1.1, and we keep reduce.
• Under and: same as above. We keep reduce.

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

• Under imp we have same binding strength, but right associativity, we are in case 1.2, we keep shift.
• Under biimp we have as above. We keep shift.
• Under or: we have p biimp (q or r) - or binds tighter, so we keep shift.
• Under and we have the same as above. We keep shift.

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

• Under imp we have the same binding strength and a right associative operator. We are in case 1.2, we keep shift.
• Under biimp we have as above. We keep shift.
• Under or we have p imp (q or r), thus we keep shift.
• Under and we have as above. We keep shift.

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

• Under imp we have (p or q) imp r. Case 3, we keep reduction.
• Under biimp we have as above. We keep reduction
• Under or we have the same tightness with a left associative operator (p or q) or r. We keep reduce.
• Under and we have as above. We keep reduce.

And we can create the final table

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

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

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.