Tunnel parsing with counted repetitions

• Autorzy: Handzhiyski Nikolay , Somova Elena

Identyfikatory

DOI

10.7494/csci.2020.21.4.3753

• Języki publikacji: EN

Abstrakty

EN

This article describes a new and efficient algorithm for parsing (called tunnel parsing) that parses from left to right on the basis of context-free grammar without left recursion nor rules that recognize empty words. The algorithm is mostly applicable for domain-specific languages. In the article, particular attention is paid to the parsing of grammar element repetitions. As a result of the parsing, a statically typed concrete syntax tree is built from top to bottom, that accurately reflects the grammar. The parsing is not done through a recursion, but through an iteration. The tunnel parsing algorithm uses the grammars directly without a prior refactoring and is with a linear time complexity for deterministic context-free grammars.

Słowa kluczowe

EN

parsing; syntax analysis; parser generator; concrete syntax tree

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2020
• Tom: T. 21 (4)
• Strony: 441--462
• Opis fizyczny: Bibliogr. 36 poz., rys., tab.

Twórcy

autor

Handzhiyski Nikolay

• ExperaSoft UG (haftungsbeschraenkt), 10 Goldasse St., 77652 Offenburg, Germany
• University of Plovdiv “Paisii Hilendarski”, 24 Tzar Assen St., 4000 Plovdiv, Bulgaria

autor

Somova Elena

• University of Plovdiv “Paisii Hilendarski”, 24 Tzar Assen St., 4000 Plovdiv, Bulgaria

Bibliografia

• [1] Abstract Syntax Tree Metamodel. https://www.omg.org/spec/ASTM/. Accessed: 2020-04-14.
• [2] Aho A.V., Lam M.S., Sethi R., Ullman J.D.: Compilers. Principles, Techniques, and Tools (Second Edition), 2007.
• [3] Aho A.V., Johnson S.C.: LR Parsing, ACM Computing Surveys, vol. 6(2), pp. 99–124, 1974. https://doi.org/10.1145/356628.356629
• [4] ANother Tool for Language Recognition (ANTLR). https://www.antlr.org/. Accessed: 2020-04-12.
• [5] Augmented BNF for Syntax Specifications: ABNF. https://tools.ietf.org/html/ rfc5234. Accessed: 2020-04-14.
• [6] Brand van den M.G.J., Scheerder J., Vinju J.J., Visser E.: Disambiguation Filters for Scannerless Generalized LR Parsers. In: Proceedings of the 11th International Conference on Compiler Construction. Springer-Verlag, 2002.
• [7] Brzozowski J.A.: Canonical regular expressions and minimal state graphs for definite events. 1962.
• [8] Case-Sensitive String Support in ABNF. https://tools.ietf.org/html/rfc7405. Accessed: 2020-04-14.
• [9] Chomsky N.: On certain formal properties of grammars, Information and Control, vol. 2(2), pp. 137–167, 1959.
• [10] Copeland T.: Generating Parsers with JavaCC: An Easy-to-Use Guide tor Developers, Centennial Books, 2nd ed., 2007.
• [11] Extensible Markup Language (XML). https://www.w3.org/TR/xml/. Accessed: 2020-04-14.
• [12] Ford B.: Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking. Ph.D. thesis, Massachusetts Institute of Technology, 2002.
• [13] Ford B.: Parsing Expression Grammars: A Recognition-Based Syntactic Foundation, ACM SIGPLAN Notices, vol. 39, pp. 111–122, 2004. https://doi.org/10 .1145/964001.964011.
• [14] Frost R.A., Hafiz R.: A new top-down parsing algorithm to accommodate ambiguity and left recursion in polynomial time, SIGPLAN Notices, vol. 41(5), pp. 46–54, 2006. https://doi.org/10.1145/1149982.1149988.
• [15] Grune D., Jacobs C.J.H.: Parsing Techniques: A Practical Guide, Ellis Horwood, 1990.
• [16] Hopcroft J.E., Ullman J.D.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing Company, 1979.
• [17] ISO/IEC 14977:1996(E) Information technology – Syntactic metalanguage – Extended BNF. http://standards.iso.org/ittf /PubliclyAvailableStandards/. Accessed: 2020-04-14.
• [18] Java Compiler Compiler (JavaCC). https://javacc.org/. Accessed: 2020-04-12.
• [19] Johnstone A., Scott E.: Modelling GLL Parser Implementations. In: Malloy B., Staab S., van den Brand M. (eds.), Software Language Engineering. SLE 2010. Lecture Notes in Computer Science, vol. 6563. Springer, Berlin, Heidelberg, pp. 42–61, 2011.
• [20] Macedo J.N., Saraiva J.: Expressing Disambiguation Filters as Combinators. In: Proceedings of the 35th Annual ACM Symposium on Applied Computing. Association for Computing Machinery, 2020.
• [21] Moore R.C.: Removing Left Recursion from Context-Free Grammars. In: Proceedings of the 1st North American chapter of the Association for Computational Linguistics Conference, 2000.
• [22] Norvig P.: Techniques for automatic memoization with applications to context-free parsing, Computational Linguistics, vol. 17(1), pp. 91–98, 1991.
• [23] Parr T.: Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages (Pragmatic Programmers). Pragmatic Bookshelf, 2010.
• [24] Parr T.: The Definitive ANTLR 4 Reference. Pragmatic Bookshelf, 2nd ed., 2013.
• [25] Rabin M., Scott D.: Finite Automata and Their Decision Problems, IBM Journal of Research and Development, vol. 3(2), pp. 114–125, 1959.
• [26] Saraiva J.: HaLeX: A Haskell Library to Model, Manipulate and Animate Regular Languages. In: Proceedings of the ACM Workshop on Functional and Declarative Programming in Education, University of Kiel Technical Report 0210. 2002.
• [27] Scott E., Johnstone A.: GLL Parsing. In: Electronic Notes in Theoretical Computer Science, vol. 253(7), pp. 177–189, 2010.
• [28] Sipser M.: Introduction to the Theory of Computation. Course Technology, 2nd ed., 2006.
• [29] Spenke M., M¨uhlenbein H., Mevenkamp M., Mattern F., Beilken C.: A language independent error recovery method for LL(1) parsers, Software: Practice and Experience, vol. 14, 1984.
• [30] Succi G., Wong R.W.: The application of JavaCC to develop a C/C++ preprocessor, SIGAPP Applied Computing Review, vol. 7(3), pp. 11–18, 1999.
• [31] The JavaScript Object Notation (JSON) Data Interchange Format. https://tool s.ietf.org/html/rfc7159. Accessed: 2020-04-14.
• [32] Tomita M.: Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems. Kluwer Academic Publishers, 1985.
• [33] Tunnel Grammar Studio. https://www.experasoft.com/products/tgs/. Accessed: 2020-04-14.
• [34] Uniform Resource Identifier (URI): Generic Syntax. https://tools.ietf.org/html/ rfc3986. Accessed: 2020-04-14.
• [35] Zhu Z., Ko H., Zhang Y., Martins P., Saraiva J., Hu Z.: Unifying Parsing and Reflective Printing for Fully Disambiguated Grammars, New Generation Computing, vol. 38, pp. 423–476, 2020.
• [36] Zhu Z., Zhang Y., Ko H.S., Martins P., Saraiva J., Hu Z.: Parsing and reflective printing, bidirectionally. In: Proceedings of the 2016 ACM SIGPLAN International Conference on Software Language Engineering, ACM, 2016.