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


Read more about SLR Grammar:  Definitions, Rules, Parsing Algorithm

Other articles related to "slr grammar, grammar, slr":

SLR Grammar - Parsing Algorithm
... A grammar is said to be SLR(1) if the following Simple LR parser algorithm results in no ambiguity ...

Famous quotes containing the word grammar:

    I demand that my books be judged with utmost severity, by knowledgeable people who know the rules of grammar and of logic, and who will seek beneath the footsteps of my commas the lice of my thought in the head of my style.
    Louis Aragon (1897–1982)