XMG (eXtensible MetaGrammar) is a metagrammar compiler which has already been used for the design of large scale Tree Adjoining Grammars and Interaction Grammars. Due to the heterogeneity in this field (different grammar formalisms, different languages, etc), a particularly interesting aspect to explore is modularity. In this paper, we discuss the different spots where this modularity can be considered in a grammar development, and its integration to XMG.
end up at an arbitrary distance from each other. Here, we will only manipulate LTAG (lexicalized-TAG), which means each elementary tree is associated with at least one lexical element.
What can we do to lower the amount of work implied by the conception of the grammar ? Let us take a look at some rules:
S
V⋄ N ↓
N ↓ Sally sings a song the song
N⋆ Those two trees share some common points: part of the structure is the same (the subject is placed before the verb in both circled parts), and the agreement constraints, given in feature structures associated to nodes (not represented here), are similar. This kind of redundancy is one of the key motivations for the use of abstractions. These abstractions are descriptions of the redundant fragments we can use everywhere they are needed.
Metagrammars are based on the manipulation of those linguistic generalizations.
They consist in generating the whole grammar from an abstract description, permitting
to reason about language at an abstract level. The metagrammatical language we will
deal with here is XMG (eXtensible MetaGrammar) 1, introduced in [
We will begin pointing out the modularity on the grammar side in section 2. In section 3, we will focus on a new level of modularity, a metagrammatical one. In section 4, we will give an overview of what has been done, and what remains to be done. Finally, we will conclude and give some perspectives. 2
XMG consists in defining fragments of the grammar, and controlling how these fragments can combine to produce the whole grammar. The following figure shows the intuition of the combination of fragments to produce a tree for transitive verbs. It is done by combining three tree fragments, one for the subject (in its canonical form, that
we noticed redundant previously), one for the object (relative) and one for the active form.
V⋄
N⋆
S
The control language and the dimension system The main particularity of XMG is that it allows to see the metagrammar as a logical program, using logical operators.
The abstractions (possibly with parameters) we manipulate are called classes. They contain conjunctions and disjunctions of descriptions (tree fragments descriptions for TAG), or calls to other classes. This is formalized by the following control language:
Class Content := :=
Name[p1 , . . . , pn ] → Content hDimi{Desc} | Name[. . . ] | Content ∨ Content | Content ∧ Content For example, we can produce the two trees of the figure 1 by defining the tree fragments for canonical subject, verbal morphology, canonical object and relativized object, and these combinations:
Object → CanObj ∨ RelObj
Transitive → CanSubj ∧ Active ∧ Object This part of metagrammar says that an object can either be a canonical object or a relative object, and that the transitive mode is created by getting together a canonical subject, an active form and one of the two object realizations.
Notice that descriptions are accumulated within dimensions, which allow to separate types of data. Sharing is still possible between dimensions, by means of another dimension we call interface. In XMG’s TAG compiler for example, the syn dimension accumulates tree descriptions while the sem dimension accumulates predicates representing the semantics. Each dimension comes with a description language, adapted to the type of data it will contain. For each type of description we need to accumulate, we have to use a different description languages. The first version of XMG provides a tree description langague (for TAG or Interaction Grammars) associated with the syn dimension and a language for semantics associated with the sem dimension. A tree description language For trees in TAG, we use the following tree description language:
Desc := x → y | x →+ y | x →∗ y | x ≺ y | x ≺+ y | x ≺∗ y | x[f :E] | x(p:E) | Desc ∧ Desc where x and y are node variables, → and ≺ dominance and precedence between nodes (+ and ∗ respectively standing for transitive and reflexive transitive closures). ’:’ is the association between a property p or a feature f and an expression E. Properties are constraints specific to the formalism (the fact that a node is a substitution node for example), while features contain linguistic information, such as syntactic categories, number or gender.
When accumulated, the tree description in the syntactic dimension is still partial. The TAG elementary trees that compose the grammar are the models for this partial description. They are built by a tree description solver, based on constraints to ensure the well-formedness of the solutions. XMG computes minimal models, that is to say models where only the nodes of the description exist (no additional node is created). Here is a toy metagrammar, composed of three description classes (representing canonical subject, relative object, active form) and one combination class (transitive mode): CanSubj →hsyni{(s1[cat : S] → v1[cat : V ]) ∧ (s1 → n1(mark : subst)[cat : N ]) ∧ (n1 ≺ v1)} ∧ (n3 ≺ s2) ∧ (s2 → c) ∧ (s2 → s1[cat = S]) ∧ (c ≺ s1) ∧ (c → wh[cat = wh]) ∧ (s1 → n1[cat = n])} RelObj →hsyni{(n2[cat = N ] → n3(mark = adj)[cat = N ]) ∧ (n2 → s2[cat = S]) Active →hsyni{(s1 → v2[cat : V ])} T ransitive →CanSubj ∧ RelObj ∧ Active
The minimal models for the classes named CanSubj, Active and Object are the trees with matching names on the previous figure. The tree Transitive is a minimal model for the description accumulated in class Transitive.
A language for semantics To describe semantics, we use another description language, which is:
SemDesc := ℓ : p(E1, ..., En) | ¬ℓ : p(E1, ..., En) | Ei << Ej | E where ℓ is a label for predicate p (of arity n) and << is a scope-over relation for dealing with quantifiers. To add binary relations to the semantic dimension, we can use a class of this type:
BinaryRel[P red, X, Y ] → hsemi{P red(X, Y )} When instantiated with P red=love, X=J ohn, Y =M ary, calling the class BynaryRel accumulates the predicate love(J ohn, M ary).
Principles Some additional sets of constraints we call principles are available. Their goal is to check some properties in the resulting models of the compilation, they are consequently dependent from the target formalism. For example, in TAG, the color principle is a way to forbid some fragments combination, by associating colors to each node.
When unifying nodes, their colors are merged: a red node must not unify, a white node has to unify with a black node, creating a black node, and a black node can only unify with white nodes. The only valid models are the ones in which every node is colored either in red or black. The following table shows the results of colors unifications.
•b •r ◦w ⊥ •b ⊥ ⊥ •b ⊥ •r ⊥ ⊥ ⊥ ⊥ ◦w •b ⊥ ◦w ⊥ ⊥ ⊥ ⊥ ⊥ ⊥
For example, if we consider our previous example, the colored trees of the metagrammar are the following:
S◦W N•B
V◦W CanSubj
C•R
S◦W
S•B →
C•R
S•B W h•R N◦W
RelObj
V•B
Active
The tree description solver (ignoring the colors) will produce models where the nodes labelled S of CanSubj and Active unify with any of the two nodes labelled S in RelObj, where the nodes labelled V do not unify, etc. But when filtering with the colors principle, the only remaining model is the one of the right, which is linguistically valid, contrary to the others.
We can also cite the rank principle: we use it to add constraints on the ordering of nodes in the models of the description. In French for example, clitics are necessarily ordered, so we associate a rank property to some nodes, with values that will force the right order. 3
The main aim of the XMG-2 project is to make it possible for the linguist to design new metagrammatical scopes, that can accomodate any linguistic theory. A simple way to
N•R N•R
S•R
N•R N•R
S•R W h•R N•B
V•B realize this ambition is to provide a set of bricks the user can pick to build the compiler he needs. Those bricks could be used to design new dimensions, with new description languages or new principles. 3.1
A modular architecture XMG compiler comes with a modular processing chain. Most of this chain is a standard compiling chain, including a tokenizer for the metagrammar, a parser, an unfolder, etc.
The particularity of XMG is to make it possible to chose the modules that suits the
best his metagrammar. By this mean, descriptions accumulated in different dimensions
can be handled differently. For example, the end of the processing chain for TAG is a
tree description solver, that builds the grammar’s elementary trees from the
descriptions accumulated in the syntactic dimension. The user can chose the kind of output
the compiler will produce: he can interactively observe the grammar he produced, or
produce an XML description of the grammar. This description can be used by a parser
(for example TuLiPA [
Representation modules As we wish to build a tool which is as universal as possible, being independent from the formalism is a priority. To achieve this goal, we need to be able to describe any type of structure into XMG. We saw the dimension system was useful to separate syntax from semantics. It could also be used to separate tree descriptions from constraints based descriptions, as long as we have a dedicated dimension, with a dedicated description language.
In [
Obligation A : △B at least one B child
Uniqueness A : B! at most one B child
Linearity A : B ≺ C B child precedes C child
Requirement A : B ⇒ C if a B child, then also a C child
Exclusion A : B 6⇔ C B and C children are mutually exclusive
Constituency A : S children must have categories in S
A real size PG consists in a inheritance hierarchy of linguistic constructions. These
constructions are composed of feature structures and a set of properties. Variables are
manipulated on both sides, and can be used to share data between them. Figure 3
represents a part of the hierarchy built in [
V (Verb)
INTR ID—NATURE hSCAT 1 .SCATi const. V : 1 CAT V
SCAT ¬ (aux-etre ∨ aux-avoir) V-m (Verb with modality) inherits V ; V-n
"RECT 1 # INTR SYN INTRO DEP Prep uniqueness Prep! requirement 1 ⇒Prep linearity 1 ≺Prep V-n (Verb with negation) inherits V
"RECT 1 # INTR SYN NEGA DEP Adv-n uniqueness AAddvv--nngp ! requirement 1 ⇒Adv-n linearity Adv-ng≺ 1
Adv-ng≺Adv-np Adv-np≺ 1 .[MODE inf] 1 .[MODE ¬inf] ≺Adv-np and an linear order must be respected (ne must come before pas). When the mode of the verb is infinitive, the verb must be placed after the adverbs.
To describe a PG, we need to be able to represent encapsulations, variables, feature structures, and properties. We can notice that XMG classes can be seen as encapsulations, and that variables and features structures were already used for TAG descriptions. Considering that, the XMG description language for PG can be formalized this way:
DescPG := x = y | x 6= y | [f :E] | {P } | DescPG ∧ DescPG
P := A : △B | A : B! | A : B ≺ C | A : B ⇒ C | A : B 6⇔ C | A : B where x, y correspond to unification variables, = to unification, 6= to unification failure, : to association between the feature f and some (possibly complex) expression E, and {P } to a set of properties. Note that E and P may share unification variables. The translation of the linguistic construction for V-m in XMG would be: V −m → (V class ∨ V −n) ∧ hP Gi{[INTR:[SYN:[INTRO:[RECT:X, DEP:Prep]]]] ∧ (V : Prep!) ∧ (V : X ⇒ Prep) ∧ (V : X ≺ Prep)}
Here, inheritance is made possible by calls of classes. The control language even allows to do disjunctive inheritance, like it happens in class V-m. The end of the compilation process for PG will differ from TAG’s one. We don’t need any solver for descriptions, the accumulation into PG dimension is the grammar. To get the properties solved for a given sentence, the solution is to use a parser as a post processor for the compiler.
Nevertheless, including a specific representation module to the compiler can be seen as an ad-hock solution. That is why allowing the linguist to build his own description language (for example, choosing to use feature structures, dominance relations between nodes, open unification, etc), would be an essential feature. 3.3
Principle bricks
The notion of principles defined in XMG was too restrictive for our aims. Their
specificity for the target formalism, for example, is incompatible with the multi-formalism
ambition. An interesting way to handle principles is the one of [
Dynamic definition of a metagrammar To build his own metagrammatical scope, one should only have to select the dimensions he needs and the properties he wants to check on them. Building a dimension would consist in picking bricks out from a library to create a new description language. With this feature, a user could redefine the property grammars description we proposed earlier. The advantage here is that the specific part of the compiler is written automatically, and new features could be added just for experiments. Defining the principles would just consist in taking meta-principles out from the library and instantiate them.
Building a metagrammar compiler in this way allows to deal with a large range of linguistic theories, or even to quickly experiment while creating a new grammar formalism. 4
XMG project started in 2003 with a first tool, that has been used to produce large
TAG grammars for French [
Consequently, a new implementation started in 2010, in YAP (Yet Another Prolog)
with bindings with Gecode for constraints solving. XMG-2 is currently the tool used
for modeling the syntax and morphology of Ikota, a bantu language [
In this paper, we showed how modularity, together with a metagrammatical approach, eases the development of a large scale grammar. This modularity is essential for reaching the main goal of XMG, that is to say extensibility. Getting to that means taking a big step towards multi-formalism and multi-language grammar development, and then offers new possibilities for sharing data between different types of grammar, or even for comparing them.
Now, what we would like to create is a way to express the definition of dimensions and meta-principles. This could begin by formalizing a description language for description languages. We also aim to provide more checking tools to the user, beginning with the type checking of the properties and the feature structures we manipulate in a lot of grammar formalisms.