@mastersthesis{zingaro_practice_2007,
	address = {Hamilton, Ontario, Canada},
	title = {On the {Practice} of {B}-ing {Earley}},
	url = {http://hdl.handle.net/11375/21372},
	abstract = {arley's parsing algorithm is an O(n{\textasciicircum}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.

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.},
	school = {McMaster University},
	author = {Zingaro, Daniel},
	month = aug,
	year = {2007},
}

{"_id":"tnWBE5Jfi5r8zwKXK","bibbaseid":"zingaro-onthepracticeofbingearley-2007","author_short":["Zingaro, D."],"bibdata":{"bibtype":"mastersthesis","type":"mastersthesis","address":"Hamilton, Ontario, Canada","title":"On the Practice of B-ing Earley","url":"http://hdl.handle.net/11375/21372","abstract":"arley's parsing algorithm is an O(n\\textasciicircum3) 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. 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.","school":"McMaster University","author":[{"propositions":[],"lastnames":["Zingaro"],"firstnames":["Daniel"],"suffixes":[]}],"month":"August","year":"2007","bibtex":"@mastersthesis{zingaro_practice_2007,\n\taddress = {Hamilton, Ontario, Canada},\n\ttitle = {On the {Practice} of {B}-ing {Earley}},\n\turl = {http://hdl.handle.net/11375/21372},\n\tabstract = {arley's parsing algorithm is an O(n{\\textasciicircum}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.\n\nIn 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.},\n\tschool = {McMaster University},\n\tauthor = {Zingaro, Daniel},\n\tmonth = aug,\n\tyear = {2007},\n}\n\n","author_short":["Zingaro, D."],"key":"zingaro_practice_2007","id":"zingaro_practice_2007","bibbaseid":"zingaro-onthepracticeofbingearley-2007","role":"author","urls":{"Paper":"http://hdl.handle.net/11375/21372"},"metadata":{"authorlinks":{}}},"bibtype":"mastersthesis","biburl":"https://api.zotero.org/users/2218414/collections/6P65S5DZ/items?key=5GEsy5KK5k3NW6g00lvqCrRy&format=bibtex&limit=100","dataSources":["QefEapbXGXWuTqpmX"],"keywords":[],"search_terms":["practice","ing","earley","zingaro"],"title":"On the Practice of B-ing Earley","year":2007}