Simple LR parser: Difference between revisions

Revision as of 02:07, 13 December 2012

Latest revision as of 14:38, 22 August 2025

(34 intermediate revisions by 25 users not shown)

Line 1:

{{Short description|Computer mechanic}}

{{norefs|date=December 2012}}

{{more citations needed|date=November 2024}}

In [[computer science]], a '''Simple LR''' or '''SLR parser''' is a type of [[LR parser]] with small [[parse table]]s and a relatively simple parser generator algorithm. As with other types of LR(1) parser, an SLR parser is quite efficient at finding the single correct [[bottom-up parsing|bottom-up parse]] in a single left-to-right scan over the input stream, without guesswork or backtracking. The parser is mechanically generated from a formal grammar for the language.

In [[computer science]], a '''Simple LR''' or '''SLR parser''' is a type of [[LR parser]] with small [[LR parser#Constructing LR(0) parsing tables|parse table]]s and a relatively simple parser generator algorithm. As with other types of LR(1) parser, an SLR parser is quite efficient at finding the single correct [[bottom-up parsing|bottom-up parse]] in a single left-to-right scan over the input stream, without guesswork or backtracking. The parser is mechanically generated from a formal grammar for the language.

SLR and the more- general methods [[LALR parser]] and [[Canonical LR parser]] have identical methods and similar tables at parse time; they differ only in the mathematical grammar analysis algorithms used by the parser generator tool. SLR and LALR generators create tables of identical size and identical parser states. SLR generators accept fewer grammars than do LALR generators like [[yacc]] and [[GNU bison|Bison]].{{citation needed|date=November 2024}} Many computer languages don't readily fit the restrictions of SLR, as is. Bending the language's natural grammar into [[SLR grammar]] form requires more compromises and grammar hackery. So LALR generators have become much more widely used than SLR generators, despite being somewhat more complicated tools. SLR methods remain a useful learning step in college classes on compiler theory.{{citation needed|date=November 2024}}

SLR and LALR were both developed by [[Frank DeRemer]] as the first practical uses of [[Donald Knuth]]'s LR parser theory.<ref>{{Cite web| title=Introduction to Computational Linguistics - LR Parsers | url=https://wiki.eecs.yorku.ca/course_archive/2013-14/W/6339/_media/lrk.pdf | archive-url=https://web.archive.org/web/20210415164259/https://wiki.eecs.yorku.ca/course_archive/2013-14/W/6339/_media/lrk.pdf | archive-date=2021-04-15}}</ref><ref>{{Cite web| title=Introduction to LR-Parsing | url=https://www.seas.upenn.edu/~cis5110/notes/cis511-sl9.pdf | archive-url=https://web.archive.org/web/20240629070724/https://www.seas.upenn.edu/~cis5110/notes/cis511-sl9.pdf | archive-date=2024-06-29}}</ref> The tables created for real grammars by full LR methods were impractically large, larger than most computer memories of that decade, with 100 times or more parser states than the SLR and LALR methods.<ref>{{citationcite book needed| url=https://books.google.com/books?id=nEA9AAAAIAAJ&pg=PA87 | title=LR Parsing: Theory and Practice | isbn=978-0-521-30413-9 | last1=Chapman | first1=Nigel P. | date=June17 December 1987 | publisher=CUP Archive 2012}}</ref>

== Lookahead Setssets ==

To understand the differences between SLR and LALR, it is important to understand their many similarities and how they both make shift-reduce decisions. (See the article [[LR parser]] now for that background, up through the section on reductions' '''lookahead sets'''.)

The one difference between SLR and LALR is how their generators calculate the lookahead sets of input symbols that should appear next, whenever some completed [[Formal grammar#The syntax of grammars|production rule]] is found and reduced.

To understand the differences between SLR and LALR, you should first understand their many similarities and how they both make shift-reduce decisions. Please read article [[LR parser]] now for that background, up through the section on reductions' Lookahead Sets.

SLR generators calculate that lookahead by an easy approximation method based directly on the grammar, ignoring the details of individual parser states and transitions. This ignores the particular context of the current parser state. If some nonterminal symbol ''S'' is used in several places in the grammar, SLR treats those places in the same single way rather than handling them individually. The SLR generator works out <code>Follow(S)</code>, the set of all terminal symbols which can immediately follow some occurrence of ''S''. In the parse table, each reduction to ''S'' uses Follow(S) as its LR(1) lookahead set. Such follow sets are also used by generators for LL top-down parsers. A grammar that has no shift/reduce or reduce/reduce conflicts when using follow sets is called an [[SLR grammar]]. {{citation needed|date=November 2024}}

The one difference between SLR and LALR is how their generators calculate the '''lookahead sets''' of input symbols that should appear next, whenever some completed [[Formal grammar#The syntax of grammars|production rule]] is found and reduced.

SLRLALR generators calculate that lookahead sets by ana easymore approximationprecise method based directly on the grammar, ignoringexploring the detailsgraph of individual parser states and their transitions. This ignoresmethod considers the particular context of the current parser state. IfIt somecustomizes nonterminalthe symbolhandling Sof iseach usedgrammar inoccurrence severalof placessome innonterminal theS. grammar, SLRSee treatsarticle those[[LALR placesparser]] infor thefurther samedetails singleof waythis rather than handling them individuallycalculation. The SLRlookahead generatorsets workscalculated outby Follow(S),LALR thegenerators setare ofa all terminal symbols which can immediately follow some occurrencesubset of S. In the parse table, each reduction to S uses Follow(S)and ashence itsbetter LR(1than) lookaheadthe set. Such followapproximate sets arecalculated alsoby used bySLR generators. for LLIf top-downa parsers.grammar has Atable grammarconflicts thatwhen hasusing noSLR shift/reducefollow orsets, reduce/reducebut conflictsis conflict-free when using FollowLALR follow sets, it is called ana [[SLRLALR grammar]]. {{citation needed|date=November 2024}}

LALR generators calculate lookahead sets by a more precise method based on exploring the graph of parser states and their transitions. This method considers the particular context of the current parser state. It customizes the handling of each grammar occurrence of some nonterminal S. See article [[LALR parser]] for further details of this calculation. The lookahead sets calculated by LALR generators are a subset of (and hence better than) the approximate sets calculated by SLR generators. If a grammar has table conflicts when using SLR follow sets, but is conflict-free when using LALR follow sets, it is called a LALR grammar.

== Example ==

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

Line 26 ⟶ 25:

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 37 ⟶ 36:

: + E → • 1

: ''';Item set 2'''

: S → E •

: ''';Item set 3'''

: E → 1 E •

The action and goto tables:

{| class="wikitable"

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

<tr|- align="center">

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

<td></td>

|- align="center"

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

<td>! ''gotostate''</td>

!1||$||E

</tr>

<tr|- align="center">

!0

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

|s1||||2

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

|- align="center"

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

!1

<td>'''E'''</td>

|s1/r2||r2||3

</tr>

<tr|- align="center">

!2

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

|||acc||

<td>s1</td>

|- align="center"

<td></td>

!3

<td>2</td>

|r1||r1||

</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:

{| class="wikitable"

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

<tr|- align="center">

<td>! symbol</td>

|S||E||1

<td>S</td>

|- align="center"

<td>E</td>

! following

<td>1</td>

|$||$||1,$

</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))

}

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:

{| class="wikitable"

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

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

<tr align="center">

|- align="center"

<td></td>

! ''state''

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

!1||$||E

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

|- align="center"

</tr>

!0

<tr align="center">

|s1||||2

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

|- align="center"

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

!1

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

|s1||r2||3

<td>'''E'''</td>

|- align="center"

</tr>

!2

<tr align="center">

|||acc||

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

|- align="center"

<td>s1</td>

!3

<td></td>

|||r1||

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

Line 157 ⟶ 113:

* [[SLR grammar]]

==References==

[[Category:Parsing algorithms]]

{{reflist}}

{{Parsers}}

[[ar:محلل بسيط من اليسار إلى اليمين]]

[[fr:Analyseur SLR]]

[[Category:Parsing algorithms]]

[[it:Parser SLR]]

[[ja:単純LR法]]

[[pl:Parser SLR]]

[[sr:SLR analizator]]