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.
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)).
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.
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.
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.
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