|
Generalized table-based LL-parsing
S. V. Grigorev, A. K. Ragozina Saint-Petersburg State University, 7-9 Universitetskaya Nab., St. Petersburg 199034, Russian Federation
Abstract:
Syntax analysis is an important step of code analysis. The problem is that the grammars have to be in a form which is deterministic, or at least near-deterministic for the chosen parsing technique. Generalized parsing algorithms — Generalized LR and Generalized LL (GLL) — make it possible to remove these restrictions. Abstract analysis makes it possible to parse embedded languages for supporting them in IDE, reengineering tasks, or finding vulnerabilities (SQL-injection). Abstract syntax analysis is based on the classic table-based analysis. The generalized algorithm of top-down parsing without the use of predictive tables was described earlier in order to extend the class of languages processed by descent analyzers. This paper describes an approach to creation of a table-based GLL-analyzer based on the proposed algorithm, which will be used later for an abstract analyzer. This article describes the algorithm of generalized top-down analysis, its modifications, and the results of comparison with the generalized bottom-up parsing algorithm, which was implemented earlier.
Keywords:
generalized parsing; GLL; RNGLR; abstract parsing; string-embedded languages.
Received: 20.01.2015
Citation:
S. V. Grigorev, A. K. Ragozina, “Generalized table-based LL-parsing”, Sistemy i Sredstva Inform., 25:1 (2015), 89–107
Linking options:
https://www.mathnet.ru/eng/ssi395 https://www.mathnet.ru/eng/ssi/v25/i1/p89
|
Statistics & downloads: |
Abstract page: | 377 | Full-text PDF : | 499 | References: | 51 |
|