Re: more on FOLLOW sets

dww@inf.fu-berlin.de (Debora Weber-Wulff) writes:


>I've been thinking a lot about follow sets since the recent posting
>and I am puzzled by a question.
...
>So those of you who are "in the know": why follow?


  Because it is simple, and often sufficient. It is not perfect, however.


>Let's say we have the following item set in the set of LR(0) items:


> Ii: A -> B.T
> A -> B. where A is a nonterminal, T a terminal, B either.
>construction of the follow set for A can give rise to the following - if T
>is in the follow for A, then we have a shift-reduce conflict:


>My question: Why bother? Why not define the action at this point to be the
>reduction and ignore the shift possibility?


Either action, shift or reduce, could be the wrong one, depending on
subsequent input. Choosing to reduce (or shift) is simply a guess and may
lead to rejection of a valid input. You can see this if you fill out the
grammar the right way. Try this complete grammar:


  S -> A
  S -> A C
  A -> B T
  A -> B
  C -> T T


where B, T are terminals, S and A are nonterminals. Then in your LR(0)
state, we should shift if the remaining input is T, reduce if it is T T.
In this case, the grammar requires 2-symbol lookahead, and should be
rejected by a 1-symbol lookahead parser generator. Similar examples can
be constructed in which the grammar is LR(1) but not SLR(1). An SLR(1)
generator should reject the grammar, since it cannot correctly analyze all
legal cases.


Using default actions to resolve conflicts can be a great convenience, but
the grammar-writer has a responsibility to verify that the results are
always correct. By bypassing the formal mechanism you lose the formal
properties.


--
Jon Mauney, parsing partisan
Mauney Computer Consulting
mauney@csc.ncsu.edu (919) 828-8053


--

Return to the comp.compilers page.
Search the comp.compilers archives again.