|Time complexity of LR parser generation email@example.com (2006-03-05)|
|Re: Time complexity of LR parser generation firstname.lastname@example.org (SM Ryan) (2006-03-06)|
|Re: Time complexity of LR parser generation email@example.com (Sylvain Schmitz) (2006-03-06)|
|From:||Sylvain Schmitz <firstname.lastname@example.org>|
|Date:||6 Mar 2006 02:13:35 -0500|
|Posted-Date:||06 Mar 2006 02:13:35 EST|
> 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,
Return to the
Search the comp.compilers archives again.