[Previous] [Up] [Next]
Go backward to Context Free Grammars
Go up to Context Free Grammars And How To Implement Them In Prolog
Go forward to Exercises

Implementing CFGs in Prolog

The Prolog implementation of CFGs relies on rules which basically correspond directly to the production rules discussed above. The only addition is that the rule has to encode which part of the sentence the corresponding constituent concerns.

The first issue, thus, is how to represent sentences. As has already been pointed out numerous times, the easiest way to represent strings of arbitrary length is to use the list format. So a sentence such as John loves Mary will be represented as the Prolog list [john,loves,mary] (we have to use lower case letters, otherwise the interpreter will treat the word as a variable).

Say that we want to write the Prolog equivalent of the following production rules:

s -> np, vp
np -> noun
vp -> verb, np

n -> "John"
n -> "Mary"
v -> "loves" v -> "hates"
Given that we use the list format, the representation of a terminal in Prolog will be a list containing a single word, while a phrase or a sentence will be a list of words. So while the first production rule s -> np, vp can be understood as
if we can find an np and a vp, then we have an s
its Prolog implementation means that
if we have a list of words which we can prove to be an np and a list of words which we can prove to be vp, then if the two are concatenated, the result is an s.
The main idea behind computational syntax is that we treat the grammaticality of a sentence as something that can be proven with a grammar. The grammar is effectively a set of constraints on lists: the rule below makes a statement about a way of proving that a list is a sentence.
s(S):-
     np(NP),
     vp(VP),
     conc(NP,VP,S).
All of NP, VP and S are lists of words. The rule says that the list S is a sentence if So [john,loves,mary] is a sentence if [john] can be shown to be an NP and [loves,mary] can be shown to be a VP--or [john,loves] to be an NP and [mary] to be a VP for that matter--Prolog does not have any opinions on this--and we concatenate the pair to form [john,loves,mary].

The following Prolog rules implement the np and vp rules above:

vp(VP):-
     verb(V),
     np(NP),
     conc(V,NP,VP).
 
np(NP):-
     noun(NP).
and finally, we need a set of facts corresponding to the lexical rules:
noun([john]).
noun([mary]).
verb([loves]).
verb([hates]).
If this grammar is loaded into the interpreter, it is now possible to parse John loves Mary. An indented trace of the query is shown below.
| ?- s([john,loves,mary]).
   1  1  Call: s([john,loves,mary]) ? 
      2  2  Call: np(_353) ? 
         3  3  Call: noun(_353) ? 
         3  3  Exit: noun([john]) ? 
      2  2  Exit: np([john]) ? 
      4  2  Call: vp(_348) ? 
         5  3  Call: verb(_1332) ? 
         5  3  Exit: verb([loves]) ? 
         6  3  Call: np(_1327) ? 
            7  4  Call: noun(_1327) ? 
            7  4  Exit: noun([john]) ? 
         6  3  Exit: np([john]) ? 
         8  3  Call: conc([loves],[john],_348) ? 
            9  4  Call: conc([],[john],_2690) ? 
            9  4  Exit: conc([],[john],[john]) ? 
         8  3  Exit: conc([loves],[john],[loves,john]) ? 
      4  2  Exit: vp([loves,john]) ? 
     10  2  Call: conc([john],[loves,john],[john,loves,mary]) ? 
        11  3  Call: conc([],[loves,john],[loves,mary]) ? 
        11  3  Fail: conc([],[loves,john],[loves,mary]) ? 
     10  2  Fail: conc([john],[loves,john],[john,loves,mary]) ? 
      4  2  Redo: vp([loves,john]) ? 
         8  3  Redo: conc([loves],[john],[loves,john]) ? 
            9  4  Redo: conc([],[john],[john]) ? 
            9  4  Fail: conc([],[john],_2690) ? 
         8  3  Fail: conc([loves],[john],_348) ? 
         6  3  Redo: np([john]) ? 
            7  4  Redo: noun([john]) ? 
            7  4  Exit: noun([mary]) ? 
         6  3  Exit: np([mary]) ? 
         8  3  Call: conc([loves],[mary],_348) ? 
            9  4  Call: conc([],[mary],_2690) ? 
            9  4  Exit: conc([],[mary],[mary]) ? 
         8  3  Exit: conc([loves],[mary],[loves,mary]) ? 
      4  2  Exit: vp([loves,mary]) ? 
     10  2  Call: conc([john],[loves,mary],[john,loves,mary]) ? 
        11  3  Call: conc([],[loves,mary],[loves,mary]) ? 
        11  3  Exit: conc([],[loves,mary],[loves,mary]) ? 
     10  2  Exit: conc([john],[loves,mary],[john,loves,mary]) ? 
   1  1  Exit: s([john,loves,mary]) ? 
yes
{trace}

<a.von.klopp@bangor.ac.uk>

[Previous] [Up] [Next]