The append's are expensive -- Prolog uses difference lists instead.
The rule
s(A,B) :- np(A,C), vp(C,B).
says that there is a sentence at the beginning of A (with B left over) if
there is a noun phrase at the beginning of A (with C left over), and
there is a verb phrase at the beginning of C (with B left over).
DCGs can build parse trees which can be used to
construct a semantic interpretation of the sentence.
The tree is built bottom-up, when Prolog returns from
recursive calls. We give each phrase structure rule an
extra argument which represents the node to be
constructed.
A grammar rule is written LHS -> RHS.
The left-hand side (LSH) must be a non-terminal
symbol, the right-hand side (RHS)
can be a combination of terminals, non-terminals, and
Prolog goals.
Terminal symbols (words) are in square brackets:
n -> [house].
More than one terminal can be matched by
one rule: np -> [the,house].
![\begin{gprogram}
s \xx --> np, vp.\\
vp \xx --> v, np.\\
vp \xx --> v.\\
np \...
...}\\
\x yes \\
\redtt{?- s([kissed, john, lisa], []).} \\
\x no
\end{gprogram}](img1.gif)
![\begin{gprogram}
\redtt{?- s(A, []).}\\
\x A = [john,died,john] ; \\
\x A = [j...
...use] ; \\
\x A = [lisa,kissed,house] ; \\
\x A = [lisa,died] ;
\end{gprogram}](img2.gif)
![\begin{gprogram}
s(Z) :- np(X), vp(Y), append(X,Y,Z). \\
np(Z) :- n(Z). \\
vp(...
...\\
\x S = [john,died,john] ;\\
\x S = [john,died,lisa] ; \ldots
\end{gprogram}](img3.gif)
![\begin{gprogram}
s(A,B) \xxx :- np(A,C), vp(C,B).\\
np(A,B) \xxx :- n(A,B).\\
...
...kissed\vert R], []).}\\
\x R = [john] ;\\
\x R = [lisa] ;\ldots
\end{gprogram}](img4.gif)
![\begin{gprogram}
s(s(NP,VP)) \xxxxx --> np(NP), vp(VP).\\
vp(vp(V, NP)) \xxxxx ...
...(n(died)) \xxxxx --> [died].\\
v(n(kissed)) \xxxxx --> [kissed].
\end{gprogram}](img5.gif)
![\begin{gprogram}
\redtt{?- s(S, [john, kissed, lisa], []).} \\
S=s(np(n(john)),...
... died, lisa], []).} \\
S=s(np(n(john)),vp(n(died),np(n(lisa))))
\end{gprogram}](img6.gif)
![\begin{gprogram}
\redtt{?- s(s(np(n(john)),vp(n(kissed),} \\
\xxx \redtt{np(n(lisa)))), S, []).} \\
\xx S=[john, kissed, lisa]
\end{gprogram}](img7.gif)
![\begin{gprogram}
s(s(NP,VP)) --> np(NP), vp(VP).\\
vp(vp(V, NP)) --> v(V), np(N...
...her)) --> [her].\\
\\
\redtt{?- s(S, [i, saw, her, duck], []).}
\end{gprogram}](img8.gif)
![\begin{gprogram}
\% Constant declarations \\
const\_decl --> [ ]. \\
const\_de...
...], \{atom(X)\}. \\
constant --> [X], \{(integer(X); float(X))\}.
\end{gprogram}](img10.gif)
![\begin{gprogram}
\% Type declarations \\
type\_decl --> [ ]. \\
type\_decl -->...
... type --> ['REAL']. \\
type --> ['BOOLEAN']. type --> ['CHAR'].
\end{gprogram}](img11.gif)
![\begin{gprogram}
\% Variable decleclarations \\
var\_decl --> [ ]. \\
var\_dec...
...st --> identifier. \\
id\_list --> identifier, [','], id\_list.
\end{gprogram}](img12.gif)
![\begin{gprogram}
\% Procedure declarations \\
proc\_decl --> [ ]. \\
proc\_dec...
...\_params --> var\_def. \\
variable\_params --> [var], var\_def.
\end{gprogram}](img13.gif)
![\begin{gprogram}
decl(decl(C, T, V, P)) --> \\
\x const\_decl(C), type\_decl(T)...
...D, Ds)) --> \\
\x [const], const\_def(D), [;], const\_defs(Ds).
\end{gprogram}](img14.gif)
![\begin{gprogram}
const\_defs(null) --> [ ]. \\
const\_defs(const(D, Ds)) --> \\...
...atom(X)\}. \\
const(num(X)) --> [X], \{(integer(X); float(X))\}.
\end{gprogram}](img15.gif)
![\begin{gprogram}
\redtt{?- decl(S, [const, a, =, 5, ;, x, =, 3.14, ;], []).} \\ ...
...(def(id(x),num(3.14)),\\
\xxxxxx null)),\\
\xxx null,null,null)
\end{gprogram}](img16.gif)
![\begin{gprogram}
\redtt{?- number(V, [sixty, three], []).} \\
\x V = 63 \\
\re...
...
\x V = 999 \\
\redtt{?- number(V, [fifty, ten], []).} \\
\x no
\end{gprogram}](img17.gif)
![\begin{gprogram}
number(0) --> [zero]. \\
number(N) --> xxx(N). \\
\\
xxx(N)...
...is T+N1\}. \\
\\
rest\_xx(0) --> [ ]. rest\_xx(N) --> digit(N).
\end{gprogram}](img18.gif)
![\begin{gprogram}
digit(1) --> [one]. \xxxxxxxx teen(10) --> [ten]. \\
digit(2) ...
...ty]. \\
tens(80) --> [eighty] .\xxxxxxxx tens(90) --> [ninety].
\end{gprogram}](img19.gif)
![\begin{gprogram}
\redtt{?- expr(X, ''234+345*456'', []).} \\
\x X = 157554 \\
...
... num(X), ''/'', term(Y), \{Z is X /Y \}. \\
term(Z) --> num(Z).
\end{gprogram}](img20.gif)
![\begin{gprogram}
num(C) --> ''+'', num(C). \\
num(C) --> ''-'', num(X), \{C is ...
...\
digit(X) --> [C], \{''0'' =< C, C =< ''9'',X is C-''0''\}. \\
\end{gprogram}](img21.gif)
![\begin{gprogram}
digit(1) --> [one]. .... \\
digit(9) --> [nine]. \\
teen(10) ...
...een]. \\
tens(20) --> [twenty]. .... \\
tens(90) --> [ninety].
\end{gprogram}](img22.gif)
![\begin{gprogram}
\redtt{?- time(T, [eight, am], []).} \\
\x T = 8:0 \% Or, better, 8:00 \\
\end{gprogram}](img23.gif){kind=small}
![\begin{gprogram}
\redtt{?- time(T, [eight, thirty, am], []).} \\
\x T = 8:30 \\...
...
\redtt{?- time(T,[twelve,thirty,am],[]).} \\
\x T = 0:30 \% !!!
\end{gprogram}](img24.gif)
![\begin{gprogram}
\redtt{?- time(T,[eleven,thirty,pm],[]).} \\
\x T = 23:30 \\
...
...\
\redtt{?- time(T,[half,past,four,pm],[]).} \\
\x T = 16:30\\
\end{gprogram}](img25.gif)