existential yacc question (spoiler)

I came across an interesting yacc problem, due to the differences in
the error handling between berkeley yacc and at&t yacc. I had looked
here for answers and, finding none, figured I should provide one.


The existential question is: if you have something that can't reduce
empty but can reduce as an error, and that something is missing from
the input stream, is it really there? That it, does yacc reduce that
something as an error and then shift the parent rule, or does it fail
the parent rule because that something is missing?


An example helps: you have a "program":


program : program statement
| statement
| error
;


and "statement":


statement : (a variety of possibilities)
| BEGIN program END
;


And you see the input:


BEGIN END


Does the "program" between BEGIN and END reduce as an error, and the
resulting "program" get shifted in the "statement" rule, or does the
"statement" rule get an error because the "program" is missing?


The answer depends on whether you're using the AT&T yacc or the Berkeley
yacc: the AT&T yacc, being a procedural beast, goes and reduces "program"
as an error. The Berkeley yacc, being table driven and more direct,
just finds an error in the surrounding "statement".


So beware if you ever move a large grammar among yaccs. This one will
bite your ankles!


Christopher
----
Christopher Seiwald Perforce Software 1-510-864-7400
seiwald@perforce.com f-f-f-fast SCM http://www.perforce.com
[Many versions of AT&T yacc have a bug in handling error rules, and this
sounds like it. -John]




--

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