Representing CFGs in Prolog I._________________________________________________________ As an example, we will use the following simple grammar: S ::= NP VP VP ::= V | V NP NP ::= some-terminal-strings V ::= some-terminal-strings One way to represent a CFG in Prolog is to have a predicate 'rule' which takes two arguments, for the LHS (left-hand-side) category/nonterminal and the sequence of categories appearing as the RHS (represented as a list). Here is how the rules of our grammer would appear in this representation: rule(s,[np,vp]). rule(vp,[v,np]). rule(vp,[v]). For lexical entries, we can for instance introduce assertions like: word(np,'Dr.Chan'). word(np,nurses). word(np, 'Medicenter'). word(v,died). ... Lexical analysis in Prolog would be extremely cumbersome, due to Prolog's poor I/O facilities. We will therefore ignore this aspect completely and consider only parsing with lists of lexical tokens as input/output (i.e., lists like ['MediCenter', employed, nurses], etc.) II.________________________________________________________ A grammar is a formal set of rules describing what it is to be a string in a particular language. Prolog, as a language based on logic, is eminently suitable for writing formal descriptions and definitions of various kinds. It is therefore natural to consider expressing a grammar directly as a logical specification in Prolog. In fact, it is extremely simple to translate our little grammar into Prolog clauses talking directly about strings of words and which ones are grammatical. As it happens, the resulting Prolog code can be used to recognize exactly the strings of words that the grammar claims to be grammatical and to generate example grammatical sentences. The translation of grammar rules into Prolog clauses just requires thinking carefully about what each rule is actually saying. Our S (sentence) rule below can be readily paraphrased as claiming that a list of words, Z, counts as a sentence if there is a list of words, X, that counts as a NP (noun phrase), and a list of words, Y, that counts as a VP (verb phrase), and that Z is merely Y appended to X. And this paraphrase can be more concisely expressed as a Prolog clause: s(Z) :- np(X), vp(Y), append(X,Y,Z). The rule for verb plus object VP is isomorphic: vp(Z) :- v(X), np(Y), append(X,Y,Z). And the intransitive case is trivial: vp(Z) :- v(Z). We need a lexicon, of course, and this can be provided as follows: np(['Dr.Chan']). np(['MediCenter']). np([nurses]). np([patients]). v([died]). v([employed]). And that is it -- we have a recognizer for a tiny fragment of English which can be invoked thus: ?- s([patients, died]). ?- s(['MediCenter', employed, nurses]). Thanks to its wholly declarative character, we can use this very same code to do generation as well as recognition. Try the following: ?- s(Sentence). III._______________________________________________________ Although elegant in comparison with the code one would need to perform the same task in a procedural language, this scheme for writing recognizers is less than ideal. Considerations of both efficiency and aesthetics suggest that we should eliminate the explicit 'append' statements if we can. The difference list technique allows us both to eliminate the offending 'append' statements and to make the Prolog code close to isomorphic to the rules of the grammar whose language is recognized, thus simultaneously addressing our efficiency and aesthetic concerns. We recode the recognizer as follows: ------------------------------------------ % A simple top-down recognizer % % illustrating also use of DIFFERENCE LISTS % to avoid explicit concatenation % % rules s(X,Z) :- np(X,Y), vp(Y,Z). vp(X,Z) :- v(X,Z). vp(X,Z) :- v(X,Y), np(Y,Z). % % lexicon % np(['Dr.Chan'|X],X). np(['MediCenter'|X],X). np([nurses|X],X). np([patients|X],X). v([died|X],X). v([employed|X],X). % % examples % test1 :- s([patients, died],[]). test2 :- s(['MediCenter', employed, nurses],[]). ----------------------------------------------- The first rule here can be paraphrased as saying that we can find an S at the start of X (with Z the portion of string left behind after it)) if we can find an NP at the beginning of X, leaving Y behind, and a VP at the beginning of Y, with Z left behind after that. As before, we can use this very same code to do generation as well as recognition. Try the following: ?- s(Sentence,[]). IV.________________________________________________________ It is straightforward to convert the recognizer into a parser, simply by the addition of extra arguments. Each predicate in the program, which captures the notion of a particular grammatical category, is provided with an extra argument (appearing as the first argument, say) which describes (as a list) the structure of the phrase. In the logic translation of each phrase-structure rule the tree corresponding to the LHS category will be simply a list consisting of the category name followed by the trees of the RHS categories. For example: ------------------------ % A simple top-down parser % % rules s([s,NP,VP],X,Z) :- np(NP,X,Y), vp(VP,Y,Z). vp([v,V],X,Z) :- v(V,X,Z). vp([v,V,NP],X,Z) :- v(V,X,Y), np(NP,Y,Z). % % lexicon % np([np,'Dr.Chan'],['Dr.Chan'|X],X). np([np,'MediCenter'],['MediCenter'|X],X). np([np,nurses],[nurses|X],X). np([np,patients],[patients|X],X). v([v,dies],[died|X],X). v([v,employed],[employed|X],X). % % examples % test1 :- s(Parse,[patients,died],[]), write(Parse), nl. test2 :- s(Parse,['MediCenter',employed,nurses],[]), write(Parse), nl. ----------------------- Translated into English (and forgetting about the arguments concerned with portions of the string), the first clause says that one form of a sentence is as a NP followed by a VP. If a sentence has this form, then its parse tree will be a list of the form "[s,NP,VP]", where NP is the parse tree of the noun phrase and VP is the parse tree of the verb phrase. V._________________________________________________________ The code for our difference list recognizer above bears such a close relationship to the corresponding grammar that one might reasonably expect to be able to get from the latter to the former automatically. We would like to be able to get a program to convert clauses written essentially as phrase structure rules into clauses that would implement difference list recognition. Thus our input to the program might be expressed thus: s --> np, vp. np --> [nurses]. (given an appropriate operator declaration for '-->'), where the annotated ("variabilised") difference list output should be something like: s(_1,_2) :- np(_1,_3), vp(_3,_2). np([nurses|_4],_4). Prolog comes actually with such an operator '-->' but it involves a few (minor) complications. The interested reader should try to define himself an appropariate 'translate' predicate to convert from the former to the latter form. Otherwise, one is referred to a detailed treatement of --> elsewhere.