CS计算机代考程序代写 prolog database Declarative Programming

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)