<p> Earley's parsing algorithm is an O(n^3) algorithm for parsing according to any context-free grammar. Its theoretical importance stems from the fact that it was one of the first algorithms to achieve this time bound, but it has also seen success in compiler-compilers,
theorem provers and natural language processing. It has an elegant structure, and its time complexity on restricted classes of grammars is often as good as specialized algorithms. Grammars with ϵ-productions, however, require special consideration, and have historically lead to inefficient and inelegant implementations.</p> <p> In this thesis, we develop the algorithm from specification using the B-Method. Through refinement steps, we arrive at a list-processing formulation, in which the problems with ϵ-productions emerge and can be understood. The development highlights the essential properties of the algorithm, and has also lead to the discovery of an implementation optimization. We end by giving a concept-test of the algorithm as a literate Pascal program.</p> / Thesis / Master of Computer Science (MCS)
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/21372 |
| Date | 08 1900 |
| Creators | Zingaro, Daniel C. |
| Contributors | Sekerinski, Emil, Computing and Software |
| Source Sets | McMaster University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0015 seconds