% -*- Mode:Prolog -*- % working_directory(_,'/Users/robin/ucalgary/class/449/prolog/'). /* The purpose of these notes is to give a very brief introduction to definite clause grammars as supported in most prolog systems. These have been used quite successfully to develop natural langage processing applications. A typical application is to parse English language sentences. Here is a very simple example to give the idea: */ sentence --> pronoun(subject), verb_phrase. sentence --> proper_noun(subject),verb_phrase. verb_phrase --> verb, pronoun(object). verb_phrase --> verb, noun_phrase(object). noun_phrase(object) --> adjective,noun(object). noun_phrase(object) --> noun(object). proper_noun(subject) --> [mary]. proper_noun(subject) --> [john]. noun(object) --> [cats]. noun(object) --> [dogs]. adjective --> [black]. adjective --> [tan]. pronoun(subject) --> [he]. pronoun(subject) --> [she]. pronoun(object) --> [him]. pronoun(object) --> [her]. verb --> [likes]. verb --> [hates]. verb --> [does,not,mind]. /* One can then use these predicated to parse (simple) sentences: sentence([he,likes,her],[]). sentence([john,likes,black,dogs],[]). But also, importantly, the same program can be used to generate sentences: sentence(Z,[]). Z = [he, likes, him] ; Z = [he, likes, her] ; Z = [he, hates, him] ; etc. Definite clause grammars are translate to basic prolog by: h --> [atom] := h([atom|Z],Z). h --> b1, b2, b3 := h(Z,R) :- b1(Z,R1),b2(R1,R2),b3(R2,R) Pedicates enclosed in curly brackets are not translated ... (this explains why one call "sentence" with two arguments). The idea is that each predicate in the list will "eat" a prefix and passes on the remaining suffix to the next predicate ... in addition one can embedd predicates which must be satified in to grammars using curly braces "{ ...}". Definite clause grammars are powerful. For example the non-context free grammar a^n b^n c^n can be expressed as a definite clause grammar: */ s --> a(N), b(N), c(N). a(0) --> []. a(M) --> [a], a(N), {M is N + 1}. b(0) --> []. b(M) --> [b], b(N), {M is N + 1}. c(0) --> []. c(M) --> [c], c(N), {M is N + 1}. /* The definite clause syntax can be used to accomplish tasks which are not immedately grammare related. For example consider the problem of collecting the leaves of a tree into a list: */ collect(X) --> [X], {atom(X)}. collect(node(X,Y)) --> collect(X),collect(Y). /* Try collect(node(x,node(y,z)),Z,[]). dc-grammars are not magic! For example to parse/generate successfully they cannot be left recursive ... Consider the problem of evaluating expressions with addition and subtraction. We would like to write: expr(Z) --> num(Z). expr(Z) --> expr(X), "+", num(Y), {Z is X+Y}. expr(Z) --> expr(X), "-", num(Y), {Z is X-Y}. where: */ num(Z) --> num(Z, 0). num(Z, Accum) --> digit(D1), {Z is 10*Accum+D1}. num(Z, Accum) --> digit(D1), {A2 is 10*Accum+D1}, num(Z, A2). digit(Z) --> [D], {`0` =< D, D =< `9`, Z is D - `0`}. /* Note the use of backquotes which is special to SWI-prolog! But expr is left recursive and so will never terminate -- as it immediately calls itself -- so one must transform the grammar to remove the left recursion (this is a standard technique): */ expr(Z) --> num(X), rest_expr(X, Z). rest_expr(Accum, Z) --> {Z is Accum}. rest_expr(Accum, Z) --> `+`, num(Y), {W is Accum+Y}, rest_expr(W, Z). rest_expr(Accum, Z) --> `-`, num(Y), {W is Accum-Y}, rest_expr(W, Z). /* Try this out with expr(Z,`32-7+13`,[]). */