Re: Tree grammar (Anton Ertl)
12 Dec 1997 14:59:05 -0500

          From comp.compilers

Related articles
Tree grammar (R Venugopal) (1997-12-10)
Re: Tree grammar (1997-12-12)
| List of all articles for this month |

From: (Anton Ertl)
Newsgroups: comp.compilers
Date: 12 Dec 1997 14:59:05 -0500
Organization: TU Wien, Institut fuer Computersprachen
References: 97-12-079
Keywords: architecture, bibliography

R Venugopal <> 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

    author = "Helmut Emmelmann",
    title = "Testing Completeness of Code Selector Specifications",
    crossref = "cc92",
    pages = "163--175"

    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 Most things have to be believed to be seen


Post a followup to this message

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