From: kay@fiber-space.de   
      
   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.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)