Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| Related articles |
|---|
| Running Earley's Parser in O(n^3) zingard@mcmaster.ca (Daniel Zingaro) (2006-05-09) |
| Re: Running Earley's Parser in O(n^3) kym@ukato.freeshell.org (russell kym horsell) (2006-05-11) |
| From: | russell kym horsell <kym@ukato.freeshell.org> |
| Newsgroups: | comp.compilers |
| Date: | 11 May 2006 01:54:09 -0400 |
| Organization: | Central Iowa (Model) Railroad, Plano, TX, USA |
| References: | 06-05-023 |
| Keywords: | parse, theory |
| Posted-Date: | 11 May 2006 01:54:08 EDT |
Daniel Zingaro <zingard@mcmaster.ca> wrote:
} Hello,
} I'm looking for some insight into one aspect of Earley's 1970 article
} dealing with his famous context-free parsing algorithm:
} An efficient context-free parsing algorithm
} Jay Earley. February 1970. Communications of the ACM, Volume 13 Issue 2
} In section 4, Earley gives some tips for how to implement the
} algorithm. In particular, I am wondering about points (3) and (4).
} The algorithm can be implemented without keeping these lists, and I
} can see that they reduce the time necessary to scan through state
} sets, whether it be for the purpose of looking for an already existing
} item, or looking for items that can be created by the completer.
[...]
Basically it's a (Boolean) matrix multiplication problem. Using an
efficient matmul gets you slightly better than O(n^3).
Return to the
comp.compilers page.
Search the
comp.compilers archives again.