A Generic Parser for Strings and Trees

Riad S Jabri1

  1. Computer Science Department, King Abdullah II School for Information Technology
    University of Jordan, Amman 11942 –Jordan
    jabri@ju.edu.jo

Abstract

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.

Key words

bottom-up automata, parsing, regular tree grammars.

Digital Object Identifier (DOI)

https://doi.org/10.2298/CSIS101109004J

Publication information

Volume 9, Issue 1 (January 2012)
Year of Publication: 2012
ISSN: 1820-0214 (Print) 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable in PDF
Portable Document Format

How to cite

Jabri, R. S.: A Generic Parser for Strings and Trees. Computer Science and Information Systems, Vol. 9, No. 1, 381-410. (2012)