Re: Running Earley's Parser in O(n^3)

russell kym horsell <kym@ukato.freeshell.org>
11 May 2006 01:54:09 -0400

          From comp.compilers

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)
| List of all articles for this month |

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

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



Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.