Re: [QUERY] A "ignorant newbie" question about compiler-writing.

> Um, it may seem obvious, but it's not. The algorithm I described
> ``taints'' everything that could possibly depend on the first
> erroneous construct, and it refuses to issue error messages about
> tainted things.


While I don't know the details of his work, the basic technique he
describes is valid and has also been used in a production Pascal
compiler. There was a Sigplan article about it several years ago.
The work was done by people at Unisys. They called their tainted
constructs, plastic constructs and a plastic construct was allowed
anywhere any other legal construct was allowed. By construct, I
actuallly mean an internal data structure representing the construct
in a compiler. Thus, for an erroneous variable a plastic symbol node
was created.


It is even possible to imagine using the technique to give better
error diagnostics. For example, take the erroneous variable case.
Since the plastic symbol node would have been used by the compiler
everywhere the erroneous variable was used, it is possible to look at
all uses of the variable, and, if, for example, the variable had been
used consistently as an integer, it would be possible to infer that
the appropriate declaration should have been an integer declaration.


However, the most important thing I remember from the article was a
software engineering principle. Once they had plastic nodes
implemented in their compiler, the most important problem they had to
resolve was the use of internal data structures which were only
partially filled out. This was (still is)? a common problem in
compilers, where some data structure can represent some special case
of an object and only certain of the fields are meaningful in that
case. The common temptation is to only fill in the meaningful fields.
However, when the construct is used erroneously, sometimes those
special nodes can leak out into more general parts of the program,
where the fact that some of the fields are not meaningful is not
recognized. (This can also happen with compiler bugs also.) Of
course, the leaking of these special nodes into unsuspecting parts of
the compiler makes the cascading error problem worse, and is often the
source of compiler crashes.


In any case, they spent a great deal of time, defining all the fields
in all of the data structures of their compiler for all cases, noting
when to mark the field values as plastic (i.e. not meaningful in this
case). They claimed it signficantly improved the robustness of their
compiler.


-Chris
--

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