|Question regarding complexity of grammar email@example.com (Johann Neugebauer) (2007-05-04)|
|Re: Question regarding complexity of grammar cfc@shell01.TheWorld.com (Chris F Clark) (2007-05-06)|
|From:||Chris F Clark <cfc@shell01.TheWorld.com>|
|Date:||6 May 2007 16:11:02 -0400|
|Organization:||The World Public Access UNIX, Brookline, MA|
|Posted-Date:||06 May 2007 16:11:02 EDT|
Johann Neugebauer <firstname.lastname@example.org> 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.
Return to the
Search the comp.compilers archives again.