Computer Science and Information Systems | |
A Generic Parser for Strings and Trees | |
Riad S Jabri1  | |
[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
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO201904023906296ZK.pdf | 507KB | download |