Re: How do I test my syntax tree classes?

K.V.Rao <kvrao@ARCTIC.WIPSYS.SOFT.NET> wrote:
>I am involved in a compiler project and maily deal with design, implement
>and testing the classes for parse tree that is built while parsing. As a
>parser is involved, does it cause any significant shift the testing process?
>I am using VC++ 2.0/MFC under WinNT. I am using PCYACC and PCLEX for WinNT.
>
>My question is how should I plan my Unit Test Plan and how should design my
>test cases? Any ideas?


At the risk of stating the obvious, here's one of the techniques that
I have used with some success-- write a pretty-printer for your parse
tree objects. This pretty-printer should be able to display every nuance
of the information in each object, but even a relatively simple printer
can have some value.


The output format of the pretty-printer depends on the nature of your
parsing classes. Mine tend to generate stuff that looks like LISP,
but maybe that's just me. For some languages, it might be appropriate
for the output language to be the same as the input, but in my experience,
there's usually a lot more information in the parse tree than is
immediately obvious from the input text. For example, if you've
got the following input (imagining some sort of C-like input language):


{
int a;


a = 2 + 3;
}


then if you can generate this same text, you know that you're at least
doing something right. However, there's probably a *lot* more information
represented in your parse tree, so you probably really want something like:


(+block+
(+variables+
(+integer+ 'a 0))
(+statement+
(+expression+
(+assignment+
'a
(+expression+
(+plus+
(+const-int-expr+ 2)
(+const-int-expr+ 3)))))))


(Note-- I'm just making this structure up off the top of my head, so don't
get flustered if I've forgotten some important detail that the parser
should have recorded in the parse tree.)


Once you've got a pretty printer, then you'll need to choose a test set
of programs that you believe exercise all the aspects of your parser (how
you do this depends on your input language, of course), run them through,
and see if the output corresponds to what you would expect. If it does,
save the output, to use as a regression test later, etc.


-Dan
--


Daniel J. Ellard - ellard2@fas.harvard.edu
--

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