Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/21372
Title: | On The Practice of B-ing Earley |
Authors: | Zingaro, Daniel C. |
Advisor: | Sekerinski, Emil |
Department: | Computing and Software |
Keywords: | Earley's parsing algorithm, grammars, B-Method, Pascal program |
Publication Date: | Aug-2007 |
Abstract: | <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> |
URI: | http://hdl.handle.net/11375/21372 |
Appears in Collections: | Digitized Open Access Dissertations and Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Zingaro_Daniel_C._2007Aug_Masters..pdf | 3.34 MB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.