Grail Tutorial - Parsing AB Grammars

Parsing example sentences

As we have seen, once Grail has loaded a grammar file, the main window lists the example sentences for a given grammar. The current section continuous using the grammar file grail0.pl used for the previous sections, so (re)load it if necessary. Lexical trees for the
sentence [Lancelot rescues Galahad]

Clicking on one of the example sentences will display the corresponding phrase in the Phrase entry field below the examples and the goal category for this phrase in the Goal entry field. The <cursor up> and <cursor down> keys will move to the previous and next example phrase respectively. Lines starting with --- are comments about the phrases and will therefore not be displayed in the Phrase and Goal entry fields.

To start parsing a phrase, select the example phrase you want to parse followed by pressing the [Parse] button. You can also double-click the phrase you want to parse or enter a phrase in the Phrase entry field followed by the <Enter> key.

To begin with, parse the first sentence: "Lancelot rescues Galahad", by selecting it and pressing the [Parse] button.

Grail starts by looking in the lexicon for the trees which correspond to the words in the sentence. Once a tree has been found for each of the words, the result, at least for the sentence "Lancelot rescues Galahad", should look as shown in the figure.

We have two simple noun phrases "Lancelot" (which is node 1) and "Galahad" (which is node 7). The verb "rescues" is a transitive verb (like "dismembers" from the previous section) and therefore has the same lexical tree assigned to it (again up to renumbering of the nodes).

Finally, node 8 is the goal category: it states that we a looking for a tree of category s.

In order to find a parse for the given sequence of trees we need to identify all positive (conclusion) and negative (hypothesis) nodes which have an atomic category assigned to them (in our example, the np and s categories). The result is a tree such that all of its leaves are words from the lexicon and its root is connected to the goal.

The requirement that all atomic categories of positive and negative nodes are identified is an important restriction: it implies that we use exactly the "material" we have at our disposition, nothing more, nothing less. Therefore, "Lancelot rescues" is invalid since a noun phrase would be missing: the transitive verb would not find the object it needs. Similarly, the sentences "Lancelot rescues Galahad Arthur" would have a noun phrase too many and would therefore not be a valid sentence either.

A final requirement on the resulting tree is that the yield of this tree has the words of the sentence in the correct order.

Performing substitutions manually

The atom selection window for the
sentence [Lancelot rescues Galahad] After displaying the lexical lookup in the Graphviz window, Grail will by default ask you to select which substitution you want to perform. A window with the possible substitutions will open. For the current example, the window should look as shown in the figure. Grail will not consider links which cannot lead to a valid derivation (this is described in more detail in a later section). In addition, Grail will keep track of the substitutions which have already been tried and eliminate them from the current possibilities.

The atom selection window has a set of five toolbar buttons below the title and at the bottom there is a square grid for each of the atomic formulas occurring in the current sentence. Here, the possibilities for np are shown on the left, whereas the possibilities for s are shown on the right.

Given that the number of positive and negative occurrences has to be equal for each of the categories the possibilities for each category are in a square grid, with negative occurrences of the items (ie. things we have) in the rows and positive occurrences (ie. things we need) in the columns. Items which have been excluded or which have already been tried are shown as empty rectangles. For example, the substitution 1-6 is excluded since it would produce a sentence containing "rescues Lancelot", that is, the yield of the result tree would not correspond to a parse of "Lancelot rescues Galahad". The different methods used by Grail to exclude substitutions are discussed in detail in the section on optimization.

This window will not appear if there is a different number of positive and negative occurrences for a category, though in these cases the Graphviz window will still display the sequence of lexical trees in order to help you identify the problem and correct it if you want to. Derived tree for the
sentence [Lancelot rescues Galahad]

You will notice that with the substitutions 1-6 and 4-7 excluded, there is only one set of substitutions possible for this example: 1-4 and 7-6 for the noun phrases and 5-8 for the sentence category. Perform these substitutions by clicking on the corresponding buttons. The result is a tree with no remaining or missing categories and with yield "Lancelot rescues Galahad" as required.

Exercise 1.1 In order to familiarize yourself with the manual substitutions, try to find a derivation for all sentences in the AB section of the grammar.

Exercise 1.2 Verify what happens when you try to parse the following two sentences.

  1. Lancelot rescues.
  2. Lancelot rescues Galahad Arthur.
Remember that you can parse sentences which are not already in the grammar by typing the string into the Phrase entry field and selecting s in the Goal field.

The toolbar buttons

In addition to the buttons for performing substitutions, the atom selection window has a set of five toolbar buttons. They are portrayed at the top of the window above the atom grids. You can remind yourself which button does what by keeping the pointer over one of then, which will cause a short help message to appear.

The fail toolbar button This is the Fail button. It abandons the current parse and lets you select an alternative path in the search space. You can use this button to abandon parses which you know cannot succeed. Use this button with caution, though, since if it is possible to complete the current partial parse, you will miss a solution.

The step toolbar button The Step button lets Grail choice the atom connections one by one. Grail will always select one of the atoms which has the least possible substitution possibilities.

The fast-forward toolbar button The Fast-forward button will let Grail perform substitutions until the moment when all atoms have been connected and a solution has been found.

The next lookup toolbar button The Next lookup button will abandon the current lexical lookup. If the grammar has another sequence of possible trees for the current grammar, it will be tried immediately. Like the Fail button, you have to be careful not to miss any possible parses because of this. You can use this if you just interested in one of the possible sequences of lexical trees for the current sentence.

The stop toolbar button The Stop button will abandon the current parse immediately. Again, you need to be careful not to accidentally miss parses because of this button.

Link Mode Options

The [Options] menu has an item [Options/Link Mode]. This allows you to globally change the way Grail parses sentences. By default the link mode is set to Manual which allows you to select the atomic formulas to be identified yourself.

If you want Grail to take care of all substitutions, set the link mode to Auto: the atom selection window will never appear and Grail will only inform you when it finds a solution. This is a bit like the Fast-forward toolbar button, except that the Fast-forward button gives control back to you when a solution has been found.

When link mode is set to Partial, Grail will automatically perform a substitution whenever it is the only possibility for an atomic formula. Your input is only asked when a real choice has to be made for the substitutions.

The final possibility, K-best, is like Auto in that it performs axioms links without your input. An important difference is that K-best performs only some, that is k, of the possible the axiom connections. This option is described in more detail in one of the advanced sections.

It is recommended that you keep the link mode set to Manual for the rest of this tutorial.

What's Next

We have complete our section on parsing AB grammars. It is worth the effort to familiarize yourself with atom selection window and try to analyse a few of the other sentences in the AB section of the grail0.pl grammar.

The next section will introduce the lexical graphs for the non-associative Lambek calculus.


Richard.Moot@labri.fr
Last modified: Wed Jun 10 17:11:41 CEST 2009