Tunnel Parsing with the Token’s Lexeme

Handzhiyski, Nikolay; Somova, Elena

doi:10.2478/cait-2022-0021

Abstract

The article describes a string recognition approach, engraved in the parsers generated by Tunnel Grammar Studio that use the tunnel parsing algorithm, of how a lexer and a parser can operate on the input during its recognition. Proposed is an addition of the augmented Backus-Naur form syntax that enables the formal language to be expressed with a parser grammar and optionally with an additional lexer grammar. The tokens outputted from the lexer are matched to the phrases in the parser grammar by their name and optionally by their lexeme, case sensitively or insensitively.

References

1. 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
2. Unicode Standard. https://www.unicode.org/
Search in Google Scholar Back to article
3. Deremer, F. L. Practical Translators for LR(K) Languages. Massachusetts Institute of Technology, USA, 1969.
Search in Google Scholar Back to article
4. Aho, A., J. Ullman. The Theory of Parsing, Translation, and Compiling. Prentice-Hall, USA, 1972.
Search in Google Scholar Back to article
5. Chomsky, N. Three Models for the Description of Language. – IRE Transactions on Information Theory, Vol. 2, 1956, No 3, pp. 113-124.10.1109/TIT.1956.1056813
Search in Google Scholar Back to article
6. D. Crocker, P. Overell, Eds. ABNF RFC 5234. Network Working Group, 2008.
Search in Google Scholar Back to article
7. Wirth, N. What Can We Do About the Unnecessary Diversity of Notation for Syntactic Definitions? – Communications of the ACM, Vol. 20, 1977, No 11, pp. 822-823.10.1145/359863.359883
Search in Google Scholar Back to article
8. ISO/IEC 14977:1996(E) Information Technology – Syntactic Metalanguage – Extended BNF. http://standards.iso.org/ittf/PubliclyAvailableStandards/
Search in Google Scholar Back to article
9. Dos Reis, A. J. Compiler Construction Using Java, JavaCC, and Yacc. Wiley-IEEE Computer Society Pr, 2011.10.1002/9781118112762
Search in Google Scholar Back to article
10. Moessenboeck, H. Coco/R – A Generator for Fast Compiler Front Ends. Zurich, ETH, 1990.
Search in Google Scholar Back to article
11. Aho, A. V., M. S. Lam, R. Sethi, J. D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley Longman Publishing, Co., USA, 2006.
Search in Google Scholar Back to article
12. Szafron, D., R. Ng. LexAGen: An Interactive Incremental Scanner Generator. – Software: Practice and Experience, Vol. 20, 1990, No 5, pp. 459-483.10.1002/spe.4380200503
Search in Google Scholar Back to article
13. Rabin, M. O., D. S. Scott. Finite Automata and Their Decision Problems. – IBM Journal of Research and Development, Vol. 3, 1959, No 2, pp. 114-125.10.1147/rd.32.0114
Search in Google Scholar Back to article
14. Van Wyk, E. R., A. C. Schwerdfeger. Context-Aware Scanning for Parsing Extensible Languages. – In: Proc. of 6th International Conference on Generative Programming and Component Engineering, October 2007, pp. 63-72.10.1145/1289971.1289983
Search in Google Scholar Back to article
15. Aho, A. V., R. Sethi, J. D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley Longman Publishing, Co., USA, 1986.
Search in Google Scholar Back to article
16. Aycock, J., R. Horspool. Schrödinger’s Token. – Software: Practice and Experience, Vol. 31, 2001, No 8, pp. 803-814.10.1002/spe.390
Search in Google Scholar Back to article
17. Johnson, S. C. YACC: Yet Another Compiler-Compiler. CiteSeer, 2001.
Search in Google Scholar Back to article
18. Saltzer, J. H. Traffic Control in a Multiplexed Computer System. Massachusetts Institute of Technology, USA, 1966.
Search in Google Scholar Back to article
19. Barve, A., B. K. Joshi. Parallel Lexical Analysis of Multiple Files on Multi-Core Machines. – International Journal of Computer Applications, Vol. 96, 2014, No 16, pp. 22-24.10.5120/16879-6879
Search in Google Scholar Back to article
20. Kleene, S. Representation of Events in Nerve Nets and Finite Automata. – Annals of Mathematics Studies, Vol. 34, 1956, pp. 3-41.10.1515/9781400882618-002
Search in Google Scholar Back to article
21. Rus, T., T. Halverson. A Language Independent Scanner Generator. CiteSeer, 1999, pp. 1-35.
Search in Google Scholar Back to article
22. ANTLR. https://www.antlr.org/
Search in Google Scholar Back to article
23. JavaCC. https://javacc.github.io/javacc
Search in Google Scholar Back to article
24. Visser, E. Scannerless Generalized-LR Parsing. University of Amsterdam, Netherlands, 1997.
Search in Google Scholar Back to article
25. Afroozeh, A., A. Izmaylova. One Parser to Rule Them All. – In: ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward!), October 2015, Chicago, USA, pp. 151-170.10.1145/2814228.2814242
Search in Google Scholar Back to article
26. Van den Brand, M., J. Scheerder, J. Vinju, E. Visser. Disambiguation Filters for Scannerless Generalized LR Parsers. – In: Proc. of 11th International Conference of Compiler Construction, April 2002, pp. 1-17.10.1007/3-540-45937-5_12
Search in Google Scholar Back to article
27. Turing, A. On Computable Numbers, with an Application to the Entscheidungs Problem. – In: Proc. of the London Mathematical Society. Vol. 41. 1937, pp. 230-265.10.1112/plms/s2-42.1.230
Search in Google Scholar Back to article
28. Kleene, S. Representation of Events in Nerve Nets and Finite Automata. US Air Forse, USA, 1951.
Search in Google Scholar Back to article
29. Thompson, K. Programming Techniques: Regular Expression Search Algorithm. – Communications of the ACM, Vol. 11, 1968, No 6, pp. 419-422.10.1145/363347.363387
Search in Google Scholar Back to article
30. Kühl, B., A.-T. Schreiner. Objects for Lexical Analysis. – ACM SIGPLAN Notices, Vol. 37, 2002, No 2, pp. 45-52.10.1145/568600.568610
Search in Google Scholar Back to article
31. Saraiva, J. HaLeX: A Haskell Library to Model, Manipulate and Animate Regular Languages. – In: Proc. of ACM Workshop on Functional and Declarative Programming in Education (FDPE/PLI’02), October 2002.
Search in Google Scholar Back to article
32. Brzozowski, J. A. Canonical Regular Expressions and Minimal State Graphs for Definite Events. – In: Proc. of Symposium on Mathematical Theory of Automata, MRI Symposia Series. Vol. 12. 1963, pp. 529-561.
Search in Google Scholar Back to article
33. Revuz, D. Minimisation of Acyclic Deterministic Automata in Linear Time. – Theoretical Computer Science, Vol. 92, 1992, No 1, pp. 181-189.10.1016/0304-3975(92)90142-3
Search in Google Scholar Back to article
34. Berstel, J., L. Boasson, O. Carton, I. Fagnot. Minimization of Automata. – In: Automata: From Mathematics to Applications. European Mathematical Society, 2006.
Search in Google Scholar Back to article
35. Lesk, M., E. Schmidt. Lex – A Lexical Analyzer Generator. 1990.
Search in Google Scholar Back to article
36. Yang, W., C.-W. Tsay, J.-T. Chan. On the Applicability of the Longest-Match Rule in Lexical Analysis. – Computer Languages Systems & Structures, Vol. 28, 2002, No 3, pp. 273-288.10.1016/S0096-0551(02)00014-0
Search in Google Scholar Back to article
37. Handzhiyski, N., E. Somova. Tunnel Parsing with Countable Repetitions. – Computer Science, Vol. 21, 2020, No 4, pp. 441-462.10.7494/csci.2020.21.4.3753
Search in Google Scholar Back to article
38. Van Deursen, A., P. Klint, J. Visser. Domain-Specific Languages. – ACM SIGPLAN Notices, Vol. 35, 2000, No 6, pp. 26-36.10.1145/352029.352035
Search in Google Scholar Back to article
39. Tunnel Grammar Studio. https://www.experasoft.com/products/tgs/
Search in Google Scholar Back to article
40. T. Bray, Ed. The JavaScript Object Notation (JSON) Data Interchange Format. Internet Engineering Task Force (IETF), 2017.10.17487/RFC8259
Search in Google Scholar Back to article
41. T. Berners-Lee, R. Fielding, L. Masinter, Eds. Uniform Resource Identifier (URI): Generic Syntax. Network Working Group, 2005.10.17487/rfc3986
Search in Google Scholar Back to article
42. P. Kyzivat, Ed. Case-Sensitive String Support in ABNF. Internet Engineering Task Force (IETF), 2014.10.17487/rfc7405
Search in Google Scholar Back to article
43. Backus, J. W. The Syntax and Semantics of the Proposed International Algebraic Language of the Zurich ACM-GAMM Conference. – In: IFIP Congress, 1959, pp. 125-132.
Search in Google Scholar Back to article
44. Holub, A. Compiler Design in C. Prentice Hall, USA, 1990.
Search in Google Scholar Back to article