Java Reference
In-Depth Information
Stack
Input
Output
#
E
id+id*id#
#
E
0
T
id+id*id#
1
#
E
0
T
0
F
id+id*id#
4
#
E
0
T
0
idid+id*id#
8
#
E
0
T
0
+id*id#
#
E
0
+id*id#
6
#
E
0
T
+ +id*id#
2
#
E
0
T
id*id#
#
E
0
T
0
F
id*id#
4
#
E
0
T
0
idid*id#
8
#
E
0
T
0
*
id#
#
E
0
T
0
F
*
*
id#
5
#
E
0
T
0
F
id
#
#
E
0
T
0
id
id
#
8
#
E
0
T
0
#
#
E
0
#
6
# #
3
We are left with the question: How do we construct the parsing table in Figure 3.5?
Consider what the entries in the table tell us:
table[Y, a] = i, where i is the number of the rule Y ::= X
1
X
2
:::X
n
says that if there is the goal Y on the stack and the next unscanned symbol is a, then we can
rewrite Y on the stack as the sequence of sub-goals X
1
X
2
:::X
n
. So, the question becomes:
When do we replace Y with X
1
X
2
:::X
n
as opposed to something else? If we consider the
last two rules of our grammar (3.21),
7. F ::=
(
E
)
8. F ::=
id
and we have the non-terminal F on top of our parsing stack, the choice is simple. If the
next unscanned symbol is an open parenthesis
(
, we apply rule 7; and if it is an
id
, we
apply rule 8. That is,
table[F,
(
] = 7
table[F,
id
] = 8
The problem becomes slightly more complicated when the right-hand side of the rule
either starts with a non-terminal or is simply .
In general, assuming both and are (possibly empty) strings of terminals and non-
terminals, table[Y , a] = i, where i is the number of the rule Y ::= X
1
X
2
:::X
n
, if either
1. X
1
X
2
:::X
n
) a, or
2. X
1
X
2
:::X
n
) , and there is a derivation S
#
) Y a, that is, a can follow Y in a
derivation.
For this we need two helper functions: first and follow.
Search WWH ::
Custom Search