|Packrat parsers and memoization firstname.lastname@example.org (Kay Schluehr) (2009-06-07)|
|Re: Packrat parsers and memoization email@example.com (Armel) (2009-06-08)|
|Re: Packrat parsers and memoization firstname.lastname@example.org (Kay Schluehr) (2009-06-09)|
|RE: Packrat parsers and memoization email@example.com (Quinn Tyler Jackson) (2009-06-11)|
|From:||Kay Schluehr <firstname.lastname@example.org>|
|Date:||Tue, 9 Jun 2009 23:07:16 -0700 (PDT)|
|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.
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.
Return to the
Search the comp.compilers archives again.