1. Performance improvement of stack based recursive-descent parser for parsing expression grammar
Authors : Manish Goswami
Pages : 302-309
Keywords : PEG,Parser,Packrat Abstract :
Recursive Descent parser can be executed in linear time with Packrat parsing method. This is achieved withmemoization technique so that redundant parsing in case of backtracking can be avoided by memorizing all parsing results. But this linear time comes at the cost of large heap consumption in memorization which nullifies its benefits. Due to this developers need to make a difficult choice not to use packrat parsing despite it gives guarantee of linear parsetime.Parsing Expression Grammar relies on a limited backtracking; with language defined in the its way as a sequence of statements. Hence grammar will never return farther back than the starting of current statement. In this paper an idea of extending PEG as a primitive recursive descent parser with backtracking is used by eliminating the procedure calls representing production of grammar by using stack and performed optimization using *and cut operator mainly in addition to other optimizations. Experimental results indeed show a
Citing this Journal Article :Manish Goswami, "Performance improvement of stack based recursive-descent parser for parsing expression grammar", Volume 6 Issue 3 - January 2016, 302-309
Click here to Submit Copyright Takedown Notice for this article.