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

russell kym horsell <>
11 May 2006 01:54:09 -0400

          From comp.compilers

Related articles
Running Earley's Parser in O(n^3) (Daniel Zingaro) (2006-05-09)
Re: Running Earley's Parser in O(n^3) (russell kym horsell) (2006-05-11)
| List of all articles for this month |

From: russell kym horsell <>
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 <> 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.