Simple precedence grammar
Encyclopedia
A simple precedence grammar is a context-free formal grammar
that can be parsed with a simple precedence parser
.
precedence table:
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 with a simple precedence parser
Simple precedence parser
In computer science, a Simple precedence parser is a type of bottom-up parser for context-free grammars that can be used only by Simple precedence grammars....
.
Formal definition
G = (N, Σ, P, S) is a simple precedence grammar if all the production rules in P comply with the following constraints:- There are no erasing rules (ε-productions)
- There are no useless rulesUseless rulesIn formal grammar, useless rules are rules of symbol production which are unreachable or unproductive, that is, they are rules of production which can never be applied.-Examples:S \to Bb | CcB \to Bb | bC \to Cc | cD \to Bd | CdD is unreachable....
(unreachable symbols or unproductive rules) - For each pair of symbols X, Y (X, Y
(N ∪ Σ)) there is only one Wirth-Weber precedence relationWirth-Weber precedence relationshipThe Wirth-Weber relationship between a pair of symbols is necessary to determine if a formal grammar is a Simple precedence grammar, and in such case the Simple precedence parser can be used....
. - G is uniquely inversibleUniquely Inversible GrammarA uniquely inversible grammar is a formal grammar where no two distinct productions give the same result. This implies the specific production can be inferred from its results.- Formal definition :...
Example 1
precedence table:
| S | a | b | c | $ | |
| S |  |
 |
 |
 |
|
| a |  |
 |
 |
||
| b |  |
 |
 |
||
| c |  |
 |
 |
 |
|
| $ |  |
 |