Re: need help with labelled graph rewriting

"Uwe Assmann" <>
2 May 1996 23:59:58 -0400

          From comp.compilers

Related articles
need help with labelled graph rewriting (1996-04-29)
Re: need help with labelled graph rewriting (Uwe Assmann) (1996-05-02)
| List of all articles for this month |

From: "Uwe Assmann" <>
Newsgroups: comp.compilers
Date: 2 May 1996 23:59:58 -0400
Organization: Compilers Central
References: 96-04-150
Keywords: analysis, bibliography

>Hi. I have a labelled directed acyclic graph that I want to rewrite.
>The rewrite rules are not context free but can have, potentially,
>infinite lookahead. I plan to implement my parser in Prolog so the
>lookahead is not an issue.

Not sure what you mean by lookahead. Are you trying to rewrite or to parse

>Has anyone else done this? If so, how do you specify the rewriting of
>portions of the sub-graph? Particularly I am interested in specifying
>these types of graph transforamtions.

Rewriting of DAGs is nowadays called 'jungle rewriting' and used in
the (theory of ) implementation of functional languages. See the
following reference:

@InCollection{ sleep.93a,
    booktitle = {Term Graph Rewriting---Theory and Practice},
    editor = {Sleep, M. R. and Plasmeijer, M. J. and van Eekelen, M.
    publisher = {John Wiley and Sons Ltd},
    address = "NewYork",
    year = {1993}

or the recent volumes of the conference 'Graph-theoretic concepts in
Computer Science' which appear every year in the 'Lecture notes of
computer science' volumes, Springer.

I have also been working on rewriting on arbitrary graphs in order to
generate program optimizers. See:

@InProceedings{ assmann.95c,
    author = "A\3mann, Uwe",
    title = "{On Edge Addition Rewrite Systems and Their Relevance to
Program Analysis}",
    editor = "Cuny, J.",
    booktitle = "5th Workshop on Graph Grammars and Their Application To
Computer Science",
    note = "to appear",
    month = "November",
    address = Heidelberg,
    publisher = springer,
    year = "1995"

@InProceedings{ assmann.96a,
    author = "A\3mann, Uwe",
    title = "{How To Uniformly Specify Program Analysis and
    publisher = springer,
    year = 1996,
    booktitle = {Compiler Construction (CC)},
    series = lncs,
    volume = 1060,
    editor = {P. Fritzson},
address = Heidelberg,
    annote = {ua.}

and my thesis (unfortunately in German). It is going to be published in the
next months by GMD as GMD-Bericht.


Uwe Assmann
INRIA Rocquencourt, Bat. 13
Domaine de Voluceau BP 105
78153 Le Chesnay Cedex, France
email: fax: +33/39 63 53 30 tel: +33/1/39 63 53 84

Post a followup to this message

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