Simple LR parser: Difference between revisions

Revision as of 04:16, 22 December 2015

Revision as of 07:24, 20 January 2016

Line 24:

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 •

Line 35:

: + E → • 1

: ''';Item set 2'''

: S → E •

: ''';Item set 3'''

: E → 1 E •

Line 45:

{| class="wikitable"

|- align="center"

|! || colspan="2" |''action''||''goto''

|- align="center"

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

!1||$||E

|- align="center"

!0

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

|- align="center"

!1

| '''1'''||s1/r2||r2||3

|- align="center"

!2

| '''2'''||||acc||

|- align="center"

!3

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

|}

Line 61 ⟶ 66:

{| class="wikitable"

|- align="center"

|! symbol|
|S||E||1

|- align="center"

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

|}

Line 74 ⟶ 81:

}

for example, {{code|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, {{code|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:

Line 81 ⟶ 88:

{| class="wikitable"

|- align="center"

|! || colspan="2" |''action''||''goto''

|- align="center"

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

!1||$||E

|- align="center"

!0

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

|- align="center"

!1

| '''1'''||s1||r2||3

|- align="center"

!2

| '''2'''||||acc||

|- align="center"

!3

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

|}