Geodesic
A Generic Parser for Strings and Trees
Computer Science and Information Systems, Tome 9 (2012) no. 1.

Voir la notice de l'article provenant de la source Computer Science and Information Systems website

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 position-parsing 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. 
@article{CSIS_2012_9_1_a17,
     author = {Riad S Jabri},
     title = {A {Generic} {Parser} for {Strings} and {Trees}},
     journal = {Computer Science and Information Systems},
     publisher = {mathdoc},
     volume = {9},
     number = {1},
     year = {2012},
     url = {http://geodesic.mathdoc.fr/item/CSIS_2012_9_1_a17/}
}
TY  - JOUR
AU  - Riad S Jabri
TI  - A Generic Parser for Strings and Trees
JO  - Computer Science and Information Systems
PY  - 2012
VL  - 9
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CSIS_2012_9_1_a17/
ID  - CSIS_2012_9_1_a17
ER  - 
%0 Journal Article
%A Riad S Jabri
%T A Generic Parser for Strings and Trees
%J Computer Science and Information Systems
%D 2012
%V 9
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CSIS_2012_9_1_a17/
%F CSIS_2012_9_1_a17
Riad S Jabri. A Generic Parser for Strings and Trees. Computer Science and Information Systems, Tome 9 (2012) no. 1. http://geodesic.mathdoc.fr/item/CSIS_2012_9_1_a17/