CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

An Implementation of a Fast Threaded Nondeterministic LL(*) Parser Generator

by Amr M. AbdelLatif, Amr Kamel, Reem Bahgat
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 130 - Number 5
Year of Publication: 2015
Authors: Amr M. AbdelLatif, Amr Kamel, Reem Bahgat
10.5120/ijca2015906976

Amr M. AbdelLatif, Amr Kamel, Reem Bahgat . An Implementation of a Fast Threaded Nondeterministic LL(*) Parser Generator. International Journal of Computer Applications. 130, 5 ( November 2015), 30-37. DOI=10.5120/ijca2015906976

@article{ 10.5120/ijca2015906976,
author = { Amr M. AbdelLatif, Amr Kamel, Reem Bahgat },
title = { An Implementation of a Fast Threaded Nondeterministic LL(*) Parser Generator },
journal = { International Journal of Computer Applications },
issue_date = { November 2015 },
volume = { 130 },
number = { 5 },
month = { November },
year = { 2015 },
issn = { 0975-8887 },
pages = { 30-37 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume130/number5/23207-2015906976/ },
doi = { 10.5120/ijca2015906976 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:24:34.890754+05:30
%A Amr M. AbdelLatif
%A Amr Kamel
%A Reem Bahgat
%T An Implementation of a Fast Threaded Nondeterministic LL(*) Parser Generator
%J International Journal of Computer Applications
%@ 0975-8887
%V 130
%N 5
%P 30-37
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Parsers are used in many applications such as compilers, NLP and other applications. Parsers that are developed by hand are a complex task and require a generator to automatically generate the parser. The generator reads a grammar and generates a fully working parser. This paper proposes separating the semantic actions’ execution from the parsing phase. The parser generates a queue of semantic actions attached with grammar rules to be visited in case of successful parsing. By this separation, the execution time of the parsing phase can be enhanced. More importantly, this will avoid the incorrect execution of semantic actions when dealing with non-deterministic grammars. Investigating an implementation for the parallelization of the parsing phase for non-deterministic rules is also another contribution of the paper. A previous theoretical work of this paper was made in [1]. The experimental work shows that working with single threaded backtracking with storage of intermediate results, as well as following the Fork/Join parallel execution model without intermediate storage perform in most cases better than working with raw threads execution or by predicting rules as in ANTLR V4. The generator assumes that the grammar is left-recursive free.

References
  1. Amr M., Amr K., Reem B.,”TGLL: A Fast Threaded Nondeterministic LL(*) Parsing”. ARPN journal of systems and software, VOL. 5, NO. 2, August 2015
  2. Johnson, S.C., “YACC: Yet another compiler compiler”. In UNIX Programmer’s Manual (7th ed.), Volume 2B, 1979.
  3. Donnelly, C., Stallman, R.M., “Bison: the YACC-compatible Parser Generator”. Bison Version 1.28. Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, 1999.
  4. Appel, A. W., Flannery, F., and Hudson, S. E., “CUP parser generator for Java”. http://www2.cs.tum.edu/projects/cup/,1999, Last visited on March 4th 2015.
  5. Nozohoor-Farshi, R., “GLR parsing for ɛ-grammars”. In Tomita, M., ed.: Generalized LR Parsing. Kluwer, pp. 61-75, 1991.
  6. McPeak, S., and Necula, G. C., “Elkhound: A fast, practical GLR parser generator”. In Proc. Of 13th International Conference on Compiler Construction, vol. 2985 of LNCS, Springer, pp. 73-88, 2004.
  7. Dodd, C., and Maslov, V., “Backtracking Yacc”. http://www.siber.com/btyacc/, last visited on April 3rd 2015.
  8. Spencer, M., “Basil: A backtracking LR parser generator”. http://www.lazycplusplus.com/basil/, last visited on April 1st 2015.
  9. Merrill, G. H., “Parsing non-LR(k) grammars with Yacc”. Software, Practice and Experience, 23(8), pp. 829–850, 1993.
  10. Thurston, A. D., and Cordy, J. R, “A backtracking LR algorithm for parsing ambiguous context-dependent languages”. In Proceedings of the 2006 conference of the Center for Advanced Studies on Collaborative research, October 16-19, 2006, Toronto, Ontario, Canada.
  11. Mössenböck, H., Löberbauer, M., and Wöß, A., “The Compiler Generator Coco/R”. http://www.ssw.uni-linz.ac.at/Coco/, last visited April 2nd, 2015.
  12. Parr, T., Fisher, K., “LL(*): the foundation of the ANTLR parser generator”. In Proceedings of PLDI 2011, pp. 425-436, 2011.
  13. Parr, T., Harwell, S., and Fisher, K., “Adaptive LL(*) parsing: the power of dynamic analysis”. In Proceedings of OOPSLA 2014, pp. 579-598, 2014.
  14. Viswanadha, S., Sankar, S., and Dunkan, R., "Java compiler compiler (JavaCC)-The java parser generator." Java.net, https://javacc.java.net/, last visited Aug 2 2015.
  15. Ford, B., “Parsing Expression Grammars: a Recognition-Based Syntactic Foundation”. In POPL ’04: Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of Programming Languages, pp. 111–122, New York, NY, USA, 2004. ACM Press.
  16. Ford, B., “Packrat Parsing: a practical linear-time algorithm with backtracking”. Master’s thesis, Massachusetts Institute of Technology, September 2002.
  17. Ford, B., “Packrat parsing: Simple, powerful, lazy, linear time”. In Proceedings of the 2002 ACM International Conference on Functional Programming, pp. 36–47, Pittsburgh, Pennsylvania, Oct. 2002.
  18. Grimm, R., "Practical packrat parsing." New York University Technical Report, Dept. of Computer Science, TR2004-854, 2004.
  19. Redziejowski, R. R., "Parsing expression grammar as a primitive recursive-descent parser with backtracking." Fundamenta Informaticae 79, no. 3, pp. 513-524, 2007.
  20. Berk, E. J., and Ananian, C. S., "JLex: A lexical analyzer generator for Java (TM)". Department of Computer Science, Princeton University. Version 1, 2005.
  21. Lea, D. "A Java fork/join framework". In Proceedings of the ACM 2000 conference on Java Grande, pp. 36-43. ACM, 2000.
  22. Lesk, M. E., “LEX — A Lexical Analyzer Generator”. Computing Science Technical Report 39, Bell Telephone Laboratories, Murray Hill, NJ, 1975.
Index Terms

Computer Science
Information Sciences

Keywords

Non-deterministic grammar LL grammar and compilers

Powered by PhDFocusTM