Grail Tutorial - Structural Rules and Modes

In our context, structural rules are rewrites from one tree of main constructors into another tree of main constructors. Both trees need to have the same leaves, though we can change their order if we want.

Associativity

Load the example grammar hitchhiker.pl which is part of Grail's set of example grammars. You can see the structural rules of a grammar by selecting [Window/Structural Rules Window (Postscript)] from the main window or by directly opening the file structural_rules.dot in the current working directory. For the current grammar, the result is shown below.
The structural rule of associativity
There are two rules and each of them relates two trees, which are displayed inside of a blue square. An arrow with a name indicates the name of the tree rewrite. Each rewrite allows us to replace the tree on the left hand side of the rule by the tree on its right hand side.

It is important to remember here that the left-to-right order of the leaves is indicated by the labels 1 (for left) and 2 (for right), contrary to what the visual representation may suggest. Therefore, the [Ass1] rule applies whenever we have a tree with root E and leaves A, B and C, with C being the right daughter of the root and the internal node D being the left daughter of the root. This node D, then has A as its left daughter and B as its right daughter. That is to say, for every node A, B, C, D and E which are in the configuration shown on the left hand side of the figure we can apply this rule.

When we apply a rule, we replace its left hand side by its right hand side. In this case we replace a tree which has A and B as daughters of an internal node (with A occurring to the left of B) and C as daughter of the root node E (occurring to the right of B) by a tree where A is the left daughter of the root node and B and C are sisters of a new internal node F. The yield of both trees is A B C, only the internal structure has changed.

Parsing with associativity

As an example of the use of associativity, look at the lexical lookup for "Everyone likes someone" below. This is a classical example from Montague semantics, which has two readings: one reading is true whenever everyone has at least one person they like ("everyone" has wide scope, or ∀x∃y.like(x,y) in first order logic), the second when there is someone who is liked by everyone ("someone" has wide scope, which corresponds to the first order logic formula ∃y∀x.like(x,y)).
Lexical lookup for [Someone
loves everyone]
For the lexical lookup shown above there are two possible ways to perform the substitutions, each of them corresponding to one of the semantic readings (all of this is explained in more detail in the section about semantics) and they both require the application of the structural rule of associativity. We will derive one of the two readings and see how it depends on associativity. Perform the substitutions follows. Start by substituting 15 for 16. This will link "someone" to the goal (the existential quantifier will therefore have wide scope in this reading). Now, there are no more choices to make. Continue linking the remaining s formulas, 2 to 14 and 9 to 4, then link the two np formulas, 5 to 8 and 13 to 10. After the final substitution has been performed, you will see the following figure.
Lexical lookup for [Someone
loves everyone]
Grail uses a shared forest representation as a compact way to describe the applications of structural rules on a tree of constructors. In the literature on proof nets, such a tree of main constructors is called a component. Visually, a component which has been expanded by structural rules applications is shown in black, whereas other components are shown slightly greyed out as shown in the figure above. We say a component is active if there are no arrows from auxiliary constructors arriving at the nodes inside of it. An auxiliary constructor is active whenever it attached to an active component.

The graph shown above has three components, With respect to the auxiliary constructors, only one of the auxiliary constructors is active, as indicated by the blue color, and it is attached to to the component which is represented as a shared forest at node 9 (the root node) and at node 5 (one of the leaves).

The shared forest represents a combination of two trees. The first tree passes through internal node 7. In this tree node 5 is the left daughter of the root node 9 (we can reach it by path 1) and node 7 is the right daughter of the root node. From node 7, we can reach the two other leaves: 6, which is the left daughter of node 7, and 13, which is its right daughter. The second tree passes through internal node 17. In this tree node 13 is the right daughter of the root node whereas node 17 is its left daughter. From node 17, we can reach its left daughter 5 and its right daughter 6. Remark that both trees have the same yield 5, 6 (likes), 13 even though the figure suggests otherwises.

Now, given that the auxiliary link is connected to node 9 by its path 3 and to node 5 by its path 1 we need to contract it with a main link which is connected to node 9 by path 3 and to node 5 by path 1 as well. The auxiliary node attached to the internal node 7 fills this role exactly. Therefore, we contract the two links, while erasing the links which are no longer reachable. After the contractions, the components on both sides of the eliminated auxiliary link are joined and we apply the structural rules again. This gives the figure shown below.

Lexical lookup for [Someone
loves everyone]
The shared forest representation is similar to the one in the figure before the contraction. It again represents two trees, this time with yield 1 (everyone), 6 (likes), 13. Node 13 is the rightmost node and we can reach it either directly from the root (using the connection which has 18 as its left daughter) or passing through node 3, following two 2-labeled paths. The main constructor on the first path to node 13 is the one we need for the contraction. It is connected to the auxiliary constructor by node 13 through path 2 and by node 2 through path 3. Therefore, we can contract as we did before, join the two components and reapply the structural rules and obtain the final shared forest shown below.
Lexical lookup for [Someone
loves everyone]

Partial Associativity

An advantage of the current setup is that we can now specify lexically where we want associativity to apply and where we don't want it to apply. The current grammar has two modes a and 0 and the associativity rule applies only when a pair of modes a occurs together. A single connection of mode 0 will 'interrupt' a path of applications of the associativity rule.

What's Next

See the unary branches if you haven't seen them yet, or see everything together in the section on multimodal grammars.
Richard.Moot@labri.fr
Last modified: Mon Mar 2 00:06:52 CET 2009