Theme: A Principle Compiler for Extensible Dependency Grammar

Saarland University
Programming Systems
Jochen Setz

Bachelor Thesis

If you can read this, your browser provides insufficient support for style sheets. The visual presentation of this document will suffer.
Author: Jochen Setz
Time frame: April 07 -September/Oktober 07
Advisor: Ralph Debusmann
Responsible Professor: Prof. Dr. Gert Smolka


Analyses in the Extensible Dependency Grammar (XDG) framework for dependency grammars are represented in XDG by multigraphs. Grammars consist of a lexicon and a set of principles, and restrict the possible multigraphs. Example principles are "no cycles", "one root" and "zero or one mother", which act together to constrain a dimension of the multigraph to be a tree. Other principles stipulate valency and order constraints. Principles are formalized in a specialized first-order logic.

The XDG Development Kit (XDK) is a grammar development kit for XDG, including a parser implemented using constraint programming in Mozart/Oz. The XDK comes with a principle library of predefined principles, from which grammars can be built as with lego bricks. All principles of the XDG principle library, as laid out in Debusmann 2006, are implemented efficiently as Mozart/Oz constraints.

However, the transformation of a principle formalized in first-order logic into an efficient implementation as a Mozart/Oz constraint is far from trivial, and can only be managed by experts in both Mozart/Oz and the XDK, and even for them, the task is tiresome. This also prohibits typical grammar writers, e.g. computational linguists, from extending the principle library, and testing out new ideas.

Task description

In the thesis, we plan to bridge the gap between logically described principles and their efficient implementation as Mozart/Oz constraints by developing a compiler called "PrincipleWriter".

The PrincipleWriter will automatically compile principles specified in first-order logic into efficient implementations as Mozart/Oz constraints. This will allow a larger userbase to make full use of the "extensibility" aspect of XDG, i.e., to add and test new ideas for principles.

Starting from a first prototype, the main objective of the thesis will be on finding out how to automatically optimize the compiled principles. It will be interesting to find out how close these optimization can bring us to the level of efficiency of the already implemented principles in the XDK principle library.

A side objective of the thesis will be the integration of PrincipleWriter with the XDK principle library, e.g. with a GUI to easily add/remove/change/compile principles to the system.


  1. Ralph Debusmann (2006)
    Extensible Dependency Grammar: A Modular Grammar Formalism Based On Multigraph Description
    PhD thesis (revised version)
  2. Ralph Debusmann (2007)
    Scrambling as the Intersection of Relaxed Context-Free Grammars in a Model-Theoretic Grammar Formalism
    ESSLLI 2007 Workshop Model Theoretic Syntax at 10, Doublin


The slides from my introductory talk (pdf), the thesis (pdf), the slides from my final talk (pdf)