Re: Tree grammar

R Venugopal <venug@sasi.com> writes:
> Do you know of any systematic procedure to write the
> production rules of a tree grammar which specifies the instructions of
> a new processor? It is intended that these production rules be used
> as input by a tree pattern matching generator such as iburg to produce
> a code selector for the processor. Also, is there any technique for
> proving the soundness and completeness of the specified grammar with
> respect to the architecture considered?


Usually you will have a nonterminal (e.g., "reg"), from which you can
derive all other nonterminals via chain rules, and which can be
derived from the start nonterminal. In this case a systematic and
complete way to write a tree grammar is this: for all operators, have
a rule of the form


nonterm: Op(reg,reg) #for binary operators
nonterm: Op(reg) #for unary operators
nonterm: Op #for terminals


Of course you also need the chain rules for deriving "reg" from the
other nonterminals.


Once you have this complete grammar, you cann add more rules without
losing completeness.


As for proving soundness, you would have to check the tree grammar
against a machine description that is usually very similar to the tree
grammar, and you would have to prove the soundness of that machine
description. This does not look like a useful approach to me (unless
your tree grammar is unusually complex).


I would rather do an end-to-end test, i.e., have a set of trees that
exercise all rules in the tree grammar (at least), and sets of inputs
and expected outputs for the expressions represented by the tree. This
allows you to test your tree grammar and the assembler.


If my discussion above was a bit too superficial for your taste, you
may want to read


@InProceedings{emmelmann92,
    author = "Helmut Emmelmann",
    title = "Testing Completeness of Code Selector Specifications",
    crossref = "cc92",
    pages = "163--175"
}


@Proceedings{cc92,
    booktitle = "Compiler Construction (CC'92)",
    title = "Compiler Construction (CC'92)",
    key = "CC'92",
    year = "1992",
    publisher = "Springer LNCS~641",
    address = "Paderborn",
}


- anton
--
M. Anton Ertl Some things have to be seen to be believed
anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html




--

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