Re: Packrat parsers and memoization

Kay Schluehr <kay@fiber-space.de>
Tue, 9 Jun 2009 23:07:16 -0700 (PDT)

          From comp.compilers
Related articles
Packrat parsers and memoization kay@fiber-space.de (Kay Schluehr) (2009-06-07)
Re: Packrat parsers and memoization armelasselin@hotmail.com (Armel) (2009-06-08)
Re: Packrat parsers and memoization kay@fiber-space.de (Kay Schluehr) (2009-06-09)
RE: Packrat parsers and memoization quinn_jackson2004@yahoo.ca (Quinn Tyler Jackson) (2009-06-11)
| List of all articles for this month |
From: Kay Schluehr <kay@fiber-space.de>
Newsgroups: comp.compilers
Date: Tue, 9 Jun 2009 23:07:16 -0700 (PDT)
Organization: Compilers Central
References: 09-06-029
Keywords: parse
Posted-Date: 11 Jun 2009 08:15:40 EDT

I did a little more research and Bryan Fords O(n) claim about packrat
parsing refers to work of Birman and Ullmann about backtracking
parsers which was made in the 1970s. The paper requires payment
to the IEEE so I haven't read it.


http://www2.computer.org/portal/web/csdl/doi/10.1109/SWAT.1970.18


So I assume now it is a true claim but one has to expect various
constants depending on the structure of the grammar which makes
predictions on actual effort quite difficult.


I'm interested myself in memoization techniques for the CFG top down
parsers I build. Those have quite good left factorization capabilities
and use techniques analog to those of K.Thompson for parsing regular
expressions but there are occasions where they run into backtracking
mode as well.


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.