1. bookVolume 22 (2022): Edizione 2 (June 2022)
Dettagli della rivista
Prima pubblicazione
13 Mar 2012
Frequenza di pubblicazione
4 volte all'anno
Accesso libero

Tunnel Parsing with the Token’s Lexeme

Pubblicato online: 23 Jun 2022
Volume & Edizione: Volume 22 (2022) - Edizione 2 (June 2022)
Pagine: 125 - 144
Ricevuto: 17 Jan 2022
Accettato: 12 Apr 2022
Dettagli della rivista
Prima pubblicazione
13 Mar 2012
Frequenza di pubblicazione
4 volte all'anno

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.


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

2. Unicode Standard. https://www.unicode.org/ Search in Google Scholar

3. Deremer, F. L. Practical Translators for LR(K) Languages. Massachusetts Institute of Technology, USA, 1969. Search in Google Scholar

4. Aho, A., J. Ullman. The Theory of Parsing, Translation, and Compiling. Prentice-Hall, USA, 1972. Search in Google Scholar

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

6. D. Crocker, P. Overell, Eds. ABNF RFC 5234. Network Working Group, 2008. Search in Google Scholar

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

8. ISO/IEC 14977:1996(E) Information Technology – Syntactic Metalanguage – Extended BNF. http://standards.iso.org/ittf/PubliclyAvailableStandards/ Search in Google Scholar

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

10. Moessenboeck, H. Coco/R – A Generator for Fast Compiler Front Ends. Zurich, ETH, 1990. Search in Google Scholar

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

12. Szafron, D., R. Ng. LexAGen: An Interactive Incremental Scanner Generator. – Software: Practice and Experience, Vol. 20, 1990, No 5, pp. 459-483. Search in Google Scholar

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

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

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

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

17. Johnson, S. C. YACC: Yet Another Compiler-Compiler. CiteSeer, 2001. Search in Google Scholar

18. Saltzer, J. H. Traffic Control in a Multiplexed Computer System. Massachusetts Institute of Technology, USA, 1966. Search in Google Scholar

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

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

21. Rus, T., T. Halverson. A Language Independent Scanner Generator. CiteSeer, 1999, pp. 1-35. Search in Google Scholar

22. ANTLR. https://www.antlr.org/ Search in Google Scholar

23. JavaCC. https://javacc.github.io/javacc Search in Google Scholar

24. Visser, E. Scannerless Generalized-LR Parsing. University of Amsterdam, Netherlands, 1997. Search in Google Scholar

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

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

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

28. Kleene, S. Representation of Events in Nerve Nets and Finite Automata. US Air Forse, USA, 1951. Search in Google Scholar

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

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

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

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

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

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

35. Lesk, M., E. Schmidt. Lex – A Lexical Analyzer Generator. 1990. Search in Google Scholar

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

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

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

39. Tunnel Grammar Studio. https://www.experasoft.com/products/tgs/ Search in Google Scholar

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

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

42. P. Kyzivat, Ed. Case-Sensitive String Support in ABNF. Internet Engineering Task Force (IETF), 2014.10.17487/rfc7405 Search in Google Scholar

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

44. Holub, A. Compiler Design in C. Prentice Hall, USA, 1990. Search in Google Scholar

Articoli consigliati da Trend MD

Pianifica la tua conferenza remota con Sciendo