2.1.1 Finite State Parsers

Finite state parsers are introduced.

So, in the case of a finite state parser the output should tell us which transitions had to be made in the underlying FSA when the input was recognized. That is, the output should be a sequence of nodes and arcs. For example, if we give the input [h,a,h,a,!] to a parser for our first laughing automaton (a1), it should return [1,h,2,a,3,h,2,a,3,!,4].

There is a fairly standard technique in Prolog for turning a recognizer into a parser: add one or more extra arguments to keep track of the structure that was found. We will now use this technique to turn recognize/3 of the last chapter into parse/4, i.e. an FSA-based parser.

In the base clause, when the input is read and the FSA is in a final state, all we have to do is record that final state. So, we turn

recognize(A,Node,[]) :-
    final(A,Node).

into

parse(A,Node,[],[Node]) :-
    final(A,Node).

Then let's look at the recursive clause. The recursive clause of recognize/3 looked as follows:

recognize(A,Node_1,String) :-
    trans(A,Node_1,Node_2,Label),
    traverse(Label,String,NewString),
    recognize(A,Node_2,NewString).

And here is the recursive clause of parse/4:

parse(A,Node_1,String,[Node_1,Label|Path]) :-
    trans(A,Node_1,Node_2,Label),
    traverse(Label,String,NewString),
    parse(A,Node_2,NewString,Path).

The parser records the state the FSA is in and the symbol it is reading on the transition it is taking from this state. The rest of the path, i.e. the sequence of states and arcs that the FSA will take from Node2 onwards, will be specified in the recursive call of parse/4 and collected in the variable Path.

The only thing that's left to do is to adapt the driver predicates testparse/2 and generate/2. The new driver predicates look as follows:

testparse(A,Symbols,Parse) :-
    start(A,Node),
    parse(A,Node,Symbols,Parse).

generate(A,Symbols,Parse) :-
   testparse(A,Symbols,Parse).

You can find the new predicates in parse.pl .