Parsing of Adaptive Star Grammars

Mark Minas

Abstract


In a recent paper, adaptive star grammars have been proposed as an
extension of node and hyperedge replacement grammars. A
rule in an adaptive star grammar is actually a rule schema which, via the
so-called cloning operation, yields a potentially infinite number of
concrete rules. Adaptive star grammars are motivated by application areas
such as modeling and refactoring object-oriented programs, and they are more
powerful than node and hyperedge replacement grammars by this mechanism. It
has been shown that the membership problem is decidable for a reasonably
large subclass of adaptive star grammars, however no parser has been
proposed. This paper describes such a parser for this subclass motivated by
the well-known string parser by Cocke, Younger, and
Kasami.

Full Text:

PDF


DOI: http://dx.doi.org/10.14279/tuj.eceasst.4.17

DOI (PDF): http://dx.doi.org/10.14279/tuj.eceasst.4.17.8

Hosted By Universit├Ątsbibliothek TU Berlin.