From: cfc@shell01.TheWorld.com   
      
   Johann Neugebauer  writes:   
      
   > The parser works pretty fine but as I do not understand the   
   > code that is produced by Lex/Yacc I wonder what runtime complexity this   
   > parser has? Personally, I believe that it is O(n) but I am not quite   
   > sure about that.   
      
   All LL(k) and LR(k) parsers have O(n) complexity.  It is built into   
   the model.  It is one of the attractions of these methodologies.  PEG   
   parsers have that same property (provided one uses the memoizing   
   implementation).  GLR, backtracking, predicated, and Earley parsers do   
   not have that property.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)