Systems and Means of Informatics
2015, Volume 25, Issue 1, pp 89-107
GENERALIZED TABLE-BASED LL-PARSING
- S. V. Grigorev
- A.K. Ragozina
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.
[+] References (18)
- Kyung-Goo, D., K. Hyunha, and D.A. Schmidt. 2009. Abstract parsing: Static
analysis of dynamically generated string output using LR-Parsing technology. 16th
Symposium (International) on Static Analysis Proceedings. Berlin: Springer-Verlag.
256-272.
- YaccConstructor. Available at: http://yaccconstructor.github.io/YaccConstructor/
(accessed February 03, 2015).
- Scott, E., and A. Johnstone. 2006. Right nulled GLR parsers. ACM Trans. Program.
Lang. Syst. 28(4):577-618. doi: 10.1145/1146809.1146810.
- Grigoriev, S.V., and I.A. Kirilenko. 2013. GLR-based abstract parsing. 9th Central
& Eastern European Software Engineering Conference in Russia Proceedings. New
York, NY, USA. Article No. 5. 1-9.
- Rosenkrantz, D. J., and R. E. Stearns. 1969. Properties of deterministic top down
grammars. 1st Annual Symposium on Theory of Computing Proceedings. New York,
NY, USA: ACM. 165-180.
- Aho, A.V., M. S. Lam, R. Sethi, and J.D. Ullman. 2006. Compilers: Principles,
techniques, and tools. 2nd ed. Boston: Addison-Wesley Longman Publs. Co., Inc.
1184 p.
- Nederhof,M.-J., and J. J. Sarbo. 1993. Increasing the applicability of LR parsing. 3rd
Workshop (International) on Parsing Technologies. Tilburg. 187-201.
- Scott, E., and A. Johnstone. 2010. GLL parsing. Electronic Notes Theoretical Com-
puter Sci. 253(7):177-189. doi: 10.1016/j.entcs.2010.08.041.
- Tomita, M. 1985. Efficient parsing for natural language: A fast algorithm for practical
systems. Norwell: Kluwer Academic Publs. 201 p.
- ANTLR. Available at: http://www.antlr.org/ (accessed February 03, 2015).
- Scott, E., and A. Johnstone. 2005. Generalized bottom up parsers with reduced stack
activity. Comput. J. 48(5):565-587. doi: 10.1093/comjnl/bxh102.
- Scott, E., A. Johnstone., and R. Economopoulos. 2007. BRNGLR: A cubic Tomita-
styleGLR parsing algorithm. Acta Inform. 44(6):427-461. doi: 10.1007/s00236-007-
0054-z.
- Rekers, J.G. 1992. Parser generation for interactive environments. Amsterdam: Uni-
versty of Amsterdam. PhD Thesis. 174 p.
- Scott, E., and A. Johnstone. 2013. GLL parse-tree generation. Sci. Comput. Program.
78(10):1828-1844. doi: 10.1016/j.scico.2012.03.005.
- Johnstone, A., and E. Scott. 2010. Modelling GLL parser implementations. 3rd
Conference (International) on Software Language Engineering. Berlin: Springer-
Verlag. 42-61.
- Syme, D., A. Granicz, and A. Cisternino. 2007. Expert F#. New York, NY, USA:
Apress. 609 p.
- Economopoulos,R.G. 2006.Generalised LR parsing algorithms. London: Department
of Computer Science, Royal Holloway, University of London. PhD Thesis. 232 p.
- Verbitskaya, E.A. 2014. Diagnostika oshibok pri analize vstroennykh yazykov [Er-
ror detection in string-embedded languages]. St. Petersburg: Saint-Petersburg State
University. Course work. 18 p.
[+] About this article
Title
GENERALIZED TABLE-BASED LL-PARSING
Journal
Systems and Means of Informatics
Volume 25, Issue 1, pp 89-107
Cover Date
2013-11-30
DOI
10.14357/08696527150106
Print ISSN
0869-6527
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
generalized parsing; GLL; RNGLR; abstract parsing; string- embedded languages
Authors
S. V. Grigorev  and A.K. Ragozina
Author Affiliations
Saint-Petersburg State University, 7-9 Universitetskaya Nab., St. Petersburg 199034, Russian Federation
|