A Generic Parser for Strings and Trees

Computer Science and Information Systems

Riad S Jabri¹ 

[1] Computer Science Department, King Abdullah II School for Information Technology

关键词: bottom-up automata;    parsing;    regular tree grammars.;   

DOI  :  10.2298/CSIS101109004J

学科分类：社会科学、人文和艺术（综合）

来源: Computer Science and Information Systems

【 摘 要 】

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.

【 授权许可】

CC BY-NC-ND