Re: Time complexity of LR parser generation

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

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