Re: more on FOLLOW sets (Jon Mauney)
Fri, 26 Jun 1992 16:52:15 GMT

          From comp.compilers

Related articles
more on FOLLOW sets (1992-06-26)
Re: more on FOLLOW sets (1992-06-26)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Jon Mauney)
Organization: North Carolina State University
Date: Fri, 26 Jun 1992 16:52:15 GMT
References: 92-06-129
Keywords: LR(1), parse
Posted-Date: Fri, 26 Jun 1992 16:52:15 GMT (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

Jon Mauney, parsing partisan
Mauney Computer Consulting (919) 828-8053


Post a followup to this message

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