Re: yacc: how to fix ambiguity

"Lemaitre, Laurent" <r29173@email.sps.mot.com>
On 30 Oct 1998 13:57:39 -0500


Posted
>> I am writing a parser for a specific grammar and
found the following problem for which I have no answer:


In my grammar expr and func are defined as:


expr := expr + expr
                | ( expr )
                | IDENTIFIER


func := IDENTIFIER IDENTIFIER ( IDENTIFIER )


define -> DEFINE func expr
                    | DEFINE IDENTIFER expr


The grammar is ambiguous. For instance:


ID ( ID ) + ID yields (a) FUNC expr
                                            (b) ID expr + expr


/*
for instance if I parse "define sign (x) +y" I
would like to mean sign(x) = +y and not sign = (x)+y
*/


I would like to tell yacc to reduce rule (a).


Is-it possible to code it into yacc input?


Any help/advice welcome,
<<


In a way your problem may simply be that your are not getting the
reduction you want. But perhaps it is because of miscoding, instead of
ambiguity.


You have listed


func := IDENTIFIER IDENTIFIER ( IDENTIFIER )


Is that what you want? Perhaps you intend merely


func := IDENTIFIER ( IDENTIFIER )


You state that ID ( ID ) + ID
has the ambiguous possibility
  (a) FUNC expr
  (b) ID expr + expr




It does not seem that way from your posted specification of
'func'. Failing that, 'define' can not engage the 'DEFINE func expr'
production.


So, if you switch to


func := IDENTIFIER ( IDENTIFIER )


(which maybe is what you have had at some point) then you may be able
to get to the ambiguity to which you refer. Pardon me for guessing
here, but what you are possibly doing is experimenting with numerous
alternatives (as we are all wont to do) and posting an approximation
of your most recent trials.


What you posted is not ambiguous. It is simply dysfunctional relative
to your goal. To get 'func', as posted you would have to be trying to
parse input of the form
  ID ID ( ID ) + ID
not just
  ID ( ID ) + ID


If you simplify the 'func' defintion as suggested then it IS
ambiguous. Yacc should complain, and I expect fail, on its inability
to resolve that. It truely is ambiguous. Precedence won't help you
here, because you could only build a single solution, whichever one
had precedence.


However, there are ways out. You could use a disambiguating assignment
symbol, as you do in the text statement "... I would like to mean
sign(x) = +y ...". If you could tolerate that syntax, then there is
no ambiguity.


If you do not like the assignment symbol convention, you could
eliminate ambiguity in front by establishing two different 'define'
keywords: perhaps DEF_FUNC and DEF_IDENT.


Yet another alternative is the use of a second key word for one of the
'define' rules, such as


define -> DEFINE 'FUNCTION' func expr
                    | DEFINE IDENTIFER expr


(ut-oh my FORTRAN is showing again).


and another possibility is the simplification:


define -> FUNCTION func expr
                    | DEFINE IDENTIFER expr




We get into this situation because of the pervasive use of parenthesis
for enclosing both expressions and for function parameter lists and
macro argument lists. This tradition is a tremendous aid to
readability and actually makes coding in popular languages a lot
easier. It also solves myriad precedence and associativity issues. But
with your first projected grammar on this effort, the multi-function
syntax of '(' and ')' are actually creating your problem.


If it is applicable for your purposes, a limitted scope parser might
be able to use some of the other paired ciphers for the function or
macro parameter list enclosing, [ ], { }, or even << >>.


so you might have
func := IDENTIFIER << IDENTIFIER >>


The actual text that you give as an example also suggest another very
difficult problem. If you try to parse parse "define sign (x) +y", and
get it into to 'func' pathway, then you have ". +y" left to parse.


In know that you may have abbreviated your post to help us focus on
the part you think is the issue. But you do not list "+expr" as an
'expr' pattern. And this seems to be the unary operator problem
surfacing.


Have you addressed this elsewhere in your grammar (say, under IDENTIFIER).


Looked at from this perspective, perhaps
"DEFINE func +..." could never be recognized, since no production of 'expr'
seems to start with "+...".


It may be worth consulting the GNU C compiler specification since it
must deal with a virtually identical problem for macro definitions:
where, as you probably know, the syntax is either of ...


#define identifier substitution-text
#define identifier(param-list) substitution-text


Best Wishes,


Robert Rayhawk
RKRayhawk@aol.com

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