Re: Q: writing YACC rules

Chris Clark USG wrote:
> 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.


Not quite -- synpreds provide an additional check; they don't hush
warnings.


What's happenning is that the normal check for lookahead is performed
(which was ambiguous with some other alternative, hence the need for the
synpred), _then_ the synpred is "attempted". If the attempt succeeds,
the alt is followed; otherwise, the next alt that matches the lookahead
prediction is attempted.


Kinda like backtracking in some ways, but we like to call it "guess
mode" or "inifinite lookahead".


ANTLR 2.x now has an option to hush ambiguities (like if-else) though I
caution folks to use it with great care (otherwise it will turn into
%prec in yacc, where many inexerienced grammar writers just start
slapping it everywhere to hush warnings...)


> 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


Not realy true. Yes, synpreds will hush ambig warnings, but you're not
just saying "trust me"; you're telling ANTLR/PCCTS _how_ to add a check
that will really resolve the ambiguity at runtime.


I definitely agree with your statement that when writing a grammar one
should first try to remove ambiguities before using %PREC in Yacc or
predicates in ANTLR/PCCTS. Not only will you have a more correct and
simpler grammar (at least by my def of simpler...) but it will be more
efficient.


> 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.


Definitely. Grammar maintenance can be a huge nightmare, as a single
rule could introduce several conflicts.


I always suggest that whenever you're done with grammar edits, comment
ambiguities LIKE CRAZY in the grammar, _including_ places that you
"hush" or add predicates.


Then the maintainer should, as you suggest, comment out the "hushers",
add new rules or edit existing ones, and see if any new ambigs are
introduced.


If comments aren't there, I'd suggest that the _first_ thing a
maintainer do is comment out the "hushers" and generate, noting
ambiguities and trying to understand why they're there. Then make
changes.


(Of course when I usually inherit a grammar, the first thing I try to do
is cleanup silly ambiguities. There seem to be few folks who really
understand how to write grammars well.)


> Next,
> examine the parser output (with any debugging aids your parser
> generator supplies enabled)


While you mention this, keep an eye out for ANTLR 2.4.0. Ter's out of
town right now, but when he gets back in mid-sept he'll be finishing it
and releasing it.


ANTLR 2.4.0 contains my visual parser debugger, ParseView (see
http://www.jguru.com/thetick/parseview) which can help this effort
immensely.


With something like ParseView, you don't really even need to narrow down
the test case much... (In a later release I'll support breakpoints so
you can break on certain rule matches and such, as well as breaking when
you hit a certain source-line number).


-- Scott


Scott Stanchfield Santa Cruz, CA USA
    thetick@magelang.com http://www.jguru.com/thetick


MageLang Institute http://www.MageLang.com
    "We serve the best Java Education!"


VisualAge for Java Tips and Tricks
    http://www.jguru.com/thetick/visualage/tips
--

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