Recursive transition networks

  1. Generating sentences from a grammer
  2. Nested Networks
  3. Python generators
  4. Matching input sentences
  5. The match generator
  6. Retrieving the sentence structure
  7. Recursive networks
  8. Parsing another language
  9. Pratical considerations

Recursive transition networks (RTN) are useful devices for representing grammers in both human and computer languages. The kind of grammers that can be represented with RTN's are called context-free. The consist of rules for how words may be put together into structures and, in turn, how those structures may be built into larger structures. For a particular grammer a valid sentence is a list of words that follow the rules of the grammer.

The computer language Pascal (among others) is formally defined using RTN's.

Here is a very simple example. The grammer in figure 1 consists of a single sentence, the word red followed by the word book.

For our purposes an alternative, but equivalent, format is more useful because it is easily translated into a Python dictionary. The network consists of nodes (1, 2, END) connected by named arcs. The name of an arc indicates what word(s) will carry one from one node to another, and in which direction. You traverse the network by starting at node 1 and finding a path to node END.

And here is one way to represent the network in Python

simple1 = {TITLE: "simple1",
            1: [("red", 2)  ],
            2: [("book", END)]
           }

The nodes in the network are key/value pairs in a dictionary. The key is the name of the node and the value is a list of arcs. Each arc is a two valued tuple describing the word and destination. The END node does not need to be defined since no arcs emanate from it. A special key/value pair is used for a title. TITLE and END are simply defined constants.

Let's move on to a somewhat more interesting grammer. Figure 3 describes a grammer that consists of the word book preceded by one or more words red. So red book and red red red book are both valid sentences in the grammer.

And here is the Python version.

simple2 = {TITLE: "simple2",
           1: [("red", 2)  ],
           2: [("red", 2), ("book", END)]
           }

Generating sentences from a grammer

It's easy to write a python function that will generate a random sentence in a grammer. For our simple non-recursive grammers above the following function works well.

def gen1(network) :
    "Generate random sentence from network. Non recursive"
    p = network[1]; s = ""
    while 1 :
        choose = random.randrange(len(p))
        s = s + " " + p[choose][0]
        next = p[choose][1]
        if next == END : return s
        p = network[next]

The variable p keeps track of the current node and s is the sentence as it is being built. From each node we choose an arc at random (line 5), add its word to the sentence (line 6) and advance to the next node (line 9). The sentence is returned when the END node is reached (line 8).

Let's play with this a bit. You can access code and grammer at rtn.py and simple.py

>>> import rtn
>>> import simple
>>> rtn.gen1(simple.simple1)
' red book'
>>> rtn.gen1(simple.simple1)
' red book'
>>> rtn.gen1(simple.simple2)
' red red book'
>>> rtn.gen1(simple.simple2)
' red book'
>>> rtn.gen1(simple.simple2)
' red red red book'

The network simple1 always produces the same sentence, but simple2 generates a random number of red words preceding book.

Nested Networks

The following is going to assume a rudimentary knowledge of english grammer. You need to at least know the difference between nouns, prepositions, verbs and adjectives. There are lots places to get this information. Try google.

Extending our simple networks to recursive networks requires just one change. Allow the label on an arc to be either a word or another network. Here is an example of 3 simple networks article, noun1 and adjective along with a recursive network noun2. These 2nd order nouns are preceded by the word the or a followed by zero or more adjectives.

The recursive netword noun2 is defined in Python as you probably already suspect. The subnetworks must be defined earlier. For a full listing see english.py

noun2 = {TITLE: "Noun2",
         1: [(article, 2)],
         2: [(adjective, 2), (noun1, END)]
        }

A small modification in the generator function is needed to make it work recursively.

def gen2(item) :
    "Generate random sentence, allow recursive network"
    if type(item) == type("") : return item
    p = item[1]; s = ""
    while 1 :
        choose = random.randrange(len(p))
        s = s + " " + gen2(p[choose][0])
        next = p[choose][1]
        if next == END : return s
        p = item[next]

Now the item passed to the function may be either a word or a subnetwork. The third checks if the item is a string and, if so, simply returns it. Otherwise line 7 calls gen2 recursively to possibly expand a subnetwork. Let's generate some sentences. 

>>> import english
>>> import rtn
>>> rtn.gen2(english.noun2)
'  a  red  top'
>>> rtn.gen2(english.noun2)
'  a  big  book'
>>> rtn.gen2(english.noun2)
'  the  table'
>>> rtn.gen2(english.noun2)
'  the  small  red  table'
>>>

Now suppose that instead of generating a random sentence, we want to generate all possible sentences in a grammer. We must be careful to choose a grammer that is finite. We'll use a grammer whose sentences consist of a single adjective followed by a simple noun.

from english import *
simple3 = {TITLE: "Simple finite network",
           1: [(adjective, 2)],
           2: [(noun1, END)]
           }

But is there an easy way to generate all sentences in a grammer? This brings us to a new topic

Python generators

Generators are new to Python 2.2. You may think of them as functions that return multiple values one at a time to the caller, but maintaining their internal state (where they are and the value of local variables) between calls. They are very convenient when used with a for loop.

Here's a very simple example

>>> def gg() :
...     yield 2
...     yield 4
...     yield 8
...
>>> for i in gg() : print i
...
2
4
8
>>>

What turns a function definition into a generator is the use of the keyword yield. yield returns a value but keeps a bookmark of where it left off and values for local variables. The for loop will keep getting values from the generator until an explicit return in the generator is encountered or the generator falls off the end.

Generators are actually objects with a next method that is used by the for loop. They raise a specific exception when a return is excecuted, explicitly or implicitly.

Here is a generator that will generate all the sentences in the little recursive grammer above.

def gen3(item, Start=1) :
    "Use generator to yield all possible sentences"
    if        Start == END      : yield ""
    elif type(item) == type("") : yield item
    else :
        p = item[Start]; s = ""
        for arc in p :
            for word in gen3(arc[0]) :
                for rest in gen3(item,Start=arc[1]) :
                    yield word + " " + rest

This generator is doubly recursive and deserves a close study. When it is entered item may be network, a partial network (where Start is set), or terminal word (like red). Basically, from a given node, each arc is tried. For each word (terminal or subnetwork) the arc label produces, we check from the target node to see if the END can be reached and yield the sentence accordingly. It is tricky.

Let's try this out.

>>> import simple
>>> import rtn
>>> for sent in rtn.gen3(simple.simple3) : print sent
...
big  book
big  table
big  top
small  book
small  table
small  top
red  book
red  table
red  top
>>>

As an exercise, figure out why the words are separated by 2 spaces instead of 1.

Matching input sentences

Usually we want to do is see if a given sentence is valid in the grammer and, if so, what are its constituent parts and how are they related to one another. Sometimes there is more than one answer. For example, with the sentence, The book on the table that is red. You can't tell whether it is the table or the book that is red. Of course we humans will rely on context for resolving ambiguities. In the sentence, The man wearing the hat that is green, it is almost certain that it is the hat that is green since you almost never see martians wearing hats. But computer programs cannot be expected to know such things, at least not yet! So if our grammer allows ambiguity, the matching algorithm should find multiple interpretations.

Our approach will be to generate all sentences that match the input sentence. If we are unable to find at least one match the sentence is not valid for our grammer. Later, as the match is generated we will track the structures built in subnetworks and combine them into nested list structures. The nesting will show the relationship of the parts in the same way that a sentence diagram does.

We are going to extend our noun phrase grammer to include prepositional phrases. Like adjectives, these qualify (or zero in on) a noun. The book on the table with a blue cover has two prepositional phrases both of which distinguish this book from, perhaps, others nearby. However, notice the ambiguity. Is the book or the table covered?

Remember that a noun2 included an article (a,the) and zero or more adjectives. We'll call a noun3 any noun2 follwed by zero or more prepositional phrases.

preposition = {TITLE: "Preposition",
    1: [("on",END), ("of",END), ("in",END)]
    }

prepPhrase = {TITLE: "Prepositional Phrase",
    1: [(preposition, 2)],
    2: [(noun2, END)]
    }

noun3 = {TITLE: "Noun-3",
    1: [(noun2, END), (noun2, 2)],
    2: [(prepPhrase, END), (prepPhrase, 2)]
    }

Of course, this grammer is not really good english, since the noun inside a prepositional phrase itself may be qualified by a prepositional phrase. So noun2 in line 7 really should be noun3. This can be done only after noun3 itself has been defined with a statement like

prepPhrase[2][0] = (noun3, END)

This is ok, although we need to be carefule because the grammer is now circluar. If you were to print the dictionary prepPhrase, you would get a recursion overflow. But this will let our match functions discover the kind of ambiguities mentioned above.

The match generator

Our first match generator is very simliar to gen3 above.

def match1 (item, input, Start=1) :
    "Use generator to yield all possible matching sentences"
    if        Start == END      : yield input
    elif type(item) == type("") :
        if item == input[0] : yield input[1:]
    else :
        p = item[Start]; s = ""
        for arc in p :
            for input1 in match1 (arc[0], input) :
                for rest in match1 (item, input1, Start=arc[1]) :
                    yield rest

One difference is the parameter input which is the input sentence to be matched. Its format is a list of words. Secondly, rather than yielding (generating) sentences (or pieces of a sentence), match1 yields the rest of the input left unmatched. This means that subnetworks can chop off pieces of the input that they can use and pass back the remainder. Note that we are careful not to modify the input list itself. In line 5, yield input[1:] will create a new list each time. This allows concurrent partial matches to be active.

Let's play with this a bit.

>>> import english
>>> import rtn
>>> for s in rtn.match1(english.noun1, ['the','red','book']) : print s
...
>>> for s in rtn.match1(english.noun2, ['the','red','book']) : print s
...
[]
>>> for s in rtn.match1(english.noun2, ['the','red','book','bites']) : print s
...
['bites']

Matching a simple noun1 with noun2 input (line 3) generates no match because the article and adjective just get in the way. Matching the input to the noun2 network generates a single match comsuming all the input (line 6). The 3rd match leaves the verb bites after the match.

Retrieving the sentence structure

Our match generator generates values that reflect the input that remains to be matched. We would like to also generate a data structure showing the sentence structure of the input that has been matched.

We'll generate nested tuples, one tuple for each network. An example should make this fairly clear. The noun2 sentence the red book is represented by the set of nested tuples

('Noun2', ('Article', 'the'), ('Adjective', 'red'), ('Noun', 'book'))

The first element of each tuple contains the name of the network and the remaining elements the items that satisfied each arc on the path from node 1 to the END node. This is a format that makes it fairly easy to do semantic analysis. Here is a run for our second match generator.

>>> import rtn
>>> import english
>>> for s,t in rtn.match2(english.noun2,['the','red','book']) : print s,t
...
[] ('Noun2', ('Article', 'the'), ('Adjective', 'red'), ('Noun', 'book'))
>>>

And this is the python code:

def match2(item, input, Start=1, depth=0):
    "Use generator to yield all possible matching sentences"
    if depth > 10:
        return
    if Start == END:
        yield input, None
    elif not input:
        return
    elif type(item) == type(""):
        if item == input[0]:
            yield input[1:], item
    else:
        p = item[Start]; s = ""
        trace = [item[TITLE]]
        for arc in p:
            sav1 = trace[:]
            for input1,trace1 in match2(arc[0], input, depth=depth+1):
                if trace1:
                    trace.append(trace1)
                sav2 = trace[:]
                for rest, trace2 in match2(item, input1, Start=arc[1],
                                           depth=depth+1):
                    if trace2:
                        trace = trace + list(trace2[1:])
                    yield rest, tuple(trace[:])
                    trace = sav2[:]
                trace = sav1[:]

This is essentially match1 extended to generate trace tuples. At each level a different trace is started at line 9, grown at line 14 when the first arc is traversed and the rest of it gathered at line 17. The appends and additions are then backed off in lines 19 and 20 in order not to corrupt further possibilities. Incidentally, I spent a couple of hours getting this to work correctly.

Notice the variable depth. With a circularly recursive network it is possible for the code to get caught in an infinite loop. Aborting any search that exceeds some maximum level of nesting stops this. Except for artificially constructed sentences (involving a house that Jack built) this should not be a problem.

Here is a handy function to display the nested networks in an indented form that resembles sentence diagrams.

def display(trace, Indent="") :
     if type(trace) == type("") : print Indent, trace
     else :
         print Indent, trace[0]
         for item in trace[1:] : display(item, Indent=Indent+"  ")

>>> for s,t in rtn.match2(english.noun2,['the','red','book']) :
...     rtn.display(t)
...
Noun2
Article
the
Adjective
red
Noun
book
>>>

Finally, just to make life a little easier, we'll introduce a 3rd match function. It will generate solutions only where the complete input is matched and simply return the trace.

def match3(item, input):
    "Use generator to yield all matches that consume input"
    import string
    for input, trace in match2(item, string.split(input)):
        if not input:
            yield trace

Recursive networks

Let's now play with a sentence that is purposely ambiguous.

>>> sentence = "a book on the table with a cover"
>>> for t in rtn.match3(english.noun3,sentence) : rtn.display(t)
...
-------------------
Noun-3
Noun2
Article
a
Noun
book
Prepositional Phrase
Preposition
on
Noun2
Article
the
Noun
table
Prepositional Phrase
Preposition
with
Noun2
Article
a
Noun
cover

With our current grammer we don't allow the noun in a prepositional phrase to itself be modified by another prepositional phrase. So the only interpretaion possible is that the book is both covered and on the table.

Now let's change the network for prepPhrase so that the definition is circular. Running the same sentence we get

>>> english.prepPhrase[2] = [(english.noun3,english.END)]
>>> for t in rtn.match3(english.noun3,sentence) : rtn.display(t)
...
-------------------
Noun-3
Noun2
Article
a
Noun
book
Prepositional Phrase
Preposition
on
Noun-3
Noun2
Article
the
Noun
table
Prepositional Phrase
Preposition
with
Noun-3
Noun2
Article
a
Noun
cover
-------------------
Noun-3
Noun2
Article
a
Noun
book
Prepositional Phrase
Preposition
on
Noun-3
Noun2
Article
the
Noun
table
Prepositional Phrase
Preposition
with
Noun-3
Noun2
Article
a
Noun
cover
>>>

If you look carefully, you'll see that in the first interpretation it is the table that is covered and in the second, the book.

Parsing another language

Finally, let's contrast an english phrase with a japanese one and create a RTN grammer for japanese.

The phrase we will parse is in english the book on top of the table.

Now in japanese there are no articles (the, a, an). Prepositional phrases precede the noun and the preposition itself comes at the end. So the sentence looks like the following

taberu   no   ue   ni  hon
table    of   top  on  book

See japanese.py for the networks. Notice that the last line of the file updates the prepPhrase network for the circular definition.

>>> sentence = "taberu no ue ni hon"
>>> for t in rtn.match3(japanese.noun3,sentence) : rtn.display(t)
...
-------------------
Noun3
Prepositional Phrase
Noun3
Noun2
Noun1
taberu
Preposition
no
Prepositional Phrase
Noun3
Noun2
Noun1
ue
Preposition
ni
Noun2
Noun1
hon
-------------------
Noun3
Prepositional Phrase
Noun3
Prepositional Phrase
Noun3
Noun2
Noun1
taberu
Preposition
no
Noun2
Noun1
ue
Preposition
ni
Noun2
Noun1
hon
>>>

Again, two interpretations are possible although we humans would hardly think so. Beside the obvious one, the book on top of a table could be a book consisting of a table (of logrithms, maybe) on top of some other books. Of course, the computer is just finding the ambiguity in the structure itself.

But subtle ambiguities are absolutely rampant in natural languages which is one reason why natural language translation by computer programs is very difficult. A famous sentence time flies like an arrow leads to several interpretaions beside the one you are thinking of. For example, would you time flies and arrows with a stopwatch? Why would time flies prefer to hang out with (or is it eat?) arrows instead of whatever horse flies prefer? Or perhaps time flies in parabolic arcs just like arrows. You can have almost as much fun with the sentence fruit flies like a banana.

Pratical considerations

We just used a network for lexicons of nouns, adjectives, etc. but this would be impractical for anything other than the toy grammers shown here. Instead, matching noun to (say) table would be better done with a real Python dictionary where the key table might index a structure indicating a number of things about the word, including that it is a noun and its japanese translation is taberu. Of course, table can also be a verb in which case it would have a different japanese counterpart. Yet more ambiguity possibilities.

Index