Re: Bison reduce/reduce problem

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
conflict:


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:
http://www.cs.man.ac.uk/~pjj/complang/grammar.html


--
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 http://www.cs.man.ac.uk/~pjj

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