Re: ensuring full semantic checker coverage?

Quinn Tyler Jackson wrote:
>
> Ross Bencina said:
>
> > My current plan is to build a database (some sort of tagged
> > textfile) with separate items for each assertion that the checker
> > must test, give each of these assertions an ID, then embed these IDs
> > in comments with the source code that implements each check. That
> > way I can write a script that crossreferences every required check
> > to the code that performs it. Perhaps the error message text for
> > each check might also form part of this approach.
>
> That would formally guarantee that you've written the code to do the
> required checks, but unless I'm mistaken, it would then require flow
> analysis of the code that reaches the code that contains the checks to
> determine that those checks are actually executed, which, of course,
> would leave you with something that is undecidably correct.


If I go as far as David Chase suggested and embed these IDs in the
compiler output, and in an optional trace log, then I should be able
to write a suite of test inputs that excercises all paths (at least in
isolation), and verify that the correct tests/errors have been raised
by comparing expected output IDs with the trace and error logs. I can
think of a good way to automate such tests within my error logging
framework


> I assume that not all of the checks apply to all of the code under
> consideration for verification, and that the semantic checks occur in
> grouped clusters. (For instance, code block A would have a proscribed
> set of semantic checks, code B another, possibly different set, and so
> on.) Thus, the checks that are required to be applied to any block of
> source would depend on the source itself.


That's correct. There are various checks (about 100 at last count),
which pertain to different subexpression and statement types. In many
cases checks are clustered around a node type in the AST
(BinaryOperator, or NullAssignment for example). Other checks relate
to global information that can only be deduced examining the program
as a whole - these global checks are more of a concern than the
localised checks - but perhaps that's just because I don't yet
understand the global semantics of the target language quite as well
as I understand the local semantics.




> My suggestion would be to annotate the tree with a set of semantic
> checking attributes, where each node would be decorated such that its
> decorations would indicate which checks are required on that node.
> Then, after decoration, semantic checking visitors would traverse the
> tree, flagging as completed those checks that pass muster. A final
> visitation on each node to verify that all semantic decorations have
> been processed and accepted would then tell you with some certainty
> that all proscribed semantic checks had been applied. This method
> would scale to more checks in future, and would keep the semantic
> checking code in its own sandbox, apart from lexing, parsing,
> optimizing, and other code.


At present I have already partitioned the parsing from the semantic
checking. The parser builds a heterogeneous C++ AST data structure and
I use the (somewhat dubious) Visitor design pattern as a basis for
classes that visit the AST. Visitors have separate functions for each
node type, so it's guaranteed that if a function that checks a node of
a specific type is called, it knows which checks need to be performed
on that node. As part of semantic checking I plan to annotate the AST
with derived type information which will be used by a later visitor to
generate the intermediate representation. Your suggestion of marking
the nodes once they've been checked would provide a good way to verify
that all nodes have been visited.


Best wishes


Ross.

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