A new parsing scheme for plex grammars

摘要

Plex structures specified by plex grammars are sets of symbols which interconnect in multidirection. We propose a new parsing scheme for plex grammars, which consists of two phases for symbols and their interconnections respectively in an input plex structure. The parsing of plex structures is simplified by our parsing scheme, because we are required to parse only a set of symbols instead of a plex structure. Algorithms for the first phase are primarily discussed in this paper. Earley's algorithm is extended to recognize a set of symbols. It is anticipated that the two-phase scheme of parsing may suggest a method for the parsing of other high-dimensional pattern grammars.