30 Mar 2003 21:40:18 -0500

Related articles |
---|

LR(1) resolving SLR(1) reduce/reduce conflict haberg@math.su.se (2003-03-30) |

Re: LR(1) resolving SLR(1) reduce/reduce conflict gvcormac@speedy.uwaterloo.ca (2003-03-30) |

Re: LR(1) resolving SLR(1) reduce/reduce conflict haberg@math.su.se (2003-03-31) |

Re: LR(1) resolving SLR(1) reduce/reduce conflict gvcormac@speedy.uwaterloo.ca (2003-04-05) |

Re: LR(1) resolving SLR(1) reduce/reduce conflict haberg@math.su.se (2003-04-07) |

From: | gvcormac@speedy.uwaterloo.ca (Gordon Cormack) |

Newsgroups: | comp.compilers |

Date: | 30 Mar 2003 21:40:18 -0500 |

Organization: | A poorly-installed InterNetNews site |

References: | 03-03-181 |

Keywords: | parse, LR(1) |

Posted-Date: | 30 Mar 2003 21:40:18 EST |

Hans Aberg <haberg@math.su.se> wrote:

*>Is it possible for LR(1) to resolve a reduce/reduce conflict appearing in*

*>SLR(1)?*

The following grammar is LR(1) but not SLR(1) or LALR(1)

S -> A x B x

S -> B y A y

A -> w

B -> w

In the LR(0) machine you have a state that looks like this:

A -> w .

B -> w .

SLR(1) uses follow(A) = {x,y} as the lookahead for the first item

and follow(B) = {x,y} as the lookahead for the second,

so ther's a reduce-reduce conflict.

LR(1) has two different states:

A -> w . { x }

A -> w . { y }

and

A -> w . { y }

A -> w . { x }

Neither state has a conflict.

LALR(1) merges these two LR(1) states, because they have the same

core. The net results is the same as for SLR(1) - a reduce-reduce conflict.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.