2.1.2 An Example

An example of how the output is being built in the extra argument during recognition.

Now, let's step through an example to have a look at how the output is being built in the extra argument during recognition. Assume that we have loaded the Prolog representation of a1 (our first laughing automaton) into the Prolog database. So the database contains the following facts:

start(a1,1).

final(a1,4).

trans(a1,1,2,h).

trans(a1,2,3,a).

trans(a1,3,4,!).

trans(a1,3,2,h).

parse.pl

We ask Prolog the following query:

testparse(a1,[h,a,!],Parse).

Prolog retrieves 1 as the only initial node in the FSA a1 and calls parse instantiated as

parse(a1,1,[h,a,!],Parse).

Next, Prolog has to retrieve arcs starting in node 1 from the database. It finds trans(a1,1,2,h), which it can use because the first symbol in the input is h as well. So, Parse is unified with [1,h|G67] where G67 is some Prolog internal variable. Prolog then makes a recursive call (the first recursive call) of parse with

parse(a1,2,[a,!],G67).

Now, Prolog finds trans(a1,2,3,a) in the database. So, G67 gets unified with [2,a|G68] (G68 again being some internal variable) and Prolog makes the second recursive call of parse:

parse(a1,3,[!],G68).

Using trans(3,4,!), the last symbol of the input can be read and G68 gets instantiated to [3,!|G69]. The next recursive call of parse (parse(a1,4,[],G69) ) matches the base clause. Here, G69 gets instantiated to [4], instantiating G68 to [3,!,4], G67 to [2,a,3,!,4], and Parse to [1,h,2,a,3,!,4] as Prolog comes back out of the recursion. If you have trouble understanding how the output gets assembled, draw a search tree for the query parse(a1,1,[h,a,!],Parse). Note, how with every recursive call of parse the third argument gets instantiated with a list. The first two elements of this list are the state the FSA is currently in and the next symbol it reads; the rest of the list is an uninstantiated variable at first, but gets further instantiated by the next recursive call of parse.