Sun, 27 Feb 1994 13:48:48 GMT

Related articles |
---|

Parsing with infinite lookahead Matt_Timmermans@msl.isis.org (Matt Timmermans/MSL) (1994-02-22) |

Re: Parsing with infinite lookahead jos@and.nl (1994-02-24) |

Parsing with infinite lookahead bevan@cs.man.ac.uk (Stephen J Bevan) (1994-02-24) |

Re: Parsing with infinite lookahead dwohlfor@cs.uoregon.edu (1994-02-24) |

Re: Parsing with infinite lookahead parrt@s1.arc.umn.edu (Terence Parr) (1994-02-25) |

Re: Parsing with infinite lookahead corbett@lupa.Eng.Sun.COM (1994-02-26) |

Re: Parsing with infinite lookahead nandu@cs.clemson.edu (1994-02-27) |

Re: Parsing with infinite lookahead hbaker@netcom.com (1994-02-28) |

Re: Parsing with infinite lookahead hbaker@netcom.com (1994-03-01) |

Re: Parsing with infinite lookahead bromage@mundil.cs.mu.OZ.AU (1994-03-02) |

Re: Parsing with infinite lookahead mareb@cis0.levels.unisa.edu.au (1994-03-24) |

Newsgroups: | comp.compilers |

From: | nandu@cs.clemson.edu |

Keywords: | parse, theory |

Organization: | Compilers Central |

References: | 94-02-174 94-02-190 |

Date: | Sun, 27 Feb 1994 13:48:48 GMT |

Terence parr writes:

!I think the Early Algorithm (in O(n^3) time?) parses any unambiguous

!context-free language. However, most parser-generators are restricted to

!the LALR(1), LR(1), or LL(1) grammars and, hence, cannot handle all

!context-free languages.

Earley's Algorithm parses any grammar (ambiguous or unambiguous) in O(n^2)

space and O(n^2) or O(n^3) time, depending upon whether the grammar is

unambiguous or ambiguous, respectively. The best part about the algorithm

is that no tables are constructed before hand (unlike any other parser)

but instead, built on the fly, for a given string to be parsed. It is

undecidable whether a CFG is ambiguous, as was pointed out earlier, but

for a given string to be parsed, Earley's algorithm will tell you whether

more than one derivation exists or not. For Further information, refer AHO

and ULLMAN, "The Theory of Parsing, Translation and Compiling", Volume 1,

Prentice Hall.

As an aside, does anybody know where Dr. Earley is and if he is still

working on parsers or not?

--

Nandakumar Sankaran (nandu@cs.clemson.edu) (nsankar@hubcap.clemson.edu)

311-8 Old Greenville Hwy. Clemson SC 29631-1651 (803)653-7749

G34 Jordan Hall Comp. Sci. Dept. Clemson Univ. SC 29634 (803)656-6979

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.