Java Reference
In-Depth Information
7.2 Bottom-Up Syntax-Directed Translation
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.
7.2.1 Example
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
 
 
 
Search WWH ::




Custom Search