Java Reference
In-Depth Information
We now consider how to incorporate semantic actions into bottom-up parsers.
Suchparsers are almost always generated automaticallyby tools (e.g., JavaCUP,
yacc, Bison) that allow incorporation of code sequences that execute as reduc-
tions are performed. Such parsers also execute
shift
actions, but no provision
is generally made for semantic actions when symbols are shifted.
Consider an LR parser that is about to perform a reduction using the
production
...X
n
As discussed in Chapter 6, the symbols
A
→X
1
X
...X
n
are on top-of-stack prior to
1
the reduction, with
X
n
topmost. The reduction pops
n
symbols from the stack
and pushes the symbol A onto the stack. It is likely that previous reductions
have associated semantic values with the symbols
...X
n
in the bottom-
up parse. The semantic action associated with the reduction consists of an
arbitrary fragment of code that can reference semantic values associated with
X
X
1
...X
n
and can associate a semantic value with the resulting A.
The notation for referencing a given semantic value varies among parser-
generating tools. For example, yacc and Bison use the ordinal occurrence of
the symbol in semantic action code: $
i
denotes the semantic value of
1
X
i
and $0
denotes A's semantic value. Other tools (e.g., JavaCUP) use the notation
X
:
val
to specify
val
as the semantic value associated with
X
.Ine
ff
ect, the bottom-up
parser operates two stacks:
•
The
syntactic stack
(also called the
parse stack
) manipulates terminal and
nonterminal symbols as described in Chapter 6
•
The
semantic stack
manipulates semantic values associatedwith the gram-
mar symbols.
The code for maintaining both stacks is generated automatically by the parser
generator, based on the grammar and semantic-action code specified by the
compiler writer.
Consider the translation task of computing the value of a string of base-10
digits. For example, given the input 431$, the translation would produce
the numerical value 431. This task—normally handled by the scanning phase
of a compiler—is illustrated here as a for syntax-directed, bottom-up transla-
tion using the grammar shown in Figure 7.3(a). The grammar is augmented
with semantic actions, shown beneath each production. Semantic values are
denoted by subscripts on grammar symbols. For example, the variable
ans
is