Simple LR parser: Difference between revisions

Revision as of 12:23, 24 December 2011

Revision as of 16:46, 8 March 2012

Line 1:

{{context|date=December 2011}}

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 less 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.

The SLR parsing algorithm

Initialize the stack with S

Read input symbol

while (true)

if Action(top(stack), input) = S

NS <- Goto(top(stack),input)

push NS

Read next symbol

else if Action(top(stack), input) = Rk

output k

pop |RHS| of production k from stack

NS <- Goto(top(stack), LHS_k)

push NS

else if Action(top(stack),input) = A

output valid, return d

else

output invalid, return

== Example ==

Line 92 ⟶ 73:

</table>

As can be observed there is a shift-reduce conflict for state 1 and terminal '1'. HoweverThis occurs because, when the followaction settable offor Ean LR parser is {created, $reduce }actions soare theinserted reduceon actionsa r1per-row andbasis. r2However, areby onlyusing valida infollow theset, columnreduce foractions $.can Thebe resultadded iswith thefiner followinggranularity. conflict-lessThe actionfollow andset gotofor tablethis grammar:

<table border="1" align="center">

<tr align="center">

<td>symbol</td>

<td>S</td>

<td>E</td>

<td>1</td>

</tr>

<tr align="center">

<td>following</td>

<td>$</td>

<td>$</td>

<td>1,$</td>

</tr>

</table>

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:

<table border="1" align="center">