Re: Time complexity of LR parser generation

SM Ryan <wyrmwif@tsoft.org>
6 Mar 2006 02:12:06 -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: SM Ryan <wyrmwif@tsoft.org>
Newsgroups: comp.compilers
Date: 6 Mar 2006 02:12:06 -0500
Organization: Quick STOP Groceries
References: 06-03-005
Keywords: LR(1), theory

alpanad@cse.iitk.ac.in wrote:
# Can anyone throw some ligth on this or give me a relevant link? I.e.
# what is the time complexity of the LR parser generation? Is it
# exponenetial in the size of grammar?


The original parser creation had k terminal symbols in each
state item. So if you have things like recursive productions
with multiple alternatives length less than k, you would have
a m^k combinatorial explosion of terminal lookahead strings.


S -> A$
A -> aA | bA | C
C -> cC | dC | e


Then for k=3, the lookahead strings for S -> .A would be


A$
aA$ | bA$ | cC$ | dC$ | e$
aaA | abA | acC | adC | ae$ | baA | bbA | bcC | bdC | be$
| ccC | cdC | ce$ | dcC | ddC | de$ | e$
aaa | aab | aaC | aba | abb | abC | acc | acdC | ace$ | adc | addC | ade$
| ae$ | baa | bab | baC | bba | bbb | bbC | bcc | bcd | bce
| bdc | bdd | bde | be$ | ccc | ccd | cce | cdc | cdd | cde
| ce$ | dcc | dcd | dce | ddc | ddd | dde | de$ | e$
aaa | aab | aac | aad | aae | aba | abb | abc | abd | abe
| acc | acd | ace$ | adc | add | ade$
| ae$ | baa | bab | bac | bad | bae
| bba | bbb | bbc | bbd | bbe | bcc | bcd | bce
| bdc | bdd | bde | be$ | ccc | ccd | cce | cdc | cdd | cde
| ce$ | dcc | dcd | dce | ddc | ddd | dde | de$ | e$


There are subsequently LR(k) generators that delay expanding
nonterminals in the lookahead string. The combinatorial
explosion still lurks in the shadows, but in practical cases
stays in the shadows.


--
SM Ryan http://www.rawbw.com/~wyrmwif/
Why are we here?
whrp



Post a followup to this message

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