Simple LR parser

In computer science, a simple LR or SLR parser is an LR parser which uses a follow set to remove conflicts from its action table. It has fewer conflict states than an LR(0) Parser, but will typically have more conflict states than an LALR parser. For real-world computer languages, an SLR parser is usually not adequate, but for student projects in a compiler class it is a good learning tool.

A grammar that has no conflicts reported by an SLR parser generator is an SLR grammar.

Algorithm

The parsing algorithm for an SLR parser is the same as for an LR parser; the only difference between the two is how their action tables are constructed.

Example

A grammar that can be parsed by an SLR parser but not by an LR(0) parser is the following:

(0) S → E

(1) E → 1 E

(2) E → 1

Constructing the action and goto table as is done for LR(0) parsers would give the following item sets and tables:

Item set 0

S → • E

+ E → • 1 E

+ E → • 1

Item set 1

E → 1 • E

E → 1 •

+ E → • 1 E

+ E → • 1

Item set 2

S → E •

Item set 3

E → 1 E •

The action and goto tables:

	action		goto
state	1	$	E
0	s1		2
1	s1/r2	r2	3
2		acc
3	r1	r1

As can be observed there is a shift-reduce conflict for state 1 and terminal '1'. This occurs because, when the action table for an LR parser is created, reduce actions are inserted on a per-row basis. However, by using a follow set, reduce actions can be added with finer granularity. The follow set for this grammar:

symbol	S	E	1
following	$	$	1,$

A reduce only needs to be added to a particular action column if that action is in the follow set associated with that reduce. This algorithm describes whether a reduce action must be added to an action column:

function mustBeAdded(reduceAction, action){
	ruleNumber = reduceAction.value;
	ruleSymbol = rules[ruleNumber].leftHandSide;
	if (action in followSet(ruleSymbol)){
		return true;
	}
	else{
		return false;
	}
}

for example, mustBeAdded(r2, "1") is false, because the left hand side of rule 2 is "E", and 1 is not in E's follow set. Contrariwise, mustBeAdded(r2, "$") is true, because "$" is in E's follow set.

By using mustBeAdded on each reduce action in the action table, the result is a conflict-free action table:

	action		goto
state	1	$	E
0	s1		2
1	s1	r2	3
2		acc
3		r1

Algorithm

Example

See also