Xref: utzoo comp.unix.questions:25294 comp.lang.misc:5457 gnu.misc.discuss:1738
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!decwrl!ads.com!potomac!jtn
From: jtn@potomac.ads.com (John T. Nelson)
Newsgroups: comp.unix.questions,comp.lang.misc,gnu.misc.discuss
Subject: Problem with YACC and LEX (Bison and Flex)
Keywords: yacc lex bison flex
Message-ID: <9138@potomac.ads.com>
Date: 7 Sep 90 14:38:22 GMT
Organization: Advanced Decision Systems, Arlington VA
Lines: 97


I know this isn't a Un*x question specifically but I don't know where
to post a question like this.  It's a problem with YACC.  I seem to
have a reduce/reduce conflict that YACC is unable to resolve, yet it
looks to me like it SHOULD be able to figure out the ambiguity.
Now actually I'm using the Macintosh implementation of GNU Bison,
however I assume that the two oprate identically.

I've written a grammar to recognize the following input
sequence:

A = \n
	B \n
	C \n
	D \n
E = \n
	F \n
	G \n
	H \n

etc etc.

Notice that line feeds are considered tokens here and not white space.
I do this because the existance of a token helps delimit lines and
distinguish the "X =" lines from the other lines.  At least that's the
idea.  Problem is that Bison kicks me out with an error when it gets
to the second "=" in the line E = \n.

The grammar looks a lot like this:


SECTION
	:
	NAME	SPECS
|
	SECTION		NAME	SPECS
	;

NAME
	:
	TOKEN_WORD	TOKEN_EQUAL_SIGN	OPTIONAL_THING	LINE_FEED
|
	NUMBER	TOKEN_EQUAL_SIGN	OPTIONAL_THING	LINE_FEED
	;

SPECS
	:
	SPEC
|
	SPECS	SPEC
	;

SPEC
	:
	TOKEN_WORD	OPTIONAL_THING	LINE_FEED
|
	NUMBER	OPTIONAL_THING	LINE_FEED
	;

OPTIONAL_THING
	:
|
	TOKEN_SPECIAL_SYMBOL
	;

"OPTIONAL_THING" recognizes a special identifier or an empty sequence
so with the above input string it always does the empty thing.

Bison seems to get confused when it gets to SPEC.  It fails to match the
second "=" and immediately enters yyerror.  It's almost as if it were
loosing track of the alternative "NAME" in rule "SECTION."  Is the
intention not getting through to the implementation?  Am I doing
something uterlly stupid?

Now the Bison processor does indeed catch a bunch of shift/reduce and 2
reduce/reduce conflicts however the "TOKEN_EQUAL_SIGN" in the NAME rule
should be enough to uniquify it from the "SPEC" rules and that's what
bugs me..... Bison is unable to make a decision on the string when the
token that resolves the ambiguity is one or perhaps two tokens ahead
in the stream.

Notice that I am also using TWO recursive rules in tandem (SECTION,
SPECS).  Maybe this is confusing Bison.  Any ideas?  I've gone over it
and over it and worse, I can't figure out how to rewrite the grammar to
do the same thing so I'm basically stuck with this form... or am I?

Hope you have some thoughts.  I don't.


-- 

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
ORGANIZATION:  Advanced Decision Systems   GEOGRAPHIC: Arlington, VA
UUCP:          kzin!speaker@mimsy.umd.edu  INTERNET:   jtn@potomac.ads.com
SPOKEN:        Yo... John!                 PHONE:      (703) 243-1611
PROJECT:       The Conrail Locomotive/Harpsichord Fusion Program
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=