CFG in Prolog
The standard way to write CFG in Prolog is by means of Definite Clause Grammars. They are a nice user friendly notation for grammars written in terms of difference lists. The used strategy is as below. For each syntactic category "C", define a predicate "c(InList,OutList)" which takes a list of words (InList) as input, "bites off" a sequence of words corresponding to an expression of category "C" and returns the rest (OutList). For instance,?- np([the,nurse,whistles],Out).
Out = [whistles]
?- np([the,whiskey],Out).
Out = []
Strategy for assigning categories to words: If the head of the input list is the word bride, then we have found a noun. Return the tail of the list. Examples:
n([bride|Out],Out).
n([nurse|Out],Out).
n([sword|Out],Out).
det([the|Out],Out).
pn([bill|Out],Out).
vt([kills|Out],Out).
Another notation for lexical entries is the following one, exemplified with the determiner "the".
det(A,B) :- 'C'(A,the,B).
the idea is the same as above. Basically, it says you can get a B from an A by consuming a the. Note that 'C' is an atom.
Examples of definition of complex categories:
np(In,Out) :- det(In,DetOut), n(DetOut,Out).
If we can bite a determiner off the list and then bite a noun of the list, then we have found an NP. Return what's left when biting off the determiner and the noun.
np(In,Out) :- pn(In,Out).
If we can bite a proper name off the list, then we have found an NP. Return what's left when biting off the proper name. Therefore, you have to keep this in mind when asking a query. For instance, to ask whether [the,nurse,whistles] is a sentence, you have to write:
?- s([the,nurse,whistles],[]).