Yacc parsers: Cleaning up the wreckage!

mch24@harvey27.demon.co.uk (Martin Harvey)
16 Aug 1997 00:21:20 -0400

          From comp.compilers

Related articles
Yacc parsers: Cleaning up the wreckage! mch24@harvey27.demon.co.uk (1997-08-16)
Re: Yacc parsers: Cleaning up the wreckage! dwight@pentasoft.com (Dwight VandenBerghe) (1997-08-19)
Re: Yacc parsers: Cleaning up the wreckage! armbru@pond.sub.org (Markus Armbruster) (1997-08-20)
Re: Yacc parsers: Cleaning up the wreckage! mch24@harvey27.demon.co.uk (1997-08-24)
| List of all articles for this month |

From: mch24@harvey27.demon.co.uk (Martin Harvey)
Newsgroups: comp.compilers
Date: 16 Aug 1997 00:21:20 -0400
Organization: Compilers Central
Keywords: yacc, errors, comment

Hello all,

I've just written my first Yacc parser, and am very satisfied with the
results. However, I have a problem with error recovery. I'm not
worried (for the moment) about reporting multiple errors, and I'm
quite happy for the parser to give up on the first error. However, I'm
finding it more difficult to work out how to clean up the partial
syntax tree that is generated during an error. For example:

S : a _b c | a _b ;

a : _d ;

c : _d | e ;

e : _f ;

where S is the Sentence, _b, _d, _f are terminals and a, c and e are
non terminals.

If this correctly parsed, then we might have a syntax tree that looked
something like this (assuming suitable code to build this).


however, if we have an error in our parse (let's say that the rule e :
_f ; fails because the terminal _f is not encountered) then a, _b (or
their representative equivalents) will have been created, and put on
the parser stack (array of yysType) in order that they might be joined
onto c,_f and S into a final tree.

However, the parser is bottom up, and as a result of the failure of
rule e:_f then c,_f and S will not have been created and the parser
will abort. This now means that I have a whole load of allocated
objects on the parser stack, and no syntax tree at all :-(

How on earth do I go about clearing up?? I suspect I need to comb
through the parser stack finding all the parts of the syntax tree and
deallocating them. However, this presents problems for me:

Some parts of the gramar I am using equate one non terminal to another

ambient_statement : _ambient colour_statement

This is simply in order to avoid shift-reduce conflicts.

This means that I may have two entries in the stack pointing to the
same object. As a result of this, if I just try to go up the stack
calling destructors on every object found, I'm very likely to try to
destroy the same object twice, with rather nasty consequences.

What methods are there for picking up the pieces in situations like

Many thanks.

Martin Harvey
Uni web pages: http://www-stu.pem.cam.ac.uk/~mch24/
[Yacc isn't very helpful there, is it? I usually use my own malloc()
wrapper than chains together the space it allocates so I can run down the
chain and free everything after the parse completes one way or the other.

Post a followup to this message

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