Declarative Programming
More on Definite Clause Grammars
Geraint A. Wiggins
Professor of Computational Creativity
Department of Computer Science
Vrije Universiteit Brussel
How –> expansion works
I Recall from the last lecture that consulting a file
containing a definition like
command –> startcommand.
gave us a two-place predicate command/2
I When Prolog reads a clause defined with the –>
operator, it expands that clause before it is added to the
database, to give, e.g.,
command(A,B) :- startcommand(A,B).
I Here, A is a list of items to be parsed; B is a list of what
is left over afterwards
How –> expansion works (2)
I In general, the rule
a –> b, c.
expands to
a( X, Z ) :- b( X, Y ),
c( Y, Z ).
I We use the variable pair as a difference list, to avoid
having to append/3 things together
I We cannot use these variables directly in a program –
they are added in by Prolog and we do not know what
their names are
How –> expansion works (3)
I Raw Prolog code, in {}, is simply inserted verbatim, so
consulting
a –> b, {test(X)}, c.
gives us a database containing
a(U,W) :- b(U,V),
test(X),
c(V,W).
How –> expansion works (4)
I Items in [] are processed using the built-in ’C’ predicate:
’C’( [Term|List], Term, List ).
I So a DCG rule including a constant, eg
np –> [the], n.
expands like this:
np(X,Z) :- ’C’(X,the,Y),
n(Y,Z).
How –> expansion works (5)
I Recall the example command language:
command –> startcommand.
command –> stopcommand.
command –> savecommand.
startcommand –> [start,1,player].
startcommand –> [start],number gt 1,
[players].
stopcommand –> [stop].
savecommand –> [save],saveablething.
saveablething –> [game].
saveablething –> [player],number.
number –> [X], {integer(X), X>0}.
number gt 1 –> [X], {integer(X), X>1}.
How –> expansion works (6)
I This comes out as a parser program:
command(Y,Z) :- startcommand(Y,Z).
command(Y,Z) :- stopcommand(Y,Z).
command(Y,Z) :- savecommand(Y,Z).
startcommand(W,Z) :- ’C’( W, start, X ),
’C’( X, 1, Y ),
’C’( Y, player, Z ).
startcommand(W,Z) :- ’C’( W, start, X ),
number gt 1(X,Y),
’C’( Y, player, Z ).
stopcommand(Y,Z) :- ’C’( Y, stop, Z ).
savecommand(X,Z) :- ’C’( X, save, Y ),
saveablething(Y,Z).
How –> expansion works (7)
saveablething(Y,Z) :- ’C’( Y, game, Z ).
saveablething(X,Z) :- ’C’( X, player, Y ),
number(Y,Z).
number(Y,Z) :- ’C’( Y, X, Z ),
integer(X),
X>0.
number gt 1(Y,Z) :- ’C’( Y, X, Z ),
integer(X),
X>1.
I N.B. NLP people: there are two common Prolog grammar
operators: –> and —>. They are NOT the same.
I N.B. everyone: there are two arrow operators used in this
course: -> and –>. They are NOT the same.
Running a parser
I To run our parser, we call the predicate generated by the
top-most grammar rule (command/2 here) eg
?- command([start,2,players],[]).
I This means:
I “Parse a command from the front of the string in the
first argument,. . .
I with no string left over ([] in the second argument)”
Running a parser (2)
I Here’s a trace:
?- command( [start,2,players], [] ).
Call: command( [start,2,players], [] ).
Call: startcommand( [start,2,players], [] ).
Call: ’C’( [start,2,players], start, Y ).
Succeed: ’C’([start,2,players],start,[2,players]).
Call: number gt 1( [2,players], Y ).
Call: ’C’( [2,players], X, Z ).
Succeed: ’C’( [2,players], 2, [players] ).
Call: integer( 2 ).
Succeed: integer( 2 ).
Call: 2>1.
Succeed: 2>1.
Call: ’C’( [players], players, [] ).
Succeed: ’C’( [players], players, [] ).
Running a parser (3)
I Recall that the final [] comes from the initial query via
the clauses
command(Y,Z) :- startcommand(Y,Z).
startcommand(W,Z) :- ’C’( W, start, X ),
number gt 1(X,Y),
’C’( Y, players, Z ).
?- command([start,2,players],[]).
Adding arguments to DCGs
I So far, all our DCG can do is
I check acceptability
I generate acceptable examples (maybe)
I For more useful things, we can add arguments. . .
. . . so that other information can be processed alongside
the grammar input
I Examples of this are:
I adding arguments to subcategorize
I producing a syntax tree for study of grammar;
I translating into another language;
I translating into some semantic formalism.
Adding arguments to DCGs (2)
I When we add arguments to DCG rules, they are
automatically added to the expanded predicates, eg
compare
a –> b,
c.
a(X,Z) :- b(X,Y),
c(Y,Z).
a(B) –> b(B),
c(C).
a(B,X,Z) :- b(B,X,Y),
c(C,Y,Z).
Adding arguments to DCGs (2)
I A very common pattern is a rule like this:
thing(Val) –> subthing1(SubV1),
subthing2(SubV2),
{process(SubV1,SubV2,Val)}.
I Here, each sub-string returns a value, which is then
processed by a direct call to Prolog to return a combined
answer
Translating between languages
I Suppose that our hypothetical game software included
the commands
go(N) – to start a game with N players
halt – to stop a game
store(N) – where N is a player number, or 0 for the
whole game
I We could use an extra argument to the command DCG to
translate the input command to the appropriate internal
one
Translating between languages (2)
I This DCG will do the job:
command(ICom) –> startcommand(ICom).
command(ICom) –> stopcommand(ICom).
command(ICom) –> savecommand(ICom).
startcommand(go(1)) –> [start,1,player].
startcommand(go(N)) –> [start],number gt 1(N),
[players].
stopcommand(halt) –> [stop].
savecommand(store(N)) –> [save],saveablething(N).
saveablething(0) –> [game].
saveablething(N) –> [player],number(N).
number(X) –> [X], {integer(X), X>0}.
number gt 1(X) –> [X], {integer(X), X>1}.
Translating between languages (2)
I Now we can make calls like the following:
?- command( C, [start,2,players], [] ),
execute( C ).
where execute/1 is the command that runs the game
I This will yield the value go(2) for C and then execute
that command.
I For another example:
?- command( C, [save,game], [] ),
execute( C ).
will execute the command store(0)