precedence parsing
precedence parsing A bottom-up parsing technique that exploits precedence relations on the symbols of the grammar to decide when a string of symbols may be replaced, i.e. form a handle. Two precedence parsing techniques, operator precedence and simple precedence, are in common use.
In simple precedence three relations, <· ·> and ≐, are defined on the symbols (terminal and nonterminal) of the grammar. If X <· Y, X ≐ Y, or X ·> Y
then, respectively, X is said to yield precedence to Y, have the same precedence as Y, or take precedence over Y. Note that these relations are not symmetric. By inserting the precedence relations between symbols in a sentential form and then regarding the <· and ·> symbols as matching brackets, a handle is determined as the leftmost string delimited by <· at its left end and ·> at its right end.
Operator precedence differs from simple precedence in that the three precedence relations are defined on just the terminal symbols of the grammar. Furthermore the grammar must satisfy the property that nonterminals on the right-hand side of a production must always be separated by at least one terminal.
Arithmetic expressions provided the original motivation for operator precedence since conventionally multiplication takes precedence over addition. Simple precedence is a generalization of operator precedence. Both methods are limited in the scope of their application to grammars for which at most one precedence relation exists between any ordered pair of symbols. In addition the right-hand side of productions must be unique.
In simple precedence three relations, <· ·> and ≐, are defined on the symbols (terminal and nonterminal) of the grammar. If X <· Y, X ≐ Y, or X ·> Y
then, respectively, X is said to yield precedence to Y, have the same precedence as Y, or take precedence over Y. Note that these relations are not symmetric. By inserting the precedence relations between symbols in a sentential form and then regarding the <· and ·> symbols as matching brackets, a handle is determined as the leftmost string delimited by <· at its left end and ·> at its right end.
Operator precedence differs from simple precedence in that the three precedence relations are defined on just the terminal symbols of the grammar. Furthermore the grammar must satisfy the property that nonterminals on the right-hand side of a production must always be separated by at least one terminal.
Arithmetic expressions provided the original motivation for operator precedence since conventionally multiplication takes precedence over addition. Simple precedence is a generalization of operator precedence. Both methods are limited in the scope of their application to grammars for which at most one precedence relation exists between any ordered pair of symbols. In addition the right-hand side of productions must be unique.
More From encyclopedia.com
George Boole , Boole, George
Boole, George
(b. Lioncoln, England, 1815; d. Cork, Ireland, 1864)
mathematics.
George Boole was the son of John Boole, a cobbler whose… Garrett Birkhoff , Birkhoff was the son of mathematician George David Birkhoff and Margaret Grafius Birkhoff. George Birkhoff, the father, was the first American mathem… Domain , Domain
The domain of a relation is the set that contains all the first elements, x, from the ordered pairs (x,y) that make up the relation. In mathem… Symbol , Symbol
From a psychoanalytic perspective, the symbol refers to all indirect and figurative representations of unconscious desire (symptoms, dreams, s… Symbolism , The evolution of representational capacities and symbolic expression has contributed essentially to human thought, language, and culture. There are d… Diophantus Of Alexandria , Diophantus of Alexandria
Diophantus of Alexandria
(fl. ad. 250)
mathematics.
We know virtually nothing about the life of Diophantus. The dating of hi…
You Might Also Like
NEARBY TERMS
precedence parsing