bottom-up parsing
bottom-up parsing (shift-reduce parsing) A strategy for parsing sentences of a context-free grammar that attempts to construct a parse tree beginning at the leaf nodes and working “bottom-up” toward the root.
Bottom-up (or shift-reduce) parsers work by “shifting” symbols onto a stack until the top of the stack contains a right-hand side of a production. The stack is then “reduced” by replacing the production's right-hand side by its left-hand side. This process continues until the string has been “reduced” to the start symbol of the grammar.
The string of symbols to be replaced at each stage is called a handle. Bottom-up parsers that proceed from left to right in the input string must always replace the leftmost handle and, in so doing, they effectively construct a rightmost derivation sequence in reverse order. For example, a rightmost derivation of the string abcde might be S ⇒ ACD ⇒ ACde ⇒ Acde ⇒ abcde
A bottom-up parser would construct this derivation in reverse, first reducing abcde to Acde, then to ACde, then to ACD, and finally to the start symbol S. The handle at each stage is respectively ab, c, de, and ACD.
See also LR parsing, precedence parsing.
Bottom-up (or shift-reduce) parsers work by “shifting” symbols onto a stack until the top of the stack contains a right-hand side of a production. The stack is then “reduced” by replacing the production's right-hand side by its left-hand side. This process continues until the string has been “reduced” to the start symbol of the grammar.
The string of symbols to be replaced at each stage is called a handle. Bottom-up parsers that proceed from left to right in the input string must always replace the leftmost handle and, in so doing, they effectively construct a rightmost derivation sequence in reverse order. For example, a rightmost derivation of the string abcde might be S ⇒ ACD ⇒ ACde ⇒ Acde ⇒ abcde
A bottom-up parser would construct this derivation in reverse, first reducing abcde to Acde, then to ACde, then to ACD, and finally to the start symbol S. The handle at each stage is respectively ab, c, de, and ACD.
See also LR parsing, precedence parsing.
More From encyclopedia.com
Reducing Sugar , reducing sugar A monosaccharide or disaccharide sugar that can donate electrons to other molecules and can therefore act as a reducing agent. The pos… 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… Handle , han·dle / ˈhandl/ • v. [tr.] 1. feel or manipulate with the hands: heavy paving slabs can be difficult to handle people who handle food. ∎ drive or c… Signs And Symbols , Symbols
Culture is based on symbols. Flags, traffic lights, diplomas, and mathematical notation are all, in their various ways, symbols. So foundatio… ATTENUATE , at·ten·u·ate • v. / əˈtenyoōˌāt/ [tr.] (often be attenuated) reduce the force, effect, or value of: her intolerance was attenuated by a rather unexpe…
You Might Also Like
NEARBY TERMS
bottom-up parsing