Grammars in Prolog

Next we turn to more complex examples of Prolog programming. Prolog was originally invented as a programming language in which to write natural language applications, and thus Prolog is a very elegant language for expressing grammars. Prolog even has a builtin syntax especially created for writing grammars. It is often said that with Prolog one gets a builtin parser for free. In this section we will see why this claim is made (and sometimes contested).

Consider the following simple context-free grammar for a small fragment of English.

$S~ \longrightarrow ~NP ~VP$
$NP~ \longrightarrow ~Det~ N$
$VP~ \longrightarrow ~TV~ NP$
$VP~ \longrightarrow ~V$
$Det~ \longrightarrow ~the$
$Det~ \longrightarrow ~a$
$Det~ \longrightarrow ~every$
$N~ \longrightarrow ~man$
$N~ \longrightarrow ~woman$
$N~ \longrightarrow ~park$
$TV~ \longrightarrow ~loves$
$TV~ \longrightarrow ~likes$
$V~ \longrightarrow ~walks$

In this grammar we can derive such simple sentences as:

a man loves the woman
every woman walks
a woman likes the park

We can write a simple Prolog program to recognize this language, by writing a recursive descent parser. We first must decide how to handle the input string. We will use a list in Prolog. For each nonterminal we will construct a Prolog procedure to recognize strings generated by that nonterminal. Each procedure will have two arguments. The first will be an input parameter consisting of the list representing the input string. The second will be an output argument, and will be set by the procedure to the remainder of the input string after an initial segment matched by the nonterminal has been removed. An example will help clarify how this works. The procedure for np would, for example, take as its first argument a list [a,woman,loves,a,man] and would return in its second argument the list [loves,a,man]. The segment removed by the procedure, [a,woman], is an NP. The Prolog program is:

    s(S0,S) :- np(S0,S1), vp(S1,S).
    np(S0,S) :- det(S0,S1), n(S1,S).
    vp(S0,S) :- tv(S0,S1), np(S1,S).
    vp(S0,S) :- v(S0,S).
    det(S0,S) :- S0=[the|S].
    det(S0,S) :- S0=[a|S].
    det(S0,S) :- S0=[every|S].
    n(S0,S) :- S0=[man|S].
    n(S0,S) :- S0=[woman|S].
    n(S0,S) :- S0=[park|S].
    tv(S0,S) :- S0=[loves|S].
    tv(S0,S) :- S0=[likes|S].
    v(S0,S) :- S0=[walks|S].

The first clause defines procedure s, for recognizing sentences. An input list S0 is passed into procedure s, and it must set S to be the remainder of the list S after a sentence has been removed from the beginning. To do that, it uses two subprocedures: it first calls np to remove an NP, and then it calls vp to remove a VP from that. Since the grammar says that an S is an NP followed by a VP, this will do the right thing. The other rules are exactly analogous.

Having put this program in a file called grammar.P, we can load and execute it on our example sentences as follows:

% xsb
XSB Version 1.4.1 (94/11/21)
[sequential, single word, optimal mode]
| ?- [grammar].
[Compiling ./grammar]
[grammar compiled, cpu time used: 1.14 seconds]
[grammar loaded]

yes
| ?- s([a,man,loves,the,woman],[]).

yes
| ?- s([every,woman,walks],[]).

yes
| ?- s([a,woman,likes,the,park],[]).

yes
| ?- s([a,woman,likes,the,prak],[]).

no
| ?-

When the string is in the language of the grammar, the program will execute successfully through to the end, and the system produces `yes'. If the string is not in the language, as in the final example where `park' was misspelled, the system answers `no'. We called the s procedure with the input string as first argument and we gave it the empty list as second argument, because we want it to match the entire input string, wiht nothing left over after seeing an s.

The grammar above is called a Definite Clause Grammar (DCG) and Prolog supports a special rule syntax for writing DCGs. The syntax is simpler, much closer to the syntax one uses in writing context-free grammar rules. When using the DCG syntax, the programmer doesn't have to write all the string variables threaded through the nonterminal procedure calls; the compiler will do it. Here following is the same Prolog program as above, but witten as a DCG:

    s --> np, vp.
    np --> det, n.
    vp --> tv, np.
    vp --> v.
    det --> [the].
    det --> [a].
    det --> [every].
    n --> [man].
    n --> [woman].
    n --> [park].
    tv --> [loves].
    tv --> [likes].
    v --> [walks].

Notice that these ``procedure definitions'' use the symbol --> instead of :- to separate the procedure head from the procedure body. The Prolog compiler converts such rules to (almost) exactly the program above, by adding the extra arguments to the predicate symbols and treating the lists as terminals. The ``almost'' is because it really translates, for example, a single word list [loves] above to the procedure call 'C'(S0,loves,S), and includes the definition of this new predicate as:

    'C'([Word|String],Word,String).

This gives exactly the same effect as the Prolog program for the grammar given above.

Consider another example grammar, this one for simple arithmetic expressions over integers with operators + and *:

expr --> term, addterm.
addterm --> [].
addterm --> [+], expr.
term --> factor, multfactor.
multfactor --> [].
multfactor --> [*], term.
factor --> [I], {integer(I)}.
factor --> ['('], expr, [')'].

There are several things to note about this DCG. Notice that the list entries, representing terminals, need not appear alone on right-hand-sides of DCG rules, but may accompany nonterminals. Also notice the first rule for factor; it has a variable (I) in a list, which will cause it to be matched with, and thus set to, the next input symbol. The following procedure call is enclosed in braces. This means that it matches no input symbols and so its translation to Prolog does NOT result in the string variables being added. It remains just a call to the Prolog procedure with one argument: integer(I). The integer procedure is a Prolog builtin which tests whether its argument is an integer. Note also that we must quote the parentheses in the final rule. Otherwise, Prolog's reader would not be able to parse them correctly as atoms.

Consider some example executions of this grammar:

% xsb
XSB Version 1.4.1 (94/11/21)
[sequential, single word, optimal mode]
| ?- [grammar].
[Compiling ./grammar]
[grammar compiled, cpu time used: 1.309 seconds]
[grammar loaded]

yes
| ?- expr([4,*,5,+,1],[]).

yes
| ?- expr([1,+,3,*,'(',2,+,4,')'],[]).

yes
| ?- expr([4,5,*],[]).

no
| ?-

This grammar is not the most obvious one to write down for this expression language. It is specially constructed to avoid being left recursive. We mentioned above that we were writing a recursive descent parser for the grammar, and that is what one gets for a DCG from Prolog's execution strategy. Prolog execution of the underlying deterministic machines and its use of a stack to schedule them naturally yields a recursive descent parser. And it is well known that a recursive descent parser cannot handle left-recursive grammars; it will go into an infinite loop on them. So in Prolog we must avoid left-recursive grammars.

Also a recursive descent parser can be quite inefficient on some grammars, because it may re-parse the same substring many times. In fact, there are grammars for which recursive descent parsers take time exponential in the length of the input string. When using DCGs in Prolog, the programmer must be aware of these limitations and program around them. It is for this reason that some people respond to the claim that ``You get a parser for free with Prolog'' with ``Maybe, but it's not a parser I want to use.''

(Another example for adding arguments and using word/3 instead of strings?).