Content deleted Content added
Repairing links to disambiguation pages - You can help! |
Magioladitis (talk | contribs) m clean up using AWB (10274) |
||
Line 1:
{{
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]]. 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.
Line 9:
To understand the differences between SLR and LALR, it is important to 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.
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.
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]].
| |||