Java Reference
In-Depth Information
Y ::= Y 0
Y 0 ::=
Y 0 ::=
(3.29)
Example. Reconsider (3.14).
S ::= if E do S
j if E then S else S
j s
E ::= e
Following the rewriting rule (3.29), we can reformulate the grammar as
S ::= if E S 0
j s
S 0 ::= do S
j then S else S
E ::= e
3.4 Bottom-Up Deterministic Parsing
In bottom-up parsing, one begins with the input sentence and scanning it from left-to-right,
recognizes sub-trees at the leaves and builds a complete parse tree from the leaves up to
the start symbol at the root.
3.4.1 Shift-Reduce Parsing Algorithm
For example, consider our old friend, the grammar (3.8) repeated here as (3.30):
1. E ::= E + T
2. E ::= T
3. T ::= T * F
4. T ::= F
5. F ::= ( E )
6. F ::= id
(3.30)
And say we want to parse the input string, id+id*id . We would start off with the
initial configuration:
Stack
Input
Action
# id+id*id#
At the start, the terminator is on the stack, and the input consists of the entire input
sentence followed by the terminator. The first action is to shift the first unscanned input
symbol (it is underlined) onto the stack.
Search WWH ::




Custom Search