SLR Grammar
Encyclopedia
In computer science
, an SLR grammar is a class of formal grammar
that can be parsed by a simple LR parser
.
1. For any reducible rule A → a.Xb in state s (where X is some terminal), there must not exist some irreducible rule, B → y. in the same state s such that the follow set of B contains the terminal X. In more formal terms, the intersection of set containing the terminal X and the follow set of B must be empty. Violation of this rule is a Shift-Reduce Conflict.
2. For any two complete items A → a. and B → b. in s, Follow(A) and Follow(B) are disjoint (their intersection is the empty set). Violation of this rule is a Reduce-Reduce Conflict.
algorithm results in no ambiguity.
1. If state s contains any item of the form A -> a.Xb, where X is a terminal, and X is the next token in the input string, then the action is to shift the current input token onto the stack, and the new state to be pushed on the stack is the state containing the item A -> aX.b.
2. If state s contains the complete item A -> y., and the next token in the input string is in Follow(A), then the action is to reduce by the rule A -> y. A reduction by the rule S' -> S, where S is the start state, is equivalent to acceptance; this will happen only if the next input token is $. In all other cases, the new state in computed as follows. Remove the string y and all of its corresponding states from the parsing stack. Correspondingly, back up in the DFA to the state from which the construction of y began. By construction, this state must contain an item of the form B -> a.Ab. Push A on to the stack, and push the state containing the item B -> aA.b.
3. If the next input token is such that neither of the above two cases apply, an error is declared.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, an SLR grammar is a class of formal grammar
Formal grammar
A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...
that can be parsed by a simple LR parser
Simple LR parser
An SLR parser will typically have more conflict states than an LALR parser. For real-world computer languages, an SLR parser is usually not adequate, but for student projects in a compiler class it is a good learning tool....
.
Definitions
A rule of the form B → y. within a state of a SLR(1) automaton is said to be irreducible or in a reduce state because it has been completely expanded and is incapable of undergoing any shift transition. Rules in this state will have a dot (the current look-ahead position) located at the rightmost end of its RHS (Right Hand Side).Rules
A Grammar is said to be SLR(1) if and only if, for each and every state s in the SLR(1) automaton, none of the following conditions are violated:1. For any reducible rule A → a.Xb in state s (where X is some terminal), there must not exist some irreducible rule, B → y. in the same state s such that the follow set of B contains the terminal X. In more formal terms, the intersection of set containing the terminal X and the follow set of B must be empty. Violation of this rule is a Shift-Reduce Conflict.
2. For any two complete items A → a. and B → b. in s, Follow(A) and Follow(B) are disjoint (their intersection is the empty set). Violation of this rule is a Reduce-Reduce Conflict.
Parsing Algorithm
A grammar is said to be SLR(1) if the following Simple LR parserSimple LR parser
An SLR parser will typically have more conflict states than an LALR parser. For real-world computer languages, an SLR parser is usually not adequate, but for student projects in a compiler class it is a good learning tool....
algorithm results in no ambiguity.
1. If state s contains any item of the form A -> a.Xb, where X is a terminal, and X is the next token in the input string, then the action is to shift the current input token onto the stack, and the new state to be pushed on the stack is the state containing the item A -> aX.b.
2. If state s contains the complete item A -> y., and the next token in the input string is in Follow(A), then the action is to reduce by the rule A -> y. A reduction by the rule S' -> S, where S is the start state, is equivalent to acceptance; this will happen only if the next input token is $. In all other cases, the new state in computed as follows. Remove the string y and all of its corresponding states from the parsing stack. Correspondingly, back up in the DFA to the state from which the construction of y began. By construction, this state must contain an item of the form B -> a.Ab. Push A on to the stack, and push the state containing the item B -> aA.b.
3. If the next input token is such that neither of the above two cases apply, an error is declared.