Scanning and parsing and the need for look-ahead
- An LR(k) parser
has a fixed look-ahead of length k.
As discussed in class, a scanner uses a stack to perform a look-ahead
of arbitrary length, yet a scanner is weaker than an LR(k)
parser in the sense that it cannot keep track of a
stack of states and therefore
cannot accept expressions that have a recursive structure (like all
expressions with balanced parantheses).
Some parser generators are scanner-less, i.e. they attempt to do the
scanner's job of breaking text up into tokens directly within the
grammar, so that only one single grammar specification needs to be
built (and no definition of a scanner). Most parser generators for
scanner-less parsers use a generalized version of LR, called GLR, which
is very involved and uses back-tracking to make use of a larger
lookahead. Give an example of why it may be problematic to produce a
scanner-less LR(1) parser or even a scanner-less LR(k) parser for any konstant k.
- Construct LR(1) parse table for the following LR(1)
grammar, where the letters = * a $ (shown in red) are tokens
S' -> S$
S -> L=R | R
L -> *R | a
R -> L
- Why is the grammar shown in (2.) not an LR(0) grammar?