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.