SLR Grammar

SLR Grammar

In computer science, SLR grammars are the class of formal grammars that are 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 grammar is converted into parse tables with no shift/reduce or reduce/reduce conflicts for any combination of LR(0) parser state and expected lookahead symbol. If the grammar is not SLR, the parse tables will have shift/reduce conflicts or reduce/reduce conflicts for some state and some lookahead symbol, and the resulting rejected parser is no longer deterministic. The parser cannot decide whether to shift or reduce next, or cannot decide between two candidate reductions. SLR parsers use a Follow(A) calculation to pick the lookahead symbols to expect for every completed nonterminal.

LALR parsers use a different calculation which sometimes gives smaller, tighter lookahead sets for the same parser states. Those smaller sets can eliminate overlap with the state's shift actions, and overlap with lookaheads for other reductions in this same state. The overlap conflicts reported by SLR parsers are then spurious, a result of the approximate calculation using Follow(A).

A grammar which is ambiguous will have unavoidable shift/reduce conflicts or reduce/reduce conflicts for every LR analysis method, including SLR. A common way for computer language grammars to be ambiguous is if some nonterminal is both left- and right-recursive:

Expr → Expr * Val

Expr → Val + Expr

Expr → Val