The formalism: Interaction Grammars (IG)

Interaction grammars are a grammatical formalism defined and developed in the Sémagramme team of INRIA. Some material is given in the pages below. For a deeper introduction about Interaction Grammars, you can refer to the paper Interaction Grammars or to the bibliography.

Syntactic trees

In Interaction Grammars (IG), the parsing output of a sentence is a syntactic tree, that is an ordered tree where nodes represent syntactic constituents described by feature structures. An example of a syntactic tree for sentence Jean la voit (John sees it) is shown in the figure below.

There are three kinds of nodes in a syntactic tree:

  • anchor nodes in vivid yellow are leaves linked with some word (written in the grey rectangle at the top of the frame representing the node); this word stands for the phonological form of the corresponding node;
  • full internal nodes in pale yellow are internal nodes with a full phonological form, which is the concatenation of those of its daughters in their order;
  • empty nodes in white are nodes with an empty phonological form; they represent traces of constituents that have moved from their canonical position (extraction, subject inversion, clitics …); in this case, the canonical position is marked with an empty node.

Two kinds of relations structure syntactic trees: immediate dominance relations, which are drawn with solid lines, and immediate precedence relations between sisters, which are drawn with arrows.

In the example above, the verb voit is a transitive verb; in a canonical use, its object is put on its right, but here the object is represented by the clitic pronoun la which is adjoined to the verb immediately before it. The trace of the canonical object is represented by the unique empty node of the tree. In order to indicate that this node and node la refer to the same entity, a special feature ref with the same index 6 labels both nodes.

Polarized Tree Descriptions

In IG, the process of syntactic composition consists in superposing partially specified trees under the control of polarities expressing the saturation state of these trees. The partially specified trees decorated with polarities are called Polarized Tree Description (PTD) because they can be viewed as sets of constraints both on the tree structure and on the feature structures of syntactic trees.

A grammar is defined as a set of PTDs representing elementary syntactic constructions, called Elementary PTDs (EPTDs). A grammar is (stricly) lexicalized if every EPTD of the grammar is anchored by one word of the language at least (exactly one word).

The parsing of a sentence with a given stricly lexicalized grammar is initialized by selecting one EPTD from the grammar for each word of the sentence. For instance, here is a possible selection from the FRIGRAM grammar for parsing the sentence Jean la voit.

Graph Graph Graph Graph

Since punctuation signs are considered as words, the selection is constituted of 4 EPTDs. Each EPTD represents a syntactic construction in which the corresponding word is used. For instance, the EPTD anchored with the verb voit expresses its transitivity. The root represents the sentence that has the verb voit as its head. This node has 3 daughters, which are from the left to the right: the subject, the verbal kernel (the verb with its possible modifiers and clitics) and the object. Solid lines represent immediate dominance relations and dashed green arrows represent strict precedence relations between nodes. For instance, there is a strict precedence relation between the verbal kernel and the object. The object is put after the verbal kernel but not necessarily immediately after it. It is possible to express that a node is the leftmost or the rightmost daughter of a given node, with an orange rectangle put on the left or the right of the node. The fact that a full stop is at the end of sentence is expressed in this way in the last EPTD.

As in syntactic trees there are three kinds of nodes according to their phonological form, in a PTD, there are four possible kinds of nodes: anchor nodes, full internal nodes, empty nodes and undespecified nodes in grey; an underspecified node can take any of the previous phonological forms.

Every node is labelled with a feature structure describing the morphological, syntactic and semantic properties of the corresponding constituent. There are two kinds of features :

  • Classical features, which are pairs (name of feature, value) denoted as name of feature = value. For instance, agreement features, such as gen=f, num=sg, pers=3, are classical features.
  • Polarized features, which are triples (name of feature, polarity, value). Polarities are used to express saturation constraints. A positive polarity, denoted →, describes an available resource; it must be associated with a dual negative one, denoted ←, which describes an expected resource. A saturated polarity, denoted ↔, is self-sufficient and need no combination with any other polarity. A virtual polarity, denoted ~, expresses that some context is required: it must be associated to another non virtual feature to be saturated.

In the EPTD anchored with the verb voit, the subject node is equipped with two polarized features, cat ← np and funct → subj, which mean that the verb expects one noun phrase exactly to provide it with one syntactic function, the function subject. In a dual way, the root of the EPTD anchored with the proper noun Jean is equipped with two polarized features, cat → np and funct ← ?, which mean that exactly one noun phrase is available which expects one syntactic function exactly. The saturation of these polarities will be realized by merging this root with the subject node of the EPTD anchored with voit.

In the EPTD anchored with the clitic pronoun la, the mother node of the anchor carries one polarized feature cat ↔pro, which is saturated. Such a node needs no interaction with other nodes. It has a sister node representing the verb that will be cliticized and carrying a virtual feature cat ~ v|aux. It means that such a node needs to merge with a real verb or auxiliary node (eventually carrying a saturated feature cat ↔ v or cat ↔ aux). The difference between positive-negative polarity interactions and saturated-virtual interactions is that the formers are one-to-one (linear) interactions, whereas the latters are one-to-many (non linear) interactions. In the example, virtual features are used to express constraints about the syntactic environment in which the clitic pronoun is put: it requires a verb or an auxiliary after it to build a cliticized verbal kernel, which contains the head of a sentence. An empty node represents the trace of a noun phrase providing the object of a transitive verb. The possible interaction with such a transitive verb is expressed with the polarized features cat→np and funct ← obj.

Parsing as superposition of PTDs under the control of polarities

The parsing of a sentence with a strictly lexicalized interaction grammar starts with a selection of an EPTD from the grammar for each word of the sentence. Then, the selected EPTDs are superposed step by step to saturate their polarities and to build more specified PTD. Parsing succeeds if the computation terminates with a unique and completely specified tree, where all polarized features are saturated.

Consider the previous example of the sentence Jean la voit. The selected EPTDs are given above. A first step consists in saturating the polarized features of the EPTD anchored with la. The only way of doing it is to merge the empty node containing these features with the object node of the EPTD anchored with voit. At the same time, the node representing the virtual cliticized verb is merged with the node representing the real verb voit.


In a second step, the node representing the noun phrase anchored with Jean saturates its polarized features by merging with the subject node of the EPTD anchored with voit.


In a last step, the root of the EPTD anchored with the full stop saturates the tree representing the syntax of Jean la voit.


The resulting PTD has a unique model, the syntactic tree given in the example above.

Underspecified dominance relations in PTDs

As there are underspecified precedence relations in PTDs, there are also underspecified dominance relations with a difference: underspecification must be understood in a large sense; if a node A dominates a node B, it means that A is an ancestor of B or equal to B in all syntactic trees that are models of the PTD.

For instance, the relative pronoun que represents a direct object which is extracted from a relative clause but the extracted object may come from an object clause embedded more or less deeply in the relative clause through a stack of other object clauses as in the following examples:

  • Je connais la fille que Jean veut rencontrer. (I know the girl whom Jean wants to meet)
  • Je connais la fille que Pierre pense que Jean veut rencontrer. (I know the girl whom Pierre believes that Jean wants to meet)

In the first example, the object of rencontrer is extracted through one embedded object clause: rencontrer. In the second example, there are two embedded object clauses: rencontrer and que Jean veut rencontrer. A same EPTD from Frigram is used to model both usages of que.


In this EPTD, the trace of the extracted object is represented with an empty node. The mother A of this node represents the object clause in which the trace is an immediate sub-constituent; in the second example, this clause reduces to rencontrer. It is embedded more or less deeply in another clause which is the object of the head verb of the relative clause; in the second example, this is que Jean veut rencontrer. This second object clause is represented with a node B, which dominates A in an underspecified dominance relation, repreesented with a dashed green line. The line is labelled with a set of features expressing constraints on the nodes between A and B: all nodes must represent object clauses (object of modal verbs are distinguished with a specific function modal).