|Running Earley's Parser in O(n^3) firstname.lastname@example.org (Daniel Zingaro) (2006-05-09)|
|Re: Running Earley's Parser in O(n^3) email@example.com (russell kym horsell) (2006-05-11)|
|From:||russell kym horsell <firstname.lastname@example.org>|
|Date:||11 May 2006 01:54:09 -0400|
|Organization:||Central Iowa (Model) Railroad, Plano, TX, USA|
Daniel Zingaro <email@example.com> wrote:
} 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
Search the comp.compilers archives again.