An Introduction to Formal Languages and Automata, 7th Edition

17.6 LR(1) PARSING WITH λ-PRODUCTIONS

A λ-production has only one item, as the right-hand side is of length 0. Thus, the λ-production item has the marker (·) at the end of the righthand side and always results in a reduce operation. We can display the rule A → λ as the item A → λ· or as A → · without the λ. Any state in a dfa with this item is a final state.

EXAMPLE 17.9

Given the following context-free grammar G = (V, T, S, P) with V = {S, A} and T = {a, b}, and P shown below, compute FIRST and FOLLOW for variables in the grammar and build the dfa that models the LR(1) parsing process.

$$\begin{array}{l}S\to aA,\hfill \\ A\to bbA,\hfill \\ A\to \lambda .\hfill \end{array}$$

First calculate the FIRST and FOLLOW sets for variables S and A.

	FIRST	FOLLOW
S	a	$
A	b, λ	$

Next, add a new start symbol S