Computer Science and Information Systems 2012 Volume 9, Issue 1, Pages: 381-410
Full text ( 178 KB)
A generic parser for strings and trees
Jabri Riad S.
In this paper, we propose a two fold generic parser. First, it simulates the
behavior of multiple parsing automata. Second, it parses strings drawn from
either a context free grammar, a regular tree grammar, or from both. The
proposed parser is based on an approach that defines an extended version of
an automaton, called positionparsing automaton (PPA) using concepts from LR
and regular tree automata, combined with a newly introduced concept, called
state instantiation and transition cloning. It is constructed as a direct
mapping from a grammar, represented in an expanded list format. However, PPA
is a non-deterministic automaton with a generic bottom-up parsing behavior.
Hence, it is efficiently transformed into a reduced one (RBA). The proposed
parser is then constructed to simulate the run of the RBA automaton on input
strings derived from a respective grammar. Without loss of generality, the
proposed parser is used within the framework of pattern matching and code
generation. Comparisons with similar and well-known approaches, such as LR
and RI, have shown that our parsing algorithm is conceptually simpler and
requires less space and states.
Keywords: bottom-up automata, parsing, regular tree grammars