uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
A Comparison Between Packrat Parsing and Conventional Shift-Reduce Parsing on Real-World Grammars and Inputs
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology.
2014 (English)Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

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
National Category
Engineering and Technology
URN: urn:nbn:se:uu:diva-233403OAI: oai:DiVA.org:uu-233403DiVA: diva2:752340
Educational program
Master of Science Programme in Information Technology Engineering
Available from: 2014-10-03 Created: 2014-10-03 Last updated: 2014-10-03Bibliographically approved

Open Access in DiVA

fulltext(691 kB)337 downloads
File information
File name FULLTEXT01.pdfFile size 691 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Department of Information Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 337 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 4212 hits
ReferencesLink to record
Permanent link

Direct link