|more on FOLLOW sets email@example.com (1992-06-26)|
|Re: more on FOLLOW sets firstname.lastname@example.org (1992-06-26)|
|From:||email@example.com (Jon Mauney)|
|Organization:||North Carolina State University|
|Date:||Fri, 26 Jun 1992 16:52:15 GMT|
|Posted-Date:||Fri, 26 Jun 1992 16:52:15 GMT|
firstname.lastname@example.org (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
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
email@example.com (919) 828-8053
Return to the
Search the comp.compilers archives again.