RIPAL: Responsive and Intuitive Parsing for the Analysis of Language

Background

You've seen the fundamental concepts needed to parse strings with an LR(0) parser. However, these concepts are far less intuitive than the concepts used in an LL(1) parser.

In this section, we will illustrate the application of these concepts in a simple parser.

Setup

Example

Observe the following grammar:

S → a

This grammar has the following augmented grammar:

S' → S $
S → a

It has the following LR(0) parse table:

	a	$	S	S'
state₁	shift₂		goto₃
state₂	reduce₂	reduce₂
state₃		accept

Note

In the table above, we used some abbreviated notation for convenience as follows:

shift_{state_i} is abbreviated as shift_i
reduce_{p_i} is abbreviated as reduce_i
goto_{state_i} is abbreviated as goto_i

Note

We will not yet illustrate the exact algorithm for constructing this parse table. It will be easier to explain after you completely understand the parsing procedure.

Parse example

Example

Parsing input string a:

Input queue	Parse stack	Action
a	1	Apply action of shift₂ which corresponds to state₁ and a in our parse table
	1 a 2	Apply action of reduce₂ which corresponds to state₂ and $ in our parse table
	1 S	Apply action of goto₃ which corresponds to state₁ and S in our parse table
	1 S 3	Accept, since this action corresponds to state₃ and $ in our parse table

This parsing procedure corresponds to the following derivation of string a:

S → a

As an interesting observation, note that we could have simply accepted the input string once the start symbol S was on the stack with lookahead $.

However, the goto action is useful in the use of more complex grammars, which will be illustrated later.

Note

Note that we are using the number i to represent state_i in our parse stack representation for convenience.

Example

Failing to parse input string aa:

Input queue	Parse stack	Action
aa	1	Apply action of shift₂ which corresponds to state₁ and a in our parse table
a	1 a 2	Apply action of reduce₂ which corresponds to state₂ and a in our parse table
a	1 S	Apply action of goto ₃ which corresponds to state₁ and S in our parse table
a	1 S 3	Reject, since no action corresponds to state₃ and a in our parse table

Conclusion

We've now seen LR(0) parse table actions in action. Next, we will examine the parsing procedure for a grammar with multiple terminals.

RIPAL: Responsive and Intuitive Parsing for the Analysis of Language

Pages

LR(0) parse example - single terminal

Background

Setup

Parse example

Conclusion