6 Mar 2006 02:12:06 -0500

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) |

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.