An efficient context-free parsing algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

An efficient context-free parsing algorithm

Full text

Pdf (924 KB)

Source

Communications of the ACM archive
Volume 13 , Issue 2 (February 1970) table of contents

Pages: 94 - 102

Year of Publication: 1970

ISSN:0001-0782

Author

Jay Earley

Univ. of California, Berkeley

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 57, Downloads (12 Months): 407, Citation Count: 238

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/362007.362035 What is a DOI?

ABSTRACT

A parsing algorithm which seems to be the most efficient general context-free algorithm known is described. It is similar to both Knuth's LR(k) algorithm and the familiar top-down algorithm. It has a time bound proportional to n3 (where n is the length of the string being parsed) in general; it has an n2 bound for unambiguous grammars; and it runs in linear time on a large class of grammars, which seems to include most practical context-free programming language grammars. In an empirical comparison it appears to be superior to the top-down and bottom-up algorithms studied by Griffiths and Petrick.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Jay Clark Earley, An efficient context-free parsing algorithm, 1968
	2	KNUTH, D. E. On the translation of languages from left to right. Information and Control 8 (1965), 607-639.
	3	FLOYD, R. W. The syntax of programming languages--a survey. IEEE Trans. EC-13, 4 (Aug. 1964).
	4	YOUNGER, D. H. Recognition and parsing of context-free languages in time n 3. Information and Control 10 (1967), 189- 208.
	5	HAys, D. Automatic language-data processing. In Computer Applications in the Behavioral Sciences, H. Borko (Ed.) Prentice Hall, Englewood Cliffs, N.J., 1962.
	6	YOUNGER, D.H. Context-free language processing in time n 3. General Electric R & D Center, Schenectady, N.Y., 1966.
	7	T. Kasami , K. Torii, A Syntax-Analysis Procedure for Unambiguous Context-Free Grammars, Journal of the ACM (JACM), v.16 n.3, p.423-431, July 1969 [doi>10.1145/321526.321531]
	8	T. V. Griffiths , S. R. Petrick, On the relative efficiencies of context-free grammar, Communications of the ACM, v.8 n.5, p.289-300, May 1965 [doi>10.1145/364914.364943]
	9	Jerome Feldman , David Gries, Translator writing systems, Communications of the ACM, v.11 n.2, p.77-113, Feb. 1968 [doi>10.1145/362896.362902]

CITED BY 238

	Lillian Lee, Fast context-free grammar parsing requires fast boolean matrix multiplication, Journal of the ACM (JACM), v.49 n.1, p.1-15, January 2002
	Jean-Marc Andreoli , Remo Pareschi, Communication as fair distribution of knowledge, ACM SIGPLAN Notices, v.26 n.11, p.212-229, Nov. 1991
	C B Jones, Formal development of correct algorithms: An example based on earley's recogniser, ACM SIGACT News
	Jacques Cohen , Timothy J. Hickey, Parsing and compiling using Prolog, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.2, p.125-163, April 1987
	J. Heering , P. Klint , J. Rekers, Incremental generation of parsers, ACM SIGPLAN Notices, v.24 n.7, p.179-191, July 1989
	M. Nussbaum, An interpreter for large knowledge bases, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.87-97, February 21-23, 1989, Louisville, Kentucky
	S. O. Anderson , R. C. Backhouse, Locally Least-Cost Error Recovery in Earley's Algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.3, p.318-347, July 1981
	Susan L. Graham , Michael Harrison and Walter L. Ruzzo, An Improved Context-Free Recognizer, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.3, p.415-462, July 1980
	Annika Aasa , Kent Petersson , Dan Synek, Concrete syntax for data objects in functional languages, Proceedings of the 1988 ACM conference on LISP and functional programming, p.96-105, July 25-27, 1988, Snowbird, Utah, United States
	Robert Kowalski, Algorithm = logic + control, Communications of the ACM, v.22 n.7, p.424-436, July 1979
	Stephen A. Cook, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, Journal of the ACM (JACM), v.18 n.1, p.4-18, Jan. 1971
	W. A. Woods, Transition network grammars for natural language analysis, Communications of the ACM, v.13 n.10, p.591-606, Oct. 1970
	Ken-Chih Liu, Extending Earley's context-free parsing algorithm for string pattern matching, Proceedings of the 1988 ACM sixteenth annual conference on Computer science, p.500-509, February 1988, Atlanta, Georgia, United States
	David A. Workman , John B. Higdon, The design of a parser generator, Proceedings of the 16th annual Southeast regional conference, p.82-86, April 13-15, 1978, Atlanta, Georgia
	William L. Scherlis, Program improvement by internal specialization, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.41-49, January 26-28, 1981, Williamsburg, Virginia
	Lawrence J. Mazlack , Richard A. Feinauer, Establishing a basis for mapping natural-language statements onto a database query language, Proceedings of the 3rd annual ACM conference on Research and development in information retrieval, p.192-202, June 23-27, 1980, Cambridge, England
	Aravind K. Joshi , Leon S. Levy , Kang Yueh, Local constraints in the syntax and semantics of programming languages, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.255-264, January 23-25, 1978, Tucson, Arizona
	David S. Warren, Memoing for logic programs, Communications of the ACM, v.35 n.3, p.93-111, March 1992
	Ivan M. Havel , Michael A. Harrison, On the Parsing of Deterministic Languages, Journal of the ACM (JACM), v.21 n.4, p.525-548, Oct. 1974
	Thomas W. Christopher , Philip J. Hatcher , Ronald C. Kukuk, Using dynamic programming to generate optimized code in a Graham-Glanville style code generator, ACM SIGPLAN Notices, v.19 n.6, p.25-36, June 1984
	Franklin L. DeRemer, Simple LR(k) grammars, Communications of the ACM, v.14 n.7, p.453-460, July 1971
	Gordon Lyon, Syntax-directed least-errors analysis for context-free languages: a practical approach, Communications of the ACM, v.17 n.1, p.3-14, Jan. 1974
	G. Antoniadis , G. Lallich-Boidin , Y. Polity , J. Rouault, A french text recognition model for information retrieval system, Proceedings of the 11th annual international ACM SIGIR conference on Research and development in information retrieval, p.67-84, May 1988, Grenoble, France
	Hae-Chang Rim , Jungyun Seo , Robert F. Simmons, Transforming syntactic graphs into semantic graphs, Proceedings of the 28th annual meeting on Association for Computational Linguistics, p.47-53, June 06-09, 1990, Pittsburgh, Pennsylvania
	Barrett R. Bryant , Balanjaninath Edupuganty , K. R. Sundararaghavan , Tadao Takaoka, Two-level grammar: data flow English for functional and logic programming, Proceedings of the 1988 ACM sixteenth annual conference on Computer science, p.469-474, February 1988, Atlanta, Georgia, United States
	Wilf R. LaLonde, On directly constructing LR(k) parsers without chain reductions, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.127-133, January 19-21, 1976, Atlanta, Georgia
	James A. Hendler , Paul Roller Michaelis, The effects of limited grammar on interactive natural language, Proceedings of the SIGCHI conference on Human Factors in Computing Systems, p.190-192, December 12-15, 1983, Boston, Massachusetts, United States
	H. Albert Napier , Richard R. Batsell , Norman S. Guadango , David M. Lane, Impact of a restricted natural language interface on ease of learning and productivity, Communications of the ACM, v.32 n.10, p.1190-1198, Oct. 1989
	James N. Gray , Michael A. Harrison, On the Covering and Reduction Problems for Context-Free Grammars, Journal of the ACM (JACM), v.19 n.4, p.675-698, Oct. 1972
	Lars T. Hansen , William D. Clinger, An experimental study of renewal-older-first garbage collection, ACM SIGPLAN Notices, v.37 n.9, p.247-258, September 2002
	Patrick A. V. Hall , Geoff R. Dowling, Approximate String Matching, ACM Computing Surveys (CSUR), v.12 n.4, p.381-402, Dec. 1980
	King-Hang Chu , King-Sun Fu, VLSI architectures for high speed recognition of context-free languages and finite-state languages, ACM SIGARCH Computer Architecture News, v.10 n.3, p.43-49, April 1982
	Jim Barnett , Kevin Knight , Inderjeet Mani , Elaine Rich, Knowledge and natural language processing, Communications of the ACM, v.33 n.8, p.50-71, Aug. 1990
	A. V. Aho , P. J. Denning , J. D. Ullman, Weak and Mixed Strategy Precedence Parsing, Journal of the ACM (JACM), v.19 n.2, p.225-243, April 1972
	Mark-Jan Nederhof , Eberhard Bertsch, Linear-time suffix parsing for deterministic languages, Journal of the ACM (JACM), v.43 n.3, p.524-554, May 1996
	Glenn D. Blank, A finite and real-time processor for natural language, Communications of the ACM, v.32 n.10, p.1174-1189, Oct. 1989
	Sofie Verbaeten , Danny De Schreye , Konstantinos Sagonas, Termination proofs for logic programs with tabling, ACM Transactions on Computational Logic (TOCL), v.2 n.1, p.57-92, Jan. 2001
	Joseph Bates , Alon Lavie, Recognizing substrings of LR(k) languages in linear time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.1051-1077, May 1994
	Annika Aasa, Precedences for conctypes, Proceedings of the conference on Functional programming languages and computer architecture, p.83-91, June 09-11, 1993, Copenhagen, Denmark
	Kevin Knight, Unification: a multidisciplinary survey, ACM Computing Surveys (CSUR), v.21 n.1, p.93-124, March 1989
	Susan L. Graham , Michael A. Harrison , Walter L. Ruzzo, On line context free language recognition in less than cubic time(Extended Abstract), Proceedings of the eighth annual ACM symposium on Theory of computing, p.112-120, May 03-05, 1976, Hershey, Pennsylvania, United States
	Chris Clark, Conflicts, ACM SIGPLAN Notices, v.37 n.8, August 2002
	Tim A. Wagner , Susan L. Graham, Incremental analysis of real programming languages, ACM SIGPLAN Notices, v.32 n.5, p.31-43, May 1997
	G. V. Cormack, An LR substring parser for noncorrecting syntax error recovery, ACM SIGPLAN Notices, v.24 n.7, p.161-169, July 1989
	William S. Evans , Christopher W. Fraser, Bytecode compression via profiled grammar rewriting, ACM SIGPLAN Notices, v.36 n.5, p.148-155, May 2001
	Jukka Paakki, Multi-pass execution of functional logic programs, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.361-374, January 16-19, 1994, Portland, Oregon, United States
	Hans Leiss, On Kilbury's modification of Earley's algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.4, p.610-640, Oct. 1990
	Jukka Paakki , Antti-Pekka Tuovinen, Source-to-source translation of visual languages, Nordic Journal of Computing, v.5 n.3, p.235-264, Fall 1998
	Miroslaw Bańko, Review of "Efficient parsing for natural language: a fast algorithm for practical systems" by Masaru Tomita. Kluwer Academic Publishers 1986., Computational Linguistics, v.14 n.2, June 1988
	Bob Carpenter, The generative power of categorial grammars and head-driven phrase structure grammars with lexical rules, Computational Linguistics, v.17 n.3, p.301-313, September 1991
	Ralph Weischedel, Natural-Language Understanding at BBN, IEEE Annals of the History of Computing, v.28 n.1, p.46-55, January 2006
	J. Nelson Verastegui, Utilisation du parallelisme en traduction automatisee par ordinateur, Proceedings of the 9th conference on Computational linguistics, p.397-405, July 05-10, 1982, Prague, Czechoslovakia
	Wil Janssen , Mannes Poel , Klaas Sikkel , Job Zwiers, The Primordial Soup Algorithm: a systematic approach to the specification of parallel parsers, Proceedings of the 14th conference on Computational linguistics, August 23-28, 1992, Nantes, France
	C. Raymond Perrault, On the mathematical properties of linguistic theories, Proceedings of the 21st annual meeting on Association for Computational Linguistics, June 15-17, 1983, Cambridge, Massachusetts
	Graeme Ritchie, Completeness conditions for mixed strategy bidirectional parsing, Computational Linguistics, v.25 n.4, p.457-486, December 1999
	Derek Proudian , Carl Pollard, Parsing Head-driven Phrase Structure Grammar, Proceedings of the 23rd annual meeting on Association for Computational Linguistics, p.167-171, July 08-12, 1985, Chicago, Illinois
	Kenneth Church , Ramesh Patil, Coping with syntactic ambiguity or how to put the block in the box on the table, Computational Linguistics, v.8 n.3-4, p.139-149, July-December 1982
	Dekai Wu , Hongsing Wong Hkust, Machine translation with a stochastic grammatical channel, Proceedings of the 17th international conference on Computational linguistics, p.1408-1415, August 10-14, 1998, Montreal, Quebec, Canada
	C. Raymond Perrault, On the mathematical properties of linguistic theories, Computational Linguistics, v.10 n.3-4, p.165-176, July-December 1984
	John Aycock, Why bison is becoming extinct, Crossroads, v.7 n.5, p.3-3, Mid summer 2001
	Veronica Dahl, Review of "Constraint-based grammar formalisms: parsing and type inference for natural and computer languages" by Stuart M. Shieber. The MIT Press 1992., Computational Linguistics, v.19 n.3, September 1993
	David D. McDonald, An efficient chart-based algorithm for partial-parsing of unrestricted texts, Proceedings of the third conference on Applied natural language processing, March 31-April 03, 1992, Trento, Italy
	Stephan Oepen , John Carroll, Ambiguity packing in constraint-based parsing: practical results, Proceedings of the first conference on North American chapter of the Association for Computational Linguistics, p.162-169, April 29-May 04, 2000, Seattle, Washington
	Joep Rous, Computational aspects of M-grammars, Proceedings of the fifth conference on European chapter of the Association for Computational Linguistics, p.210-215, April 09-11, 1991, Berlin, Germany
	Mark-Jan Nederhof , Giorgio Satta, Left-to-right parsing and bilexical context-free grammars, Proceedings of the first conference on North American chapter of the Association for Computational Linguistics, p.272-279, April 29-May 04, 2000, Seattle, Washington
	Jochen Dörre, Efficient construction of underspecified semantics under massive ambiguity, Proceedings of the 35th annual meeting on Association for Computational Linguistics, p.386-393, July 07-12, 1997, Madrid, Spain
	John Carroll, Relating complexity to practical performance in parsing with wide-coverage unification grammars, Proceedings of the 32nd annual meeting on Association for Computational Linguistics, p.287-294, June 27-30, 1994, Las Cruces, New Mexico
	Scott Miller , David Stallard , Robert Bobrow , Richard Schwartz, A fully statistical approach to natural language interfaces, Proceedings of the 34th annual meeting on Association for Computational Linguistics, p.55-61, June 24-27, 1996, Santa Cruz, California
	Yves Schabes , Aravind K. Joshi, An Earley-type parsing algorithm for Tree Adjoining Grammars, Proceedings of the 26th annual meeting on Association for Computational Linguistics, p.258-269, June 07-10, 1988, Buffalo, New York
	Hans Uszkoreit, A framework for processing partially free word order, Proceedings of the 21st annual meeting on Association for Computational Linguistics, June 15-17, 1983, Cambridge, Massachusetts
	René Leermakers, How to cover a grammar, Proceedings of the 27th annual meeting on Association for Computational Linguistics, p.135-142, June 26-29, 1989, Vancouver, British Columbia, Canada
	Hiyan Alshawi, Head automata and bilingual tiling: translation with minimal representations, Proceedings of the 34th annual meeting on Association for Computational Linguistics, p.167-176, June 24-27, 1996, Santa Cruz, California
	Dekai Wu, Stochastic inversion transduction grammars and bilingual parsing of parallel corpora, Computational Linguistics, v.23 n.3, p.377-403, September 1997
	David Scott Warren , Joyce Friedman, Using semantics in non-context-free parsing of montague grammar, Computational Linguistics, v.8 n.3-4, p.123-138, July-December 1982
	Yves Schabes, Review of "The functional treatment of parsing" by René Leermakers. Kluwer Academic Publishers 1993., Computational Linguistics, v.21 n.1, March 1995
	Mats Wirén, Interactive incremental chart parsing, Proceedings of the fourth conference on European chapter of the Association for Computational Linguistics, p.241-248, April 10-12, 1989, Manchester, England
	Mark-Jan Nederhof, The computational complexity of the correct-prefix property for TAGs, Computational Linguistics, v.25 n.3, p.345-360, Septmeber 1999
	Michael Johnston, Unification-based multimodal parsing, Proceedings of the 36th annual meeting on Association for Computational Linguistics, August 10-14, 1998, Montreal, Quebec, Canada
	Vincenzo Lombardo , Leonardo Lesmo, Formal aspects and parsing issues of dependency theory, Proceedings of the 17th international conference on Computational linguistics, p.787-793, August 10-14, 1998, Montreal, Quebec, Canada
	Kent Wittenburg, Predictive combinators: a method for efficient processing of combinatory Categorial Grammars, Proceedings of the 25th annual meeting on Association for Computational Linguistics, p.73-80, July 06-09, 1987, Stanford, California
	Kenneth W. Church, A finite-state parser for use in speech recognition, Proceedings of the 21st annual meeting on Association for Computational Linguistics, June 15-17, 1983, Cambridge, Massachusetts
	Fernando C. N. Pereira , David H. D. Warren, Parsing as deduction, Proceedings of the 21st annual meeting on Association for Computational Linguistics, June 15-17, 1983, Cambridge, Massachusetts
	G. Edward Barton, The computational difficulty of ID/LP parsing, Proceedings of the 23rd annual meeting on Association for Computational Linguistics, p.76-81, July 08-12, 1985, Chicago, Illinois
	Kurt Konolige, Capturing linguistic generalizations with metarules in an annotated phrase-structure grammar, Proceedings of the 18th annual meeting on Association for Computational Linguistics, June 19-22, 1980, Philadelphia, Pennsylvania
	Michael Niv, A psycholinguistically motivated parser for CCG, Proceedings of the 32nd annual meeting on Association for Computational Linguistics, p.125-132, June 27-30, 1994, Las Cruces, New Mexico
	John Dowding , Robert Moore , Franĉois Andry , Douglas Moran, Interleaving syntax and semantics in an efficient bottom-up parser, Proceedings of the 32nd annual meeting on Association for Computational Linguistics, p.110-116, June 27-30, 1994, Las Cruces, New Mexico
	Mark-Jan Nederhof , Giorgio Satta, Efficient tabular LR parsing, Proceedings of the 34th annual meeting on Association for Computational Linguistics, p.239-246, June 24-27, 1996, Santa Cruz, California
	David M. Magerman , Carl Weir, Efficiency, robustness and accuracy in Picky chart parsing, Proceedings of the 30th annual meeting on Association for Computational Linguistics, p.40-47, June 28-July 02, 1992, Newark, Delaware
	Ajit B. Pai , Richard B. Kieburtz, Global Context Recovery: A New Strategy for Syntactic Error Recovery by Table-Drive Parsers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.1, p.18-41, Jan. 1980
	Wilf R. LaLonde, Regular right part grammars and their parsers, Communications of the ACM, v.20 n.10, p.731-741, Oct. 1977
	Warwick Irwin , Neville Churcher, XML in the visualisation pipeline, Proceedings of the Pan-Sydney area workshop on Visual information processing, p.59-67, May 01, 2001, Sydney, Australia
	Alexander Okhotin, A recognition and parsing algorithm for arbitrary conjunctive grammars, Theoretical Computer Science, v.302 n.1-3, p.365-399, 13 June 2003
	Eberhard Bertsch , Mark-Jan Nederhof, On failure of the pruning technique in “Error repair in shift-reduce parsers”, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.1, p.1-10, Jan. 1999
	A. V. Aho , S. C. Johnson, LR Parsing, ACM Computing Surveys (CSUR), v.6 n.2, p.99-124, June 1974
	John C. Reynolds, G/EDANKEN—a simple typeless language based on the principle of completeness and the reference concept, Communications of the ACM, v.13 n.5, p.308-319, May 1970
	Hiyan Alshawi , Shona Douglas , Srinivas Bangalore, Learning dependency translation models as collections of finite-state head transducers, Computational Linguistics, v.26 n.1, p.45-60, March 2000
	Paola Merlo, Modularity and information content classes in principle-based parsing, Computational Linguistics, v.21 n.4, p.515-541, December 1995
	Andreas Stolcke, An efficient probabilistic context-free parsing algorithm that computes prefix probabilities, Computational Linguistics, v.21 n.2, p.165-201, June 1995
	G. Edward Barton, On the complexity of ID/LP parsing 1, Computational Linguistics, v.11 n.4, p.205-218, October-December 1985
	K. C. Liu , A. C. Fleck, String pattern matching in polynomial time, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.222-225, January 29-31, 1979, San Antonio, Texas
	Brian Roark, Probabilistic top-down parsing and language modeling, Computational Linguistics, v.27 n.2, p.249-276, June 2001
	Vincenzo Lombardo , Leonardo Lesmo, An Earley-type recognizer for dependency grammar, Proceedings of the 16th conference on Computational linguistics, August 05-09, 1996, Copenhagen, Denmark
	Jon M. Slack, Distributed memory: a basis for chart parsing, Proceedings of the 11th coference on Computational linguistics, August 25-29, 1986, Bonn, Germany
	Patrick Cousot , Radhia Cousot, Parsing as abstract interpretation of grammar semantics, Theoretical Computer Science, v.290 n.1, p.531-544, 1 January 2003
	Sebastian Goeser, Chart parsing of robust grammars, Proceedings of the 14th conference on Computational linguistics, August 23-28, 1992, Nantes, France
	Wilhelm Weisweber , Susanne Preuß, Direct parsing with metarules, Proceedings of the 14th conference on Computational linguistics, August 23-28, 1992, Nantes, France
	Sylvie Billot , Bernard Lang, The structure of shared forests in ambiguous parsing, Proceedings of the 27th annual meeting on Association for Computational Linguistics, p.143-151, June 26-29, 1989, Vancouver, British Columbia, Canada
	Oliviero Stock , Rino Falcone , Patrizia Insinnamo, Island parsing and bidirectional charts, Proceedings of the 12th conference on Computational linguistics, p.636-641, August 22-27, 1988, Budapest, Hungry
	Karl-Michael Schneider, Parsing schemata for grammars with variable number and order of constituents, Proceedings of the 18th conference on Computational linguistics, July 31-August 04, 2000, Saarbrücken, Germany
	Philippe Blache , Jean-Yves Morin, Bottom-Up Filtering: a parsing strategy for GPSG, Proceedings of the 13th conference on Computational linguistics, p.19-23, August 20-25, 1990, Helsinki, Finland
	Yves Schabes , Richard C. Waters, Tree insertion grammar: a cubic-time, parsable formalism that lexicalizes context-free grammar without changing the trees produced, Fuzzy Sets and Systems, v.76 n.3, p.309-317, Dec. 22, 1995
	Jan Heering , Paul Klint , Jan Rekers, Incremental Generation of Parsers, IEEE Transactions on Software Engineering, v.16 n.12, p.1344-1351, December 1990
	Ted Briscoe , John Carroll, Generalized probabilistic LR parsing of natural language (Corpora) with unification-based grammars, Computational Linguistics, v.19 n.1, March 1993
	Mark-Jan Nederhof, Generalized left-corner parsing, Proceedings of the sixth conference on European chapter of the Association for Computational Linguistics, April 21-23, 1993, Utrecht, The Netherlands
	Ying Xu , Lusheng Wang , Xiaotie Deng, Exact pattern matching for RNA secondary structures, Proceedings of the second conference on Asia-Pacific bioinformatics, p.257-263, January 01, 2004, Dunedin, New Zealand
	Mats Wirén, A comparison of rule-invocation strategies in context-free chart parsing, Proceedings of the third conference on European chapter of the Association for Computational Linguistics, p.226-233, April 01-03, 1987, Copenhagen, Denmark
	Nelson Correa, An extension of earley's algorithm for S-attributed grammars, Proceedings of the fifth conference on European chapter of the Association for Computational Linguistics, p.299-302, April 09-11, 1991, Berlin, Germany
	Yasuhisa Niimi , Shigeru Uzuhara , Yutaka Kobayashi, The procedure to construct a word predictor in a speech understanding system from a task-specific grammar defined in a CFG or a DCG, Proceedings of the 11th coference on Computational linguistics, August 25-29, 1986, Bonn, Germany
	Mark Perlin, LR recursive transition networks for Earley and Tomita parsing, Proceedings of the 29th annual meeting on Association for Computational Linguistics, p.98-105, June 18-21, 1991, Berkeley, California
	Mark-Jan Nederhof, Practical experiments with regular approximation of context-free languages, Computational Linguistics, v.26 n.1, p.17-44, March 2000
	Peter Neuhaus , Norbert Bröker, The complexity of recognition of linguistically adequate dependency grammars, Proceedings of the eighth conference on European chapter of the Association for Computational Linguistics, p.337-343, July 07-12, 1997, Madrid, Spain
	Masaaki Nagata, An empirical study on rule granularity and unification interleaving toward an efficient unification-based parsing system, Proceedings of the 14th conference on Computational linguistics, August 23-28, 1992, Nantes, France
	Joshua Goodman, Semiring parsing, Computational Linguistics, v.25 n.4, p.573-605, December 1999
	Martin Bravenboer , Eelco Visser, Concrete syntax for objects: domain-specific language embedding and assimilation without restrictions, ACM SIGPLAN Notices, v.39 n.10, October 2004
	Jennifer Foster , Carl Vogel, Parsing Ill-Formed Text Using an Error Grammar, Artificial Intelligence Review, v.21 n.3-4, p.269-291, June 2004
	Thomas E. Cheatham , Thomas A. Standish, Optimization aspects of compiler-compilers, ACM SIGPLAN Notices, v.5 n.10, October 1970
	Peter Thiemann, Grammar-based analysis of string expressions, Proceedings of the 2005 ACM SIGPLAN international workshop on Types in languages design and implementation, p.59-70, January 10-10, 2005, Long Beach, California, USA
	Hans-Ulrich Block , Hans Haugeneder, The treatment of movement-rules in a LFG-parser, Proceedings of the 11th coference on Computational linguistics, August 25-29, 1986, Bonn, Germany
	Ronald F. Ayres, A simple and powerful type system for programming languages, Journal of Systems and Software, v.73 n.2, p.301-311, October 2004
	Masaru Tomita , Jaime G. Carbonell, Another stride towards knowledge-based machine translation, Proceedings of the 11th coference on Computational linguistics, August 25-29, 1986, Bonn, Germany
	Bernard Lang, Parallel non-deterministic bottom-up parsing, ACM SIGPLAN Notices, v.6 n.12, p.56-57, December 1971
	P. L. Wodon, A syntax macro processor, ACM SIGPLAN Notices, v.6 n.12, p.48-50, December 1971
	Noriko Tomuro , Steven L. Lytinen, Nonminimal derivations in unification-based parsing, Computational Linguistics, v.27 n.2, June 2001
	Jonathan Slocum, A practical comparison of parsing strategies, Proceedings of the 19th annual meeting on Association for Computational Linguistics, June 29-July 01, 1981, Stanford, California
	John T. Maxwell , Ronald M. Kaplan, The interface between phrasal and functional constraints, Computational Linguistics, v.19 n.4, p.571-590, December 1993
	Michael Schiehlen, Semantic construction from parse forests, Proceedings of the 16th conference on Computational linguistics, August 05-09, 1996, Copenhagen, Denmark
	Koichi Takeda, Pattern-based context-free grammars for machine translation, Proceedings of the 34th annual meeting on Association for Computational Linguistics, p.144-151, June 24-27, 1996, Santa Cruz, California
	Bernard Lang, Parsing incomplete sentences, Proceedings of the 12th conference on Computational linguistics, p.365-371, August 22-27, 1988, Budapest, Hungry
	Surapant Meknavin , Manabu Okumura , Hozumi Tanaka, A chart-based method of ID/LP parsing with generalized discrimination networks, Proceedings of the 14th conference on Computational linguistics, August 23-28, 1992, Nantes, France
	James Kilbury, Parsing with Category Coocurrence Restrictions, Proceedings of the 12th conference on Computational linguistics, p.324-327, August 22-27, 1988, Budapest, Hungry
	Dekai Wu, A polynomial-time algorithm for statistical machine translation, Proceedings of the 34th annual meeting on Association for Computational Linguistics, p.152-158, June 24-27, 1996, Santa Cruz, California
	Peter Norvig, Techniques for automatic memoization with applications to context-free parsing, Computational Linguistics, v.17 n.1, March 1991
	René Leermakers, Non-deterministic recursive ascent parsing, Proceedings of the fifth conference on European chapter of the Association for Computational Linguistics, p.63-68, April 09-11, 1991, Berlin, Germany
	Pavel Smrž , Vladimír Kadlec, Incremental parser for Czech, Proceedings of the 4th international symposium on Information and communication technologies, January 03-06, 2005, Cape Town, South Africa
	Paul S. Jacobs , George Krupka , Lisa Rau , Michael L. Mauldin , Teruko Mitamura , Tsuyoshi Kitani , Ira Sider , Lois Childs, The TIPSTER/SHOGUN project, Proceedings of a workshop on held at Fredericksburg, Virginia: September 19-23, 1993, September 19-23, 1993, Fredericksburg, Virginia
	Andreas Stolcke , Jonathan Segal, Precise n-gram probabilities from stochastic context-free grammars, Proceedings of the 32nd annual meeting on Association for Computational Linguistics, p.74-79, June 27-30, 1994, Las Cruces, New Mexico
	Robert J. Bobrow , Bonnie L. Webber, Some issues in parsing and natural language understanding, Proceedings of the 19th annual meeting on Association for Computational Linguistics, June 29-July 01, 1981, Stanford, California
	José M. Castaño, On the applicability of Global Index Grammars, Proceedings of the 41st Annual Meeting on Association for Computational Linguistics, p.15-22, July 07-12, 2003, Sapporo, Japan
	Dan Klein , Christopher D. Manning, Parsing with treebank grammars: empirical bounds, theoretical models, and the structure of the Penn Treebank, Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, p.338-345, July 06-11, 2001, Toulouse, France
	William Schuler, Computational properties of environment-based disambiguation, Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, p.474-481, July 06-11, 2001, Toulouse, France
	John Hale, A probabilistic earley parser as a psycholinguistic model, Second meeting of the North American Chapter of the Association for Computational Linguistics on Language technologies 2001, p.1-8, June 01-07, 2001, Pittsburgh, Pennsylvania
	Mark-Jan Nederhof , Giorgio Satta, Parsing non-recursive context-free grammars, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania
	Hai-Ming Chen , Yun-Mei Dong, Practical type checking of functions defined on context-free languages, Journal of Computer Science and Technology, v.19 n.6, p.840-847, November 2004
	Naoki Yoshinaga , Kentaro Torisawa , Jun'ichi Tsujii, Comparison between CFG filtering techniques for LTAG and HPSG, Proceedings of the 41st Annual Meeting on Association for Computational Linguistics, p.185-188, July 07-12, 2003, Sapporo, Japan
	David M. Magerman , Carl Weir, Probabilistic prediction and Picky chart parsing, Proceedings of the workshop on Speech and Natural Language, February 23-26, 1992, Harriman, New York
	Ying Xu , Lusheng Wang , Hao Zhao , Jianping Li, Exact matching of RNA secondary structure patterns, Theoretical Computer Science, v.335 n.1, p.53-66, 20 May 2005
	Charles Hemphill , Joseph Picone, Chart parsing of stochastic spoken language models, Proceedings of the workshop on Speech and Natural Language, p.250-255, February 21-23, 1989, Philadelphia, Pennsylvania
	Peter Gorniak , Deb Roy, Probabilistic grounding of situated speech using plan recognition and reference resolution, Proceedings of the 7th international conference on Multimodal interfaces, October 04-06, 2005, Torento, Italy
	Jack Minker, Information storage and retrieval: a survey and functional description, ACM SIGIR Forum, v.12 n.2, p.12-108, Fall 1977
	Mary P. Harper, Stroing logical form in a shared-packed forest, Computational Linguistics, v.20 n.4, December 1994
	Erik Aarts, Uniform recognition for acyclic context-sensitive grammars is NP-complete, Proceedings of the 14th conference on Computational linguistics, August 23-28, 1992, Nantes, France
	Oliviero Stock, Parsing with flexibility, dynamic strategies, and idioms in mind, Computational Linguistics, v.15 n.1, p.1-18, March 1989
	Diego Linares , José-Miguel Benedí , Joan-Andreu Sánchez, A hybrid language model based on a combination of N-grams and stochastic context-free grammars, ACM Transactions on Asian Language Information Processing (TALIP), v.3 n.2, p.113-127, June 2004
	Ionut E. Iacob , Alex Dekhtyar , Michael I. Dekhtyar, Checking potential validity of XML documents, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France
	Yves Schabes, Polynomial time and space shift-reduce parsing of arbitrary context-free grammars, Proceedings of the 29th annual meeting on Association for Computational Linguistics, p.106-113, June 18-21, 1991, Berkeley, California
	David Milward, Incremental interpretation of Categorial Grammar, Proceedings of the seventh conference on European chapter of the Association for Computational Linguistics, March 27-31, 1995, Dublin, Ireland
	Jungyun Seo , Robert F. Simmons, Syntactic graphs: a representation for the union of all ambiguous parse trees, Computational Linguistics, v.15 n.1, p.19-32, March 1989
	Lillian Lee, Fast context-free parsing requires fast Boolean matrix multiplication, Proceedings of the 35th annual meeting on Association for Computational Linguistics, p.9-15, July 07-12, 1997, Madrid, Spain
	Hiyan Alshawi , Shona Douglas, Speech translation performance of statistical dependency transduction and semantic similarity transduction, Proceedings of the ACL-02 workshop on Speech-to-speech translation: algorithms and systems, p.31-38, July 11, 2002
	Masaru Tomita, An efficient augmented-context-free parsing algorithm, Computational Linguistics, v.13 n.1-2, p.31-46, January-June 1987
	Anthony J. Fisher, Practical parsing of generalized phrase structure grammars, Computational Linguistics, v.15 n.3, p.139-148, September 1989
	Harry Bunt , John Carroll , Giorgio Satta, Development in parsing technology: from theory to application, New developments in parsing technology, Kluwer Academic Publishers, Norwell, MA, 2004
	Mark-Jan Nederhof , Giorgio Satta, Probabilistic parsing strategies, Journal of the ACM (JACM), v.53 n.3, p.406-436, May 2006
	James H. Morris , Eric Schmidt , Philip Wadler, Experience with an applicative string processing language, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-46, January 28-30, 1980, Las Vegas, Nevada
	Adrian Johnstone , Elizabeth Scott , Giorgios Economopoulos, Evaluating GLR parsing algorithms, Science of Computer Programming, v.61 n.3, p.228-244, August 2006
	José-Luis Sierra , Ana M. Fernández-Pampillon , Alfredo Fernández-Valmayor, An environment for supporting active learning in courses on language processing, Proceedings of the 13th annual conference on Innovation and technology in computer science education, June 30-July 02, 2008, Madrid, Spain
	Carlos J. Lucena , Daniel M. Berry, Towards a definition of structured programming, Proceedings of the 1974 annual ACM conference, January 01-01, 1974
	Ulrik Schroeder , Arno Spinner, ALIEN: a programming environment generator for personal computers, Proceedings of the 1988 ACM SIGSMALL/PC symposium on ACTES, p.45-52, May 04-06, 1988, Cannes, France
	Robert Grimm, Better extensibility through modular syntax, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Elizabeth Scott , Adrian Johnstone, Right nulled GLR parsers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.4, p.577-618, July 2006
	Olivier Blanc , Matthieu Constant, Outilex, a linguistic platform for text processing, Proceedings of the COLING/ACL on Interactive presentation sessions, p.73-76, July 17-18, 2006, Sydney, Australia
	Rohit J. Kate , Raymond J. Mooney, Using string-kernels for learning semantic parsers, Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the ACL, p.913-920, July 17-18, 2006, Sydney, Australia
	Michael W. Daniels , W. Detmar Meurers, A grammar formalism and parser for linearization-based HPSG, Proceedings of the 20th international conference on Computational Linguistics, p.169-es, August 23-27, 2004, Geneva, Switzerland
	Jason Eisner , Eric Goldlust , Noah A. Smith, Compiling Comp Ling: practical weighted dynamic programming and the Dyna language, Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, p.281-290, October 06-08, 2005, Vancouver, British Columbia, Canada
	Claus Brabrand , Michael I. Schwartzbach, The metafront system: Safe and extensible parsing and transformation, Science of Computer Programming, v.68 n.1, p.2-20, August, 2007
	Gary Wassermann , Zhendong Su, Sound and precise analysis of web applications for injection vulnerabilities, ACM SIGPLAN Notices, v.42 n.6, June 2007
	Christoph Tillmann, A rule-driven dynamic programming decoder for statistical MT, Proceedings of the Second Workshop on Syntax and Structure in Statistical Translation, p.37-45, June 20-20, 2008, Columbus, Ohio
	Tim Miller , Andy Exley , William Schuler, Elements of a spoken language programming interface for robots, Proceeding of the ACM/IEEE international conference on Human-robot interaction, March 10-12, 2007, Arlington, Virginia, USA
	Stefanie Scherzinger, Bulk data in main memory-based XQuery evaluation, Proceedings of the 4th international workshop on XQuery implementation, experience and perspectives, p.1-6, June 15-15, 2007, Beijing, China
	Yong Sun , Yu Shi , Fang Chen , Vera Chung, An efficient unification-based multimodal language processor in multimodal input fusion, Proceedings of the 2007 conference of the computer-human interaction special interest group (CHISIG) of Australia on Computer-human interaction: design: activities, artifacts and environments, November 28-30, 2007, Adelaide, Australia
	Claus Brabrand , Anders Møller , Michael I. Schwartzbach, Dual syntax for XML languages, Information Systems, v.33 n.4-5, p.385-406, June, 2008
	Sylvain Degeilh , Anne Preller, Efficiency of Pregroups and the French Noun Phrase, Journal of Logic, Language and Information, v.14 n.4, p.423-444, October 2005
	Radu Gramatovici , Florin Manea, Parsing Local Internal Contextual Languages with Context-Free Choice, Fundamenta Informaticae, v.64 n.1-4, p.171-183, January 2005
	Peter Ljunglöf, Functional chart parsing of context-free grammars, Journal of Functional Programming, v.14 n.6, p.669-680, November 2004
	Jan Rekers , Wilco Koorn, Substring parsing for arbitrary context-free grammars, ACM SIGPLAN Notices, v.26 n.5, p.59-66, May 1991
	Hiyan Alshawi , Srinivas Bangalore , Shona Douglas, Head-Transducer Models for Speech Translation and TheirAutomatic Acquisition from Bilingual Data, Machine Translation, v.15 n.1-2, p.105-124, June 2000
	Elizabeth Scott, SPPF-Style Parsing From Earley Recognisers, Electronic Notes in Theoretical Computer Science (ENTCS), v.203 n.2, p.53-67, April, 2008
	Aarne Ranta, Grammatical Framework, Journal of Functional Programming, v.14 n.2, p.145-189, March 2004
	Alexander Okhotin, Unambiguous Boolean grammars, Information and Computation, v.206 n.9-10, p.1234-1247, September, 2008
	Emma Tonkin , Henk L. Muller, Semi automated metadata extraction for preprints archives, Proceedings of the 8th ACM/IEEE-CS joint conference on Digital libraries, June 16-20, 2008, Pittsburgh PA, PA, USA
	Adrian Johnstone , Elizabeth Scott, Automatic recursion engineering of reduction incorporated parsers, Science of Computer Programming, v.68 n.2, p.95-110, September, 2007
	Nic Volanschi , Christian Rinderknecht, Unparsed patterns: easy user-extensibility of program manipulation tools, Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, January 07-08, 2008, San Francisco, California, USA
	Sylvain Schmitz, An Experimental Ambiguity Detection Tool, Electronic Notes in Theoretical Computer Science (ENTCS), v.203 n.2, p.69-84, April, 2008
	Juan Miguel Garcia-Gomez , Jose Miguel Benedi , Javier Vicente , Montserrat Robles, Corpus based learning of stochastic, context-free grammars combined with Hidden Markov Models for tRNA modelling, International Journal of Bioinformatics Research and Applications, v.1 n.3, p.305-318, September 2005
	Laurence Tratt, Domain specific language implementation via compile-time meta-programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.6, p.1-40, October 2008
	Christos Pavlatos , Alexandros C. Dimopoulos , Andrew Koulouris , Theodore Andronikos , Ioannis Panagopoulos , George Papakonstantinou, Efficient reconfigurable embedded parsers, Computer Languages, Systems and Structures, v.35 n.2, p.196-215, July, 2009
	J. D. Ullman, Applications of language theory to compiler design, Proceedings of the November 16-18, 1971, fall joint computer conference, November 16-18, 1971, Las Vegas, Nevada
	James D. Mooney, The VALI (Variable Language Interpreter), Proceedings of the May 4-7, 1981, national computer conference, May 04-07, 1981, Chicago, Illinois
	Jean Bovet , Terence Parr, ANTLRWorks: an ANTLR grammar development environment, Software—Practice & Experience, v.38 n.12, p.1305-1332, October 2008
	Roland Hausser, Center Fragments for Upscaling and Verification in Database Semantics, Proceeding of the 2009 conference on Information Modelling and Knowledge Bases XX, p.22-44, July 10, 2009
	Mark-Jan Nederhof , Giorgio Satta, IDL-expressions: a formalism for representing and parsing finite languages in natural language processing, Journal of Artificial Intelligence Research, v.21 n.1, p.287-317, January 2004
	Rudi Lutz, Chart parsing of flowgraphs, Proceedings of the 11th international joint conference on Artificial intelligence, p.116-121, August 20-25, 1989, Detroit, Michigan
	Masaru Tomita, An efficient context-free parsing algorithm for natural languages, Proceedings of the 9th international joint conference on Artificial intelligence, p.756-764, August 18-23, 1985, Los Angeles, California
	Kenneth W. Church, Allophonic and phonotactic constraints are useful, Proceedings of the Eighth international joint conference on Artificial intelligence, p.636-638, August 08-12, 1983, Karlsruhe, West Germany
	John Bear, A breadth-first parsing model, Proceedings of the Eighth international joint conference on Artificial intelligence, p.696-698, August 08-12, 1983, Karlsruhe, West Germany
	Giorgio Satta , Oliviero Stock, Formal properties and implementation of bidirectional charts, Proceedings of the 11th international joint conference on Artificial intelligence, p.1480-1485, August 20-25, 1989, Detroit, Michigan
	Prasad Tadepalli , Balas K. Natarajan, A formal framework for speedup learning from problems and solutions, Journal of Artificial Intelligence Research, v.4 n.1, p.445-475, Jnauary 1996
	Adam Lopez, Translation as weighted deduction, Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics, p.532-540, March 30-April 03, 2009, Athens, Greece
	Yuji Matsumoto , Ryoichi Sugimura, A parsing system based on logic programming, Proceedings of the 10th international joint conference on Artificial intelligence, p.671-674, August 23-28, 1987, Milan, Italy
	Gal Lavee , Ehud Rivlin , Michael Rudzsky, Understanding video events: a survey of methods for automatic interpretation of semantic occurrences in video, IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, v.39 n.5, p.489-504, September 2009
	Tsunenori Mine , Rin-ichiro Taniguchi , Makoto Amamiya, Coordinated morphological and syntactic analysis of Japanese language, Proceedings of the 12th international joint conference on Artificial intelligence, p.1012-1017, August 24-30, 1991, Sydney, New South Wales, Australia
	Dekai Wu, Stochastic inversion transduction grammars with application to segmentation, bracketing, and alignment of parallel corpora, Proceedings of the 14th international joint conference on Artificial intelligence, p.1328-1335, August 20-25, 1995, Montreal, Quebec, Canada
	Richard A. Frost , Rahmatullah Hafiz , Paul C. Callaghan, Modular and efficient top-down parsing for ambiguous left-recursive grammars, Proceedings of the 10th International Conference on Parsing Technologies, p.109-120, June 23-24, 2007, Prague, Czech REpublic
	C. Gómez-Rodríguez , J. Vilares , M. A. Alonso, A compiler for parsing schemata, Software—Practice & Experience, v.39 n.5, p.441-470, April 2009
	Krasimir Angelov, Incremental parsing with parallel multiple context-free grammars, Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics, p.69-76, March 30-April 03, 2009, Athens, Greece
	Haitao Mi , Liang Huang, Forest-based translation rule extraction, Proceedings of the Conference on Empirical Methods in Natural Language Processing, October 25-27, 2008, Honolulu, Hawaii
	Tony Clark , Laurence Tratt, Language factories, Proceeding of the 24th ACM SIGPLAN conference companion on Object oriented programming systems languages and applications, October 25-29, 2009, Orlando, Florida, USA
	Dekai Wu , Yihai Shen, An efficient algorithm to induce minimum average lookahead grammars for incremental LR parsing, Proceedings of the Workshop on Incremental Parsing: Bringing Engineering and Cognition Together, p.34-41, July 25-25, 2004, Barcelona, Spain
	Jonas Kuhn, Parsing word-aligned parallel corpora in a grammar induction context, Proceedings of the ACL Workshop on Building and Using Parallel Texts, June 29-30, 2005, Ann Arbor, Michigan
	Andreas Zollmann , Ashish Venugopal, Syntax augmented machine translation via chart parsing, Proceedings of the Workshop on Statistical Machine Translation, June 08-09, 2006, New York City, New York
	Xinying Song , Shilin Ding , Chin-Yew Lin, Better binarization for the CKY parsing, Proceedings of the Conference on Empirical Methods in Natural Language Processing, October 25-27, 2008, Honolulu, Hawaii
	Klinton Bicknell , Roger Levy, A model of local coherence effects in human sentence processing as consequences of updates from bottom-up prior to posterior beliefs, Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, May 31-June 05, 2009, Boulder, Colorado
	Berthold Crysmann, Local ambiguity packing and discontinuity in German, Proceedings of the Workshop on Deep Linguistic Processing, June 28-28, 2007, Prague, Czech Republic
	Mark-Jan Nederhof, Context-free parsing through regular approximation, Proceedings of the International Workshop on Finite State Methods in Natural Language Processing, p.13-24, June 30-July 01, 1998, Ankara, Turkey
	Bing Zhao , Yaser Al-onaizan, Generalizing local and non-local word-reordering patterns for syntax-based machine translation, Proceedings of the Conference on Empirical Methods in Natural Language Processing, October 25-27, 2008, Honolulu, Hawaii
	Srinivas Bangalore , Pierre Boulllier , Alexis Nasr , Owen Rambow , Benoît Sagot, MICA: a probabilistic dependency parser based on tree insertion grammars application note, Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Companion Volume: Short Papers, May 31-June 05, 2009, Boulder, Colorado
	Yo Sato, Lexcalised parsing of German V2, Proceedings of the Workshop on Parsing German, p.1-8, June 20-20, 2008, Columbus, Ohio
	Pierre Boullier , Benoît Sagot, Are very large context-free grammars tractable?, Proceedings of the 10th International Conference on Parsing Technologies, p.94-105, June 23-24, 2007, Prague, Czech REpublic

INDEX TERMS

Keywords:
compilers, computational complexity, context-free grammar, parsing, syntax analysis

Collaborative Colleagues:

Jay Earley: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player