31-10-2012, 04:29 PM
Bottom-up Parsing
bottom-up parsing.ppt (Size: 246.5 KB / Downloads: 106)
Parsing Techniques
Top-down parsers (LL(1), recursive descent)
Start at the root of the parse tree from the start symbol and grow toward leaves (similar to a derivation)
Pick a production and try to match the input
Bad “pick” may need to backtrack
Some grammars are backtrack-free (predictive parsing)
Bottom-up parsers (LR(1), operator precedence)
Start at the leaves and grow toward root
We can think of the process as reducing the input string to the start symbol
At each reduction step a particular substring matching the right-side of a production is replaced by the symbol on the left-side of the production
Bottom-up parsers handle a large class of grammars
Bottom-up Parsing
A general style of bottom-up syntax analysis, known as shift-reduce parsing.
Two types of bottom-up parsing:
Operator-Precedence parsing
LR parsing
Handles
Handle of a string: Substring that matches the RHS of some production AND whose reduction to the non-terminal on the LHS is a step along the reverse of some rightmost derivation.
Formally:
A certain sentential form may have many different handles.
Right sentential forms of a non-ambiguous grammarhave one unique handle
Shift Reduce Parsing with a Stack
Two problems:
locate a handle and
decide which production to use (if there are more than two candidate productions).
General Construction: using a stack:
“shift” input symbols into the stack until a handle is found on top of it.
“reduce” the handle to the corresponding non-terminal.
other operations:
“accept” when the input is consumed and only the start symbol is on the stack, also: “error”
Using Operator-Precedence Relations
The intention of the precedence relations is to find the handle of a right-sentential form,
In our input string $a1a2...an$, we insert the precedence relation between the pairs of terminals (the precedence relation holds between the terminals in that pair).