Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/21372
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Sekerinski, Emil | - |
dc.contributor.author | Zingaro, Daniel C. | - |
dc.date.accessioned | 2017-05-05T13:32:29Z | - |
dc.date.available | 2017-05-05T13:32:29Z | - |
dc.date.issued | 2007-08 | - |
dc.identifier.uri | http://hdl.handle.net/11375/21372 | - |
dc.description.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> | en_US |
dc.language.iso | en_US | en_US |
dc.subject | Earley's parsing algorithm, grammars, B-Method, Pascal program | en_US |
dc.title | On The Practice of B-ing Earley | en_US |
dc.type | Thesis | en_US |
dc.contributor.department | Computing and Software | en_US |
dc.description.degreetype | Thesis | en_US |
dc.description.degree | Master of Computer Science (MCS) | en_US |
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.