Re: need help with labelled graph rewriting

>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
graphs?


>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.
C.},
    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",
series=lncs,
    month = "November",
    address = Heidelberg,
    publisher = springer,
    year = "1995"
}


@InProceedings{ assmann.96a,
    author = "A\3mann, Uwe",
    title = "{How To Uniformly Specify Program Analysis and
Transformation}",
    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.


Regards
Uwe


--------------------------------------------------------------
Uwe Assmann
INRIA Rocquencourt, Bat. 13
Domaine de Voluceau BP 105
78153 Le Chesnay Cedex, France
email: Uwe.Assmann@inria.fr fax: +33/39 63 53 30 tel: +33/1/39 63 53 84
http://www-rocq.inria.fr/~assmann
--

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