Tunnel Parsing with Ambiguous Grammars

Nikolay Handzhiyski; Elena Somova

doi:10.2478/cait-2023-0012

.blurhash-client-img { display: none !important; }

Tunnel Parsing with Ambiguous Grammars

Cybernetics and Information Technologies

Volume 23 (2023): Issue 2 (June 2023)

By: Nikolay Handzhiyski and Elena Somova

Open Access

|Jun 2023

Abstract

The article proposes an addition to the tunnel parsing algorithm that enables it to parse grammars having countable repetitions and configurations of grammar elements generating empty words without refactoring the grammar. The equivalency of trees built by the use of ambiguous grammar is discussed. The class of the ε-ambiguous grammars is defined as a subclass of the ambiguous grammars relative to these trees. The ε-deterministic grammars are then defined as a subclass of the ε-ambiguous grammars. A technique for linearly parsing on the basis of non-left recursive ε-deterministic grammars with the tunnel parsing algorithm is shown.

References

Tunnel Grammar Studio (Visited on 03.11.2022). https://www.experasoft.com/products/tgs/
Search in Google Scholar Back to article
JavaCC (Visited on 03.11.2022). https://javacc.github.io/javacc
Search in Google Scholar Back to article
ANTLR (Visited on 03.11.2022). https://www.antlr.org/
Search in Google Scholar Back to article
Aho, A. V., J. D. Ullman. Translations on a Context Free Grammar. – Information and Control, Vol. 19, 1971, No 5, pp. 439-475,
Search in Google Scholar Back to article
Reghizzi, S. C., L. Breveglieri, A. Morzenti. Formal Languages and Compilation. Cham, Switzerland, Springer Nature Switzerland AG, 2019.
Search in Google Scholar Back to article
Paull, M. C., S. H. Unger. Structural Equivalence of Context-Free Grammars. – Computer and System Sciences, Vol. 2, 1968, No 4, pp. 427-463.
Search in Google Scholar Back to article
Tomita, M. An Efficient Augmented-Context-Free Parsing Algorithm. – Computational Linguistics, Vol. 13, 1987, No 1-2, pp. 31-46.
Search in Google Scholar Back to article
Aho, A. V., S. C. Johnson. LR Parsing. – ACM Computing Surveys, Vol. 6, 1974, No 2, pp. 99-124.
Search in Google Scholar Back to article
Aho, A. V., S. C. Johnson, J. D. Ullman. Deterministic Parsing of Ambiguous Grammars. – In: Proc. of 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL’73), 1973, pp. 1-21.
Search in Google Scholar Back to article
Kasami, T. An Efficient Recognition and Syntax Analysis Algorithm for Context-Free Languages. – Technical Report, Air Force Cambridge Research Laboratory, Bedford, MA$, 1965.
Search in Google Scholar Back to article
Chomsky, N., M. P. Schützenberger. The Algebraic Theory of Context-Free Languages. – In: P. Braffort, D. Hirschberg, Eds. Studies in Logic and the Foundations of Mathematics. Vol. 35. Elsevier, 1963, pp. 118-161.
Search in Google Scholar Back to article
Handzhiyski, N., E. Somova. Тhe Expressive Power of the Statically Typed Concrete Syntax Trees. – In: CEUR Workshop Proceedings. Vol. 3061. 2021, pp. 136-150.
Search in Google Scholar Back to article
Crocker, D., P. Overell. Augmented BNF for Syntax Specifications: ABNF. Brandenburg Internet Working, 2008.
Search in Google Scholar Back to article
Shaban, M. A Hybrid GLR Algorithm for Parsing with Epsilon Grammars. OpenBU, USA, 1994.
Search in Google Scholar Back to article
Handzhiyski, N., E. Somova. Tunnel Parsing with Counted Repetitions. – Computer Science, Vol. 21, 2020, No 4, pp. 441-462.
Search in Google Scholar Back to article
Handzhiyski, N., E. Somova. A Parsing Machine Architecture Encapsulating Different Parsing Approaches. – International Journal on Information Technologies and Security (IJITS), Vol. 13, 2021, No 3, pp. 27-38.
Search in Google Scholar Back to article
Kyzivat, P. Case-Sensitive String Support in ABNF. Internet Engineering Task Force (IETF), 2014.
Search in Google Scholar Back to article
Holub, A. Compiler Design in C. Prentice Hall, USA, 1990.
Search in Google Scholar Back to article
Sippu, S., E. Soisalon-Soininen. On the Complexity of LL(k) Testing. – Computer and System Sciences, Vol. 26, 1983, No 2, pp. 244-268.
Search in Google Scholar Back to article
Knuth, D. E. On the Translation of Languages from Left to Right. – Information and Control, Vol. 8, 1965, No 6, pp. 607-639.
Search in Google Scholar Back to article
Cohen, R., K. Čulik. LR-Regular Grammars – an Extension of LR(k) Grammar. – Computer and System Sciences, Vol. 7, 1973, No 1, pp. 66-96.
Search in Google Scholar Back to article
Aycock, J., N. Horspool, J. Janoušek, B. Melichar. Even Faster Generalized LR Parsing. – Acta Informatica, Vol. 37, 2001, pp. 633-651.
Search in Google Scholar Back to article
Tomita, M. An Efficient Context-Free Parsing Algorithm for Natural Languages. – In: Proc. of 9th International Joint Conference on Artificial Intelligence, Vol. 2, 1985, pp. 756-764.
Search in Google Scholar Back to article
Woods, W. A. Cascaded ATN Grammars. – Computer Linguistics, Vol. 6, 1980, No 1, pp. 1-12.
Search in Google Scholar Back to article
Dub ìe, D., M. Feeley. Efficiently Building a Parse Tree from a Regular Expression. – Acta Informatica, Vol. 37, 2000, No 2, pp. 121-144.
Search in Google Scholar Back to article
Dub ìe, D., A. Kadiri. Automatic Construction of Parse Trees for Lexemes. – In: Proc. of Scheme and Functional Programming Workshop, 2006, pp. 51-62.
Search in Google Scholar Back to article
Nozohoor-Farshi, R. Handling of Ill-Designed Grammars in Tomita’s Parsing Algorithm. – In: Proc. of 1st International Workshop on Parsing Technologies, 1989, pp. 182-192.
Search in Google Scholar Back to article
Earley, J. An Efficient Context Free Parsing Algorithm. – Communication ACM, Vol. 13, 1970, No 2, pp. 94-102.
Search in Google Scholar Back to article
Nozohoor-Farshi, R. GLR Parsing for ε-Grammers. – In: M. Tomita, Ed. Generalized LR Parsing. Boston, USA, Springer US, 1991, pp. 61-75.
Search in Google Scholar Back to article
Kipps, J. R. Analysis of Tomita’s Algorithm for General Context-Free Parsing. – In: Proc. of 1st International Workshop on Parsing Technologies, 1989, pp. 193-202.
Search in Google Scholar Back to article
Tanaka, H., K. G. Suresh, K. Yamada. A Family of Generalized LR Parsing Algorithms Using Ancestors Table. – IEICE Transactions on Information and Systems, Vol. E77-D, 1994, No 2, pp. 218-226.
Search in Google Scholar Back to article
Tomita, M. Graph-Structured Stack and Natural Language Parsing. – In: Proc. of 26th Annual Meeting on Association for Computational Linguistics, 1988, pp. 249-257.
Search in Google Scholar Back to article
Kipps, J. R. Table Driven Approach to Fast Context-Free Parsing. Rand, USA, 1988.
Search in Google Scholar Back to article
Nederhof, M.-J. Generalized Left-Corner Parsing. – In: Proc. of 6th Conference on European Chapter of the Association for Computational Linguistics, 1993, pp. 305-314.
Search in Google Scholar Back to article
Macedo, J. N., J. Saraiva. Expressing Disambiguation Filters as Combinators. – In: Proc. of 35th Annual ACM Symposium on Applied Computing, 2020, pp. 1348-1351.
Search in Google Scholar Back to article
Nederhof, M.-J., J. J. Sarbo. Increasing the Applicability of LR Parsing. – In: Proc. of 3rd International Workshop on Parsing Technologies, 1993, pp. 187-202.
Search in Google Scholar Back to article
Alonso, M. A., D. Cabrero, M. Vilares. Construction of Efficient Generalized LR Parsers. – In: D. Wood, S. Yu, Eds. Automata Implementation. Berlin, Heidelberg, Germany, Springer, 1998, pp. 7-24.
Search in Google Scholar Back to article
Aycock, J., R. N. Horspool. Practical Earley Parsing. – Computer Journal, Vol. 45, 2002, No 6, pp. 620-630.
Search in Google Scholar Back to article
Tomita, M. Efficient Parsing for Natural Language. New York, USA, Springer, 1986.
Search in Google Scholar Back to article
Scott, E. SPPF-Style Parsing from Earley Recognisers. – Electronic Notes in Theoretical Computer Science, Vol. 203, 2008, No 2, pp. 53-67.
Search in Google Scholar Back to article
Norvig, P. Techniques for Automatic Memoisation with Applications to Context-Free Parsing. – Computational Linguistics, Vol. 17, 1991, No 1, pp. 91-98.
Search in Google Scholar Back to article
Parr, T. J., R. W. Quong. Adding Semantic and Syntactic Predicates to LL(k): Pred-LL(k). – In: P. A. Fritzson, Ed. Compiler Construction. Berlin, Heidelberg, Germany, Springer, 1994, pp. 263-277.
Search in Google Scholar Back to article
Wöß, A., M. Löberbauer, H. Mössenböck. LL(1) Conflict Resolution in a Recursive Descent Compiler Generator. – In: L. Böszörményi, P. Schojer, Eds. Modular Programming Languages. Berlin, Heidelberg, Germany, Springer, 2003, pp. 192-201.
Search in Google Scholar Back to article
Michie, D. “Memo” Functions and Machine Learning. – Nature, Vol. 218, 1968, pp. 19-22.
Search in Google Scholar Back to article
Parr, T., S. Harwell, K. Fisher. Adaptive LL(*) Parsing: The Power of Dynamic Analysis. – ACM SIGPLAN Notices, Vol. 49, 2014, No 10, pp. 579-598.
Search in Google Scholar Back to article
Younger D. H. Recognition and Parsing of Context-Free Languages in Time n3. – Information and Control, Vol. 10, 1967, No 2, pp. 189-208.
Search in Google Scholar Back to article
Nederhof, M.-J., G. Satta. Tabular Parsing. – In: C. Martín-Vide, V. Mitrana, G. Păun, Eds. Formal Languages and Applications. Berlin, Heidelberg, Germany, Springer, 2004, pp. 529-549.
Search in Google Scholar Back to article
Doug, A. Chart Parsing. CiteSeer, 2000, pp. 1-9.
Search in Google Scholar Back to article
Scott, E., A. Johnstone. GLL Parsing. Electronic Notes in Theoretical. – Computer Science, Vol. 253, 2010, No 7, pp. 177-189.
Search in Google Scholar Back to article
Scott, E., A. Johnstone. GLL Parse-Tree Generation. – Science of Computer Programming, Vol. 78, 2013, No 10, pp. 1828-1844.
Search in Google Scholar Back to article
Afroozeh, A., A. Izmaylova. Faster, Practical GLL Parsing. – In: B. Franke, Ed. Compiler Construction. Berlin, Heidelberg, Germany, Springer, 2015, pp. 89-108.
Search in Google Scholar Back to article
Scott, E., A. Johnstone. Structuring the GLL Parsing Algorithm for Performance. – Science of Computer Programming, Vol. 125, 2016, pp. 1-22.
Search in Google Scholar Back to article
Grune, D., C. Jacobs. Parsing Techniques – A Practical Guide. New York, USA, Springer, 2008.
Search in Google Scholar Back to article
Handzhiyski, N., E. Somova. Tunnel Parsing with the Token’s Lexeme. – Cybernetics and Information Technologies, Vol. 22, 2022, No 2, pp. 125-144.
Search in Google Scholar Back to article

Articles in this issue

DOI: https://doi.org/10.2478/cait-2023-0012 | Journal eISSN: 1314-4081 | Journal ISSN: 1311-9702

Journal RSS Feed

Language: English

Page range: 34 - 53

Submitted on: Nov 16, 2022

Accepted on: Apr 18, 2023

Published on: Jun 12, 2023

Published by: Bulgarian Academy of Sciences, Institute of Information and Communication Technologies

In partnership with: Paradigm Publishing Services

Publication frequency: 4 issues per year

Keywords:

Related subjects:

Information technology

© 2023 Nikolay Handzhiyski, Elena Somova, published by Bulgarian Academy of Sciences, Institute of Information and Communication Technologies
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Volume 23 (2023): Issue 2 (June 2023)