Parsers

Caml fans

Here is a stream-based prepositional phrase parser. The stream module is based on section 5.12 of Paulson's excellent book, ML for the Working Programmer. The adjoin2 combinator is right out of SICP's natural language example. These times are from native code compiled using ocamlopt 3.09.3 and running on a MacBook Pro at 667 MHz.

	trees	seconds
4PPs	42	0.02
5PPs	132	0.17
6PPs	429	1.78
7PPs	1430	30.47

The CYK parser for Minimalist Grammars that I describe in Appendix A of my dissertation. Implements a design presented in Henk Harkema's 2001 UCLA dissertation. See also

Henk Harkema. 2004. "A Recognizer for Minimalist Languages" in New Developments in Parsing Technology, Harry Bunt, John Carroll and Giorgio Satta, editors. Springer.

Oz fans

Here are some files that will calculate what a left-corner parser would do on the unambiguous stimuli from Experiment 4 of

Van Dyke, J.A. & Lewis, R.L. (2003). Distinguishing effects of structure and decay on attachment and repair: A retrieval interference theory of recovery from misanalyzed ambiguities. Journal of Memory and Language, 49(3), 285-316.

very simple context free grammar (that also specifies the left-corner strategy)
highly verbose GLC parser in Oz (easier to understand vanilla version)
oracle-maker based on Stabler's 2003 Notes on Computational Linguistics, section 6.5
parser action typer-outer
"faucets" in Oz
lazy solver from chapter 9 of Concepts, Techniques and Models of Computer Programming

John T. Hale jthale@msu.edu