Simple LR parser: Difference between revisions

Revision as of 00:28, 4 July 2014

Revision as of 11:40, 5 July 2014

Line 43:

The action and goto tables:

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

<tr|- align="center">

<td| || colspan="2"> |''action''</td>||''goto''

<td></td>

<tr|- align="center">

<td colspan="2">''action''</td>

| ''state''||'''1'''||'''$'''||'''E'''

<td>''goto''</td>

<tr|- align="center">

</tr>

| '''0'''||s1||||2

<tr align="center">

<tr|- align="center">

<td>''state''</td>

<td>| '''1'''<||s1/td>r2||r2||3

<tr|- align="center">

<td>'''$'''</td>

<td>| '''E2'''</td>||||acc||

<tr|- align="center">

</tr>

| '''3'''||r1||r1||

<tr align="center">

|}

<td>'''0'''</td>

<td>s1</td>

<td></td>

<td>2</td>

</tr>

<tr align="center">

<td>'''1'''</td>

<td>s1/r2</td>

<td>r2</td>

<td>3</td>

</tr>

<tr align="center">

<td>'''2'''</td>

<td></td>

<td>acc</td>

<td></td>

</tr>

<tr align="center">

<td>'''3'''</td>

<td>r1</td>

<td>r1</td>

<td></td>

</tr>

</table>

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(0) 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:

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

<tr|- align="center">

<td>| symbol</td>||S||E||1

<tr|- align="center">

<td>S</td>

| following||$||$||1,$

<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;

return (action in followSet(ruleSymbol))

}

Line 110 ⟶ 79:

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

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

<tr|- align="center">

<td| || colspan="2"> |''action''</td>||''goto''

<td></td>

<tr|- align="center">

<td colspan="2">''action''</td>

| ''state''||'''1'''||'''$'''||'''E'''

<td>''goto''</td>

<tr|- align="center">

</tr>

| '''0'''||s1||||2

<tr align="center">

<tr|- align="center">

<td>''state''</td>

<td>| '''1'''</td>||s1||r2||3

<tr|- align="center">

<td>'''$'''</td>

<td>| '''E2'''</td>||||acc||

<tr|- align="center">

</tr>

| '''3'''||||r1||

<tr align="center">

|}

<td>'''0'''</td>

<td>s1</td>

<td></td>

<td>2</td>

</tr>

<tr align="center">

<td>'''1'''</td>

<td>s1</td>

<td>r2</td>

<td>3</td>

</tr>

<tr align="center">

<td>'''2'''</td>

<td></td>

<td>acc</td>

<td></td>

</tr>

<tr align="center">

<td>'''3'''</td>

<td></td>

<td>r1</td>

<td></td>

</tr>

</table>

==See also==