Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| 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: | corbett@lupa.Eng.Sun.COM (Robert Corbett) |
| Keywords: | parse, theory |
| Organization: | Sun |
| References: | 94-02-174 94-02-188 |
| Date: | Sat, 26 Feb 1994 01:31:45 GMT |
dwohlfor@cs.uoregon.edu (Clai'omh Dorcha) writes:
>The CYK algorithm (as seen in Hopcroft & Ullman) is capable of parsing
>_any_ context free grammar. The bummer is that it is O(n^3) where n is
>the length of the input string. Most folks aren't too keen on using it
>when a linear parser exists for most CFG's. But it is the only general
>purpose parsing algorithm.
The ONLY general-purpose parsing algorithm? HARDLY! Earley's
algorithm (CACM 13:2), the Graham, Harrison, Ruzzo algorithm
(TOPLAS 2:3), backtracking algorithms all handle general
context-free grammars.
BTW, the order complexity of context-free parsing has been shown to
be less than or equal to the order complexity of matrix multiplication.
Yours truly,
Robert Corbett
--
Return to the
comp.compilers page.
Search the
comp.compilers archives again.