Re: Bison reduce/reduce problem

Pete Jinks <>
27 Sep 2003 14:00:36 -0400

          From comp.compilers

Related articles
Bison reduce/reduce problem (2003-09-23)
Re: Bison reduce/reduce problem (Venkatesha Murthy) (2003-09-27)
Re: Bison reduce/reduce problem (Pete Jinks) (2003-09-27)
| List of all articles for this month |

From: Pete Jinks <>
Newsgroups: comp.compilers
Date: 27 Sep 2003 14:00:36 -0400
Organization: Computer Science Dept, University of Manchester
References: 03-09-081
Keywords: LALR, yacc
Posted-Date: 27 Sep 2003 14:00:36 EDT

Morey Roof wrote:
> So hopefully someone on here could show me how to fix it and could you
> sort of walk me through the process.

Generally, expand grammar rules until the guilty have been exposed,
but it is more a matter of practice and luck than of there being some
algorithm to follow. Here is an equivalent LR(1) grammar:

def : type /* param_spec */
| name/*_list*/ ':' type /* param_spec */
| name ':' type ',' /* return_spec */
| ID/*type*/ ',' /* return_spec */
| ID/*name, add to name_list*/ ',' name_list ':' type /* param_spec */
type, name, name_list as before

The problem is that the actions at the end of the 2nd, 4th and 5th
rules would probably need to do some tidying up (as indicated by the
comments) before dealing with the param_spec or return_spec - you end
up duplicating e.g. the action to convert an ID into a type for the
4th rule etc.

> [Your grammar isn't LR(k) since it has to look arbitrarily far ahead
> to see if there's a comma to tell whether something's a param_spec
> or a return_spec.

Another way of looking at it is that, even if an ID is followed by a
comma, you don't know whether that is part of a name_list or the end
of a return_spec until you have seen what follows the comma, so the
simpler expansion I tried first is LR(2) - the last two rules

def : type /* param_spec */
                | name ':' type /* param_spec */
                | name ':' type ',' /* return_spec */
                | type ',' /* return_spec */
                | name ',' name_list ':' type /* param_spec */

You might find this link helpful, where I try to talk about the
process and give several examples:

Peter J. Jinks, Room 2.99, Department of Computer Science,
University of Manchester, Oxford Road, Manchester, M13 9PL, U.K.
(+44/0)161-275 6186

Post a followup to this message

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