RIPAL: Responsive and Intuitive Parsing for the Analysis of Language

Observe the following grammar:

S → A
A → B
B → C
C → c

This grammar has the following augmented grammar:

S' → S $
S → A
A → B
B → C
C → c

Recall that it has the following parse table:

	c	$	S	A	B	C	S'
state1	shift2		goto6	goto5	goto4	goto3
state2	reduce5	reduce5
state3	reduce4	reduce4
state4	reduce3	reduce3
state5	reduce2	reduce2
state6		accept

Recall the following parse of input string c:

Input queue	Parse stack	Action
c	1	Apply action of shift2 which corresponds to state1 and c in our parse table
	1 c 2	Apply action of reduce5 which corresponds to state2 and $ in our parse table
	1 C	Apply action of goto3 which corresponds to state1 and C in our parse table
	1 C 3	Apply action of reduce4 which corresponds to state3 and $ in our parse table
	1 B	Apply action of goto4 which corresponds to state1 and B in our parse table
	1 B 4	Apply action of reduce3 which corresponds to state4 and $ in our parse table
	1 A	Apply action of goto5 which corresponds to state1 and A in our parse table
	1 A 5	Apply action of reduce2 which corresponds to state5 and $ in our parse table
	1 S	Apply action of goto6 which corresponds to state1 and S in our parse table
	1 S 6	Accept, since this action corresponds to state6 and $ in our parse table

Here, observe that for the following productions:

1. S → A
2. A → B
3. B → C

the repeated action of goto followed by reduce can be used to chain the processing of these productions.

However, the production C → c can't be processed in the same way because it requires the processing of an input terminal.

Example

The above augmented grammar has the production:

S → A

Now, consider the parse state we are in before nonterminal A is reduced to nonterminal S. It can be further qualified as follows:

S → · A

In this state, the nonterminal A must now be processed. We have seen in our parse example that this processing consists of a goto action follow by a reduction of nonterminal A to nonterminal S. After this processing, we will be in a state that contains the following qualified production:

S → A ·

In this state, A has been processed.

Example

The above augmented grammar has the production:

C → c

Now, consider the parse state we are in before terminal c is shifted onto the parse stack. It can be further qualified as follows:

C → · c

In this state, the terminal c must now be processed. We have seen in our parse example that this processing consists of a shift action on terminal c. After this processing, we will be in a state that contains the following qualified production:

C → c ·

In this state, c has been processed.

Example

The above augmented grammar has the production:

S' → S $

In our initial parse state, we haven't processed any shift or reduce actions.

In particular, we have not yet processed a reduction of nonterminal S to nonterminal S'. As a result, when in the initial parse state, this initial production can be further qualified as follows:

S' → · S $

Once S has been processed in our parser setup, the production can be qualified as:

S → S · $

Although it's easiest to think of symbol processing as part of a shift or reduce action, this particular example will make more sense once the algorithm for parse table generation is explained.