Simple LR parser: Difference between revisions

Revision as of 14:14, 30 September 2013

Revision as of 02:29, 27 June 2014

Line 1:

{{norefs|date=December 2012}}

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{{dn|date=April 2013}} 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.