# 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 Newsgroups: comp.compilers Date: 6 Mar 2006 02:12:06 -0500 Organization: Quick STOP Groceries References: 06-03-005 Keywords: LR(1), theory Posted-Date: 06 Mar 2006 02:12:06 EST

# 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