Week 2

Scanning and parsing and the need for look-ahead

1. 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.
2. Construct LR(1) parse table for the following LR(1) grammar, where the letters = * a $ (shown in red) are tokens (i.e. terminals):
   

   S' -> S$
   S  -> L=R | R
   L  -> *R | a
   R  -> L

3. Why is the grammar shown in (2.) not an LR(0) grammar?