In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, a Simple LR or SLR parser is a type of
LR parser
In computer science, LR parsers are a type of bottom-up parser that analyse deterministic context-free languages in linear time. There are several variants of LR parsers: SLR parsers, LALR parsers, Canonical LR(1) parsers, Minimal LR(1) parsers ...
with small
parse tables 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 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
In computer science, an LALR parser or Look-Ahead LR parser is a simplified version of a canonical LR parser, to parse a text according to a set of production rules specified by a formal grammar for a computer language. ("LR" means left-to-right, ...
and
Canonical LR parser In computer science, a canonical LR parser or LR(1) parser is an LR(k) parser for ''k=1'', i.e. with a single lookahead terminal. The special attribute of this parser is that any LR(k) grammar with ''k>1'' can be transformed into an LR(1) grammar. ...
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
Yacc (Yet Another Compiler-Compiler) is a computer program for the Unix operating system developed by Stephen C. Johnson. It is a Look Ahead Left-to-Right Rightmost Derivation (LALR) parser generator, generating a LALR parser (the part of a com ...
and
Bison
Bison are large bovines in the genus ''Bison'' (Greek: "wild ox" (bison)) within the tribe Bovini. Two extant and numerous extinct species are recognised.
Of the two surviving species, the American bison, ''B. bison'', found only in North Ame ...
. Many computer languages don't readily fit the restrictions of SLR, as is. Bending the language's natural grammar into
SLR grammar {{Confusing, date=March 2009
SLR grammars are the class of formal grammars accepted by a Simple LR parser. SLR grammars are a superset of all LR(0) grammars and a subset of all LALR(1) and LR(1) grammars.
When processed by an SLR parser, an SLR g ...
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.
SLR and LALR were both developed by
Frank DeRemer
Frank or Franks may refer to:
People
* Frank (given name)
* Frank (surname)
* Franks (surname)
* Franks, a medieval Germanic people
* Frank, a term in the Muslim world for all western Europeans, particularly during the Crusades - see Farang
Curr ...
as the first practical uses of
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
's LR parser theory. 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..
Lookahead sets
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
In computer science, LR parsers are a type of bottom-up parser that analyse deterministic context-free languages in linear time. There are several variants of LR parsers: SLR parsers, LALR parsers, Canonical LR(1) parsers, Minimal LR(1) parsers ...
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
production rule is found and reduced.
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
Follow(S)
, 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 {{Confusing, date=March 2009
SLR grammars are the class of formal grammars accepted by a Simple LR parser. SLR grammars are a superset of all LR(0) grammars and a subset of all LALR(1) and LR(1) grammars.
When processed by an SLR parser, an SLR g ...
.
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
In computer science, an LALR parser or Look-Ahead LR parser is a simplified version of a canonical LR parser, to parse a text according to a set of production rules specified by a formal grammar for a computer language. ("LR" means left-to-right, ...
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:
: (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:
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:
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)
for example, is false, because the left hand side of rule 2 is "E", and 1 is not in E's follow set.
Contrariwise, 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:
See also
*
LR parser
In computer science, LR parsers are a type of bottom-up parser that analyse deterministic context-free languages in linear time. There are several variants of LR parsers: SLR parsers, LALR parsers, Canonical LR(1) parsers, Minimal LR(1) parsers ...
*
LL parser
In computer science, an LL parser (Left-to-right, leftmost derivation) is a top-down parser for a restricted context-free language. It parses the input from Left to right, performing Leftmost derivation of the sentence.
An LL parser is called an ...
*
LALR parser
In computer science, an LALR parser or Look-Ahead LR parser is a simplified version of a canonical LR parser, to parse a text according to a set of production rules specified by a formal grammar for a computer language. ("LR" means left-to-right, ...
*
SLR grammar {{Confusing, date=March 2009
SLR grammars are the class of formal grammars accepted by a Simple LR parser. SLR grammars are a superset of all LR(0) grammars and a subset of all LALR(1) and LR(1) grammars.
When processed by an SLR parser, an SLR g ...
{{Parsers
Parsing algorithms