File: Parser.txt
Author: Keith Schwarz (htiek@cs.stanford.edu)

An informal description of the LR(1) parser used to parse
regular expressions.  The grammar is defined as follows:

R' -> R   (Mandated by LR(1) construction)
R -> S    (0)
R -> SR   (1)
S -> T    (2)
S -> T|S  (3)
T -> U    (4)
T -> U*   (5)
U -> c    (6)
U -> (R)  (7)

The parser states, follow sets, and transitions are defined
below:

I0
	R'-> .R		$        	1
	R -> .S		$        	2
	R -> .SR	$        	2
	S -> .T		$ c (    	4
	S -> .T|S	$ c (    	4
	T -> .U		$ c ( |  	5
	T -> .U*	$ c ( |  	5
	U -> .c		$ c ( | *	6
	U -> .(R)	$ c ( | *	7

I1
	R'-> R.		$               ACCEPT

I2	R -> S.		$        	Reduce
	R -> S.R	$        	3
	R -> .S		$        	2
	R -> .SR	$        	2
	S -> .T		$ c (    	4
	S -> .T|S	$ c (    	4
	T -> .U		$ c ( |  	5
	T -> .U*	$ c ( |  	5
	U -> .c		$ c ( | *	6
	U -> .(R)	$ c ( | *	7

I3
	R -> SR.	$

I4
	S -> T.		$ c (    	Reduce
	S -> T.|S	$ c (    	8

I5
	T -> U.		$ c ( |  	Reduce
	T -> U.*	$ c ( |  	9

I6
	U -> c.		$ c ( | *	Reduce

I7
	U -> (.R)	$ c ( | *	10
	R -> .S		)        	12
	R -> .SR	)        	12
	S -> .T		) c (    	13
	S -> .T|S	) c (    	13
	T -> .U		) c ( |  	14
	T -> .U*	) c ( |  	14
	U -> .c		) c ( | *	15
	U -> .(R)	) c ( | *	19

I8
	S -> T|.S	$ c (    	16
	S -> .T		$ c (    	4
	S -> .T|S	$ c (    	4
	T -> .U		$ c ( |  	17
	T -> .U*	$ c ( |  	17
	U -> .c		$ c ( | *	6
	U -> .(R)	$ c ( | *	7

I9
	T -> U*.	$ c ( |		Reduce

I10
	U -> (R.)	$ c ( | *	11

I11
	U -> (R).	$ c ( | *	Reduce

I12
	R -> S.		)        	Reduce
	R -> S.R	)        	18
	R -> .S		)        	12
	R -> .SR	)        	12
	S -> .T		) c (    	13
	S -> .T|S	) c (    	13
	T -> .U		) c ( |  	14
	T -> .U*	) c ( |  	14
	U -> .c		) c ( | *	15
	U -> .(R)	) c ( | *	19
I13
	S -> T.		) c (    	Reduce
	S -> T.|S	) c (    	20

I14
	T -> U.		) c ( |  	Reduce
	T -> U.*	) c ( |  	21

I15
	U -> c.		) c ( | *	Reduce

I16
	S -> T|S.	$ c (    	Reduce

I17
	T -> U.		$ c ( |  	Reduce
	T -> U.*	$ c ( |  	9

I18
	R -> SR.	)        	Reduce

I19
	U -> (.R)	) c ( | *	22
	R -> .S		)        	12
	R -> .SR	)        	12
	S -> .T		) c (    	13
	S -> .T|S	) c (    	13
	T -> .U		) c ( |  	14
	T -> .U*	) c ( |  	14
	U -> .c		) c ( | *	15
	U -> .(R)	) c ( | *	19

I20
	S -> T|.S	) c (    	24
	S -> .T		) c (    	13
	S -> .T|S	) c (    	13
	T -> .U		) c ( |  	14
	T -> .U*	) c ( |  	14
	U -> .c		) c ( | *	15
	U -> .(R)	) c ( | *	19

I21
	T -> U*.	) c ( |  	Reduce

I22
	U -> (R.)	) c ( | *	23

I23
	U -> (R).	) c ( | *	Reduce

I24
	S -> T|S.	) c (    	Reduce