Java Reference
In-Depth Information
Stack
Input
Action
# id+id*id#
shift
#id +id*id#
From this configuration, the next action is to reduce the
id
on top of the stack to an F
using rule 6.
Stack
Input
Action
# id+id*id#
shift
#id +id*id#
reduce (6)
#
F
+id*id#
From this configuration, the next two actions involve reducing the F to a T (by rule 4),
and then to an E (by rule 2).
Stack
Input
Action
# id+id*id#
shift
#id +id*id#
reduce (6)
#
F
+
id*id#
reduce (4)
#
T
+
id*id#
reduce (2)
#
E
+
id*id#
The parser continues in this fashion, by a sequence of shifts and reductions, until we
reach a configuration where
#
E is on the stack (E on top) and the sole unscanned symbol
in the input is the terminator
#
. At this point, we have reduced the entire input string to
the grammar's start symbol E, so we can say the input is accepted.
Stack
Input
Action
#
id
+id*id#
shift
#id
+
id*id#
reduce (6)
#
F
+
id*id#
reduce (4)
#
T
+id*id#
reduce (2)
#
E
+id*id#
shift
#
E
+ id*id#
shift
#
E
+id *id#
reduce (6)
#
E
+
F
*id#
reduce (4)
#
E
+
T
*id#
shift
#
E
+
T
* id#
shift
#
E
+
T
*id#
reduce (6)
#
E
+
T
*
F
#
reduce (3)
#
E
+
T
#
reduce (1)
#
E
#
accept
Notice that the sequence of reductions 6, 4, 2, 6, 4, 6, 3, 1 represents the right-most
derivation of the input string but in reverse:
Search WWH ::
Custom Search