Re: Question regarding complexity of grammar

Chris F Clark <cfc@shell01.TheWorld.com>
6 May 2007 16:11:02 -0400

          From comp.compilers
Related articles
Question regarding complexity of grammar mr.miller@gmx.at (Johann Neugebauer) (2007-05-04)
Re: Question regarding complexity of grammar cfc@shell01.TheWorld.com (Chris F Clark) (2007-05-06)
| List of all articles for this month |
From: Chris F Clark <cfc@shell01.TheWorld.com>
Newsgroups: comp.compilers
Date: 6 May 2007 16:11:02 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 07-05-013
Keywords: parse
Posted-Date: 06 May 2007 16:11:02 EDT

Johann Neugebauer <mr.miller@gmx.at> 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.


Post a followup to this message

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