Fri, 26 Jun 1992 16:52:15 GMT

Related articles |
---|

more on FOLLOW sets dww@inf.fu-berlin.de (1992-06-26) |

Re: more on FOLLOW sets mauney@adm.csc.ncsu.edu (1992-06-26) |

Newsgroups: | comp.compilers |

From: | mauney@adm.csc.ncsu.edu (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 |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.