Re: Q: writing YACC rules

Bert Aerts wrote:
> I'm writing a parser for quite a while now, but everytime I have to
> extend the syntax, I bounce into errors that the parser is reducing my
> token sequences always according to the wrong rule - albeit a rule
> that has a strong resemblence with the correct one.


To which our esteemed moderator suggest the possibility of shift-
reduce or reduce-reduce conflicts.


For a tool like yacc, I would just like to add that, this is one case
to be wary of precedence declarations (left, right, and nonassoc) and
the use of %prec in rules. These declarations hide shift-reduce
conflicts so that you don't even see them, which can cause exactly the
behavior you describe.


If you are using a parser generator like pccts which supports
syntactic predicates, they can have the same effect.


In both cases, you have very blunt and powerful tools that allow you
to tell your parser generator that you know what exactly you are doing
and the generator should take your word for it without comment. If
your grammar isn't parsing what you expect, such a statement is too
strong. I generally recommend removing all such declarations until
the grammar is stablized and you have an exact idea of the language
you are trying to parse.


Your tool should then provide a list of conflicts (or ambiguities)
which you need to resolve. At that point, you can add the appropriate
annotations to get your grammar to "go the right way" at each of the
decision points. Doing that requires learning how to read the output
of your parser generator (be it code, tables, or something else). Or
if you are the more masochistic type, you can rewrite the difficult
sections of your grammar to eliminate the conflicts without the
declarations--although that can be very difficult and result in a
grammar that is too large to be useful.


Even if you already have an existing grammar for the language which
was given to you "tuned" with appropriate declarations that you are
merely adding a "few" features to, it is still worthwhile removing the
declarations at least as an experiment to see what conflicts get
reported.


If your grammar has no precedence declarations and no conflict reports
and it still parses in a way that is counter-intuitive to you, create
the smallest sample case you can that illustrates the problem. Next,
examine the parser output (with any debugging aids your parser
generator supplies enabled) to see if you can determine why the parser
is "thinking" differently than you do. If all else fails, and you
have truly come up with a small case (say, 5 or 6 rules at the most)
plus a short example of input which is misparsed for that grammar that
illustrate your tool misbehaving, then try posting your example.


Either you will have enlightened the rest of us to a subtle point in
practical use or someone will correct your misunderstanding of how the
tool works. In either case, someone will probably have a suggestion
on how to rewrite your grammar in a fail-safe manner.


-Chris Clark
************************************************************************
Compiler Resources, Inc. email: cfc@world.std.com
3 Proctor St. http://world.std.com/~compres
Hopkinton, MA 01748 phone: (508) 435-5016
USA 24hr fax: (508) 435-4847
[I agree. In "lex&yacc" I tell people to use precedence declarations
only to resolve expression grammar and if/else conflicts. Anything else
is too likely to produce unexpected results. -John]
--

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