Relaxed Parsing of Regular Approximations of String-Embedded Languages

P. 291–302.

Verbitskaia E., Grigorev S., Avdyukhin D.

We present a technique for syntax analysis of a regular set of input strings. This problem is relevant for the analysis of string-embedded languages when a host program generates clauses of embedded language at run time. Our technique is based on a generalization of RNGLR algorithm, which, inherently, allows us to construct a finite representation of parse forest for regularly approximated set of input strings. This representation can be further utilized for semantic analysis and transformations in the context of reengineering, code maintenance, program understanding etc. The approach in question implements relaxed parsing: non-recognized strings in approximation set are ignored with no error detection.

Keywords: parsing, parser generator, string analysis, string-embedded languages

In book

Perspectives of System Informatics 10th International Andrei Ershov Informatics Conference, PSI 2015, in Memory of Helmut Veith, Kazan and Innopolis, Russia, August 24-27, 2015, Revised Selected Papers

Cham: Springer, 2015.