Mathematical and Computational Infrastructure for Grammar Engineering

Project description

Objective: To develop methods and techniques for grammar engineering, especially with respect to modularizing grammar design.

Researchers: Yael Sygal and Shuly Wintner. In collaboration with Nurit Melnik, the Open University.

Status: Complete

Funding: Israeli Science Foundation (grants 136/01, 505/11).

Abstract

Linguistic theories are now so mature that it is possible to describe linguistic analyses using for- mal grammars. Such grammars are written in formal languages, called grammatical formalisms, that resemble very high level, declarative (mostly logical) programming languages. Grammars for natural languages are thus very similar to computer programs. However, while computer programmers can benefit from two decades of research in software engineering, grammar engineering is still in its infancy. The proposed research will apply methods and techniques of programming language theory and software engineering to grammatical formalisms and grammar engineering, and will thereby provide the necessary infrastructure for modular construction of large grammars for natural languages. Such an infrastructure will include a set of grammar combination operators that are useful for grammar developers, a formal semantics that is compositional and fully-abstract with respect to this set of combination operators and a formal definition of grammar modules. It will make it possible to mathematically prove the correctness of a grammar, with respect to an independent definition; to construct provably correct parsers and generators for modular grammars; to implement several optimizations on compiled grammars, relying on the equivalence of different grammars; etc.

Resources

None.

Publications

• Yael Sygal and Shuly Wintner. Towards Modular Development of Typed Unification Grammars. Computational Linguistics 37(1):29-74, March 2011. 

• Yael Sygal and Shuly Wintner. Associative Grammar Combination Operators for Tree-Based Grammars. Journal of Logic, Language and Information, 18(3):293-316, July 2009. 

• Yael Sygal and Shuly Wintner. Type Signature Modules. In Philippe de Groote (Ed.) Proceedings of FG 2008: The 13th conference on Formal Grammar, pages 113-128, Hamburg, Germany, August 2008.

• Yael Cohen-Sygal and Shuly Wintner. The Non-Associativity of Polarized Tree-Based Grammars. In Gelbukh, A., editor, Proceedings of the Conference on Computational Linguistics and Intelligent Text Processing (CICLing-2007), volume 4394 of Lecture Notes in Computer Science, pages 208-217, Berlin and Heidelberg: Springer, February 2007. 

• Yael Cohen-Sygal and Shuly Wintner. Partially Specified Signatures: A Vehicle for Grammar Modularity. In Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, pages 145-152, Sydney, Australia, July 2006.