Re: Time complexity of LR parser generation

Sylvain Schmitz <schmitz@i3s.unice.fr>
6 Mar 2006 02:13:35 -0500

          From comp.compilers
Related articles
Time complexity of LR parser generation alpanad@cse.iitk.ac.in (2006-03-05)
Re: Time complexity of LR parser generation wyrmwif@tsoft.org (SM Ryan) (2006-03-06)
Re: Time complexity of LR parser generation schmitz@i3s.unice.fr (Sylvain Schmitz) (2006-03-06)
| List of all articles for this month |
From: Sylvain Schmitz <schmitz@i3s.unice.fr>
Newsgroups: comp.compilers
Date: 6 Mar 2006 02:13:35 -0500
Organization: Compilers Central
References: 06-03-005
Keywords: LR(1), theory
Posted-Date: 06 Mar 2006 02:13:35 EST

alpanad@cse.iitk.ac.in wrote:


> Can anyone throw some light on this or give me a relevant link? I.e.
> what is the time complexity of the LR parser generation? Is it
> exponential in the size of grammar?


The size of an LR parser can be exponential in the grammar size; IIRC
there were some examples in [Esko Ukkonen: Lower Bounds on the Size of
Deterministic Parsers. J. Comput. Syst. Sci. 26(2): 153-170 (1983)].


      However, this size is usually polynomial, and simple optimizations
like efficient closures and memoization---you can see it as the NFA
generation---have a great impact on the actual generation time; look how
it is done in bison for instance.


--
Hope that helps,


      Sylvain

Post a followup to this message

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