A Comparison Between Packrat Parsing and Conventional Shift-Reduce Parsing on Real-World Grammars and Inputs
Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
Packrat parsing is a top-down, recursive descent parsing technique that uses backtracking and has a guaranteed linear parse time. Conventional backtracking parsers suffer from exponential parse times in the worst case due to re-evaluating redundant results. This is avoided in packrat parsers with the use of memoization. However, memoization causes packrat parsers memory consumption to be linearly proportional to the input string, as opposed to linearly proportional to the maximum recursion depth for conventional parsing techniques.
The objective of this thesis is to implement a packrat parser generator and compare it with an existing and well-known parser combination called Lex/Yacc which produces shift-reduce parsers. The comparison will consist of pure performance measurements such as memory consumption and parsing time, and also a more general comparison between the two parsing techniques.
The conclusion made from the comparison is that packrat parsing can be a viable option due to its ability to compose modular and extendible grammars more easily than Lex/Yacc. However, from a performance perspective the Lex/Yacc combination proved superior. In addition, the results indicate that similar performance for a packrat parser is hard to achieve on grammars similar to those used in this thesis.
Place, publisher, year, edition, pages
UPTEC IT, ISSN 1401-5749 ; 14 016
Engineering and Technology
IdentifiersURN: urn:nbn:se:uu:diva-233403OAI: oai:DiVA.org:uu-233403DiVA: diva2:752340
Master of Science Programme in Information Technology Engineering
Eriksson, Lars-HenrikBol, Roland