Volume 6 Issue 3 - January 2016

  • 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", https://www.ijltet.org/journal_details.php?id=898&j_id=2858, Volume 6 Issue 3 - January 2016, 302-309, #ijltetorg