Yacc parsers: Cleaning up the wreckage!

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


S
|
+a-_d
|
+_b
|
+c-_f


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
eg:


ambient_statement : _ambient colour_statement
{
  $$:=$2;
}


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
this??


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

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