Parsing of Adaptive Star Grammars

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.