The week's pick
Random Articles
Reseach Article
An Implementation of a Fast Threaded Nondeterministic LL(*) Parser Generator
| 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
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
- 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
- Johnson, S.C., “YACC: Yet another compiler compiler”. In UNIX Programmer’s Manual (7th ed.), Volume 2B, 1979.
- 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.
- 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.
- Nozohoor-Farshi, R., “GLR parsing for ɛ-grammars”. In Tomita, M., ed.: Generalized LR Parsing. Kluwer, pp. 61-75, 1991.
- 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.
- Dodd, C., and Maslov, V., “Backtracking Yacc”. http://www.siber.com/btyacc/, last visited on April 3rd 2015.
- Spencer, M., “Basil: A backtracking LR parser generator”. http://www.lazycplusplus.com/basil/, last visited on April 1st 2015.
- Merrill, G. H., “Parsing non-LR(k) grammars with Yacc”. Software, Practice and Experience, 23(8), pp. 829–850, 1993.
- 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.
- 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.
- Parr, T., Fisher, K., “LL(*): the foundation of the ANTLR parser generator”. In Proceedings of PLDI 2011, pp. 425-436, 2011.
- Parr, T., Harwell, S., and Fisher, K., “Adaptive LL(*) parsing: the power of dynamic analysis”. In Proceedings of OOPSLA 2014, pp. 579-598, 2014.
- 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.
- 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.
- Ford, B., “Packrat Parsing: a practical linear-time algorithm with backtracking”. Master’s thesis, Massachusetts Institute of Technology, September 2002.
- 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.
- Grimm, R., "Practical packrat parsing." New York University Technical Report, Dept. of Computer Science, TR2004-854, 2004.
- Redziejowski, R. R., "Parsing expression grammar as a primitive recursive-descent parser with backtracking." Fundamenta Informaticae 79, no. 3, pp. 513-524, 2007.
- Berk, E. J., and Ananian, C. S., "JLex: A lexical analyzer generator for Java (TM)". Department of Computer Science, Princeton University. Version 1, 2005.
- Lea, D. "A Java fork/join framework". In Proceedings of the ACM 2000 conference on Java Grande, pp. 36-43. ACM, 2000.
- Lesk, M. E., “LEX — A Lexical Analyzer Generator”. Computing Science Technical Report 39, Bell Telephone Laboratories, Murray Hill, NJ, 1975.
Index Terms
Keywords