Java Reference
In-Depth Information
LR
(
k
), because such parsers scan the input from the left (the “L” in LR)
producing a rightmost derivation (the “R” in LR) in reverse, using
k
symbols of lookahead
Unfortunately, the termLR denotes both the generic bottom-up parsing engine
as well as a particular technique for constructing the engine's tables. It should
be clear in context which meaning is intended.
In an LL parser, each state is committed to expand a particular nonterminal.
On the other hand, an LR parser can concurrently anticipate the eventual
success of multiple nonterminals. This flexibility makes LR parsers more
general than LL parsers.
Tools for the automatic construction of LR parsers are available for a variety
of platforms, including ML, Java
TM
,C,andC
•
. Suppose a parser generator
for a platform
t
emits a program
p
based on a supplied grammar
g
.Allparsers
generated by this parser generator are compiled using
t
. Thus, while
p
is
compiled by
t
, the resulting programwill parse input according to grammar
g
.
For example, yacc
1
is a popular parser generator that emits C code. If yacc is
given a grammar for the syntax of Fortran, then the resulting parser is compiled
using C. However, the resulting parser performs syntax analysis for Fortran.
The syntax of most modern programming languages is defined by grammars
that are suitable for automatic parser generation using LR techniques.
++
The basic properties and actions of a generic LR parser are introduced in
Sections 6.1 and 6.2. Section 6.3 presents the most basic table-construction
method for LR parsers. Section 6.4 considers problems that prevent automatic
LR parser construction. Sections 6.5.1, 6.5.2, and 6.5.4 discuss table-building
algorithms of increasing sophistication and power. Of particular interest is the
LALR(1) technique covered in Section 6.5.2, which is used in most LR parser
generators. The formal definition of most modern programming languages
includes an LALR(1) grammar to specify the language's syntax.
In this section, we examine the operation of an LR parser, assuming that an
LR parse table has already been constructed to guide the parser's actions.
The reader may be understandably curious about how the table's entries are
determined. However, table-construction techniques are best considered after
obtaining a solid understanding of an LR parser's operation.
We describe the operation of an LR parser informally in Sections 6.2.1
and 6.2.2. Section 6.2.3 describes a generic LR parsing engine whose actions
are guided by the parse table defined in Section 6.2.4. Section 6.2.5 presents
LR(
k
) parsing more formally.
1
The tool yacc's name stands for
yet another compiler compiler
.
