Definite Clause Grammars (DCGs)

Definite Clause Grammars (DCGs) are convenient ways to represent grammatical relationships for various parsing applications. They can be used for natural language work, for creating formal command and programming languages.

For example, DCG is an excellent tool for parsing and creating tagged input and output streams, such as HTML or XML. The index and table of contents in this documentation are generated by a Prolog program that uses DCG to parse the HTML, looking for headings and index entries.

See Adventure in Prolog or Programming in Prolog by Clocksin and Mellish for tutorial information on DCGs and the difference lists used to implement them.

Parsing with Difference Lists
Generating with Difference Lists
DCG Syntax
Applications of DCG and Difference Lists

Language Translation
Bill of Materials
Command Language
XML

DCG Terminals
Parsing Files

Parsing with Difference Lists

Parsing is analyzing an input stream. Difference lists are powerful tools for parsing applications, in which the input stream is represented by difference lists.

Difference lists are pairs of lists used to represent the list of elements (tokens, words, character codes, ...) being parsed. The actual list being represented is the 'difference' between the first list and the second list. For example, [the, cat] might be represented by the two lists [the, cat, chases, the, mouse] and [chases, the, mouse]. Or more generally, [the, cat | X] and X.

In parsing applications, the first list contains the elements to be parsed. Different parsing predicates find what they are looking for at the front of that first list, and unify the second list with what's left to parse.

In the example sentence above, a predicate looking for a subject ('the cat') at the beginning of a sentence, would find it and return the rest of the sentence ('chases the mouse'). That could then be fed into another predicate that looks for a verb, finds it and returns what's left. This continues until there is nothing left.

In other words, the difference lists are chained together in the parsing application.

The full sentence would be represented by the full list and an empty list. That is, the difference is the full first list. So the difference lists for our test sentence are [the, cat, chases, the, mouse] and [].

A natural language parsing application tests to see if a sentence is grammatically correct. It does this using difference lists to chain together various grammatical catagories. Here is a simple example:

sentence(L1, L4) :-
  subject(L1, L2),
  verb(L2, L3),
  object(L3, L4).

Each of the subgoals, also links its difference lists together. For example:

subject(L1, L3) :-
  modifier(L1, L2),
  noun(L2, L3).

object(L1, L3) :-
  modifier(L1, L2),
  noun(L2, L3).

And the 'terminal' case is when there are one or more specfic elements to be identified at the head of the first list. For example, 'terminals' for the simple natural language parser would be the words in the allowed vocabulary:

modifier([the|X], X).
noun([cat|X], X).
noun([mouse|X], X).
noun([polar,bear|X], X).
verb([chases|X], X).
verb([eats|X], X).

In each case, the word is picked off the front of the first list, and the tail unified with the second list.

Experimenting with the above predicates:

?- noun([mouse, eats, cheese], X).
X = [eats, cheese] 
yes

?- noun([polar, bear, chases, cat], X).
X = [chases, cat] 
yes

?- noun([chases, the, mouse], X).
no

?- subject([the, mouse, chases, the, cat], X).
X = [chases, the, cat] 
yes

?- verb([chases, the, cat], X).
X = [the, cat] 
yes

?- object([the, cat], X).
X = '[]' 
yes

?- sentence([the, mouse, chases, the, polar, bear], []).
yes

?- sentence([chases, mouse, the, cat], []).
no

Generating with Difference Lists

In the previous section, we used the grammar rules written with difference lists to test if a sentence is a grammatically correct sentence.

Difference lists can also be used to generate grammatically correct sentences from the given vocabulary. In this case, the first list doesn't have the list to be parsed, but instead has a variable, which will be unified with the generated list.

This behavior can be seen by experimenting with the test grammar above.

For example:

?- noun(X, []).
X = [cat] ;
X = [mouse] ;
X = [polar, bear] ;
no

?- noun(X, Y).
X = [cat | H2]
Y = H2 ;

X = [mouse | H2]
Y = H2 ;

X = [polar, bear | H2]
Y = H2 ;
no

?- subject(X, Y).
X = [the, cat | H2]
Y = H2 ;

X = [the, mouse | H2]
Y = H2 ;

X = [the, polar, bear | H2]
Y = H2 ;
no

?- sentence(X, []).
X = [the, cat, chases, the, cat] ;
X = [the, cat, chases, the, mouse] ;
X = [the, cat, chases, the, polar, bear] ;
X = [the, cat, eats, the, cat] 
...

?- subject(A,B), verb(B,C), object(C,[]).
A = [the, cat, chases, the, cat]
B = [chases, the, cat]
C = [the, cat]

DCG Syntax

Definite Clause Grammar (DCG) is a Prolog preprocessor that takes DCG grammar rules, and adds linked difference lists to the goals.

DCG provides a syntax for writing more readable grammar parsing rules, without including the linked difference lists. The DCG preprocessor takes the DCG rule and translates it into pure Prolog, adding the linked difference lists.

The syntax of DCG is:

--> operator indicates a DCG rule, replacing the normal neck ( :- ) used for Prolog clauses. The preprocessor adds extra arguments for the difference lists. For example, the sentence grammar rule can be written without difference lists using a DCG rule:
```
sentence --> subject, verb, object. 
```
Each goal is assumed to refer to the head of a DCG rule, and the preprocessor adds two extra arguments for the difference list.
Curly braces {} are used to isolate normal Prolog goals from the DCG preprocessor. For example:
```
subject --> modifier, noun, {write('found subject')}.
```
Square brackets [], list notation, are used to indicate terminal symbols of the grammar. For example:
```
noun --> [cat]
```

Using DCG notation, the sentence parsing rules of the previous section can be written:

sentence -->
  subject,
  verb,
  object.

subject -->
  modifier,
  noun.

object -->
  modifier,
  noun.

modifier --> [the].

noun --> [cat].
noun --> [mouse].
noun --> [polar, bear].

verb --> [chases].
verb --> [eats].

They can be consulted and used exactly as the difference list version. That is, each of the rules has the two extra list arguments added to it, and the terminal cases are appropriately translated as well. Note that, to call a DCG predicate from a non-DCG predicate, you must add the two hidden list arguments.

?- sentence(X,[]).
X = [the, cat, chases, the, cat] ;
X = [the, cat, chases, the, mouse] ;
...

You can see the result of the DCG preprocessor using listing/1:

?- listing(sentence).
user:sentence(_X1, _X2) :- 
    subject(_X1, _X3),
    verb(_X3, _X4),
    object(_X4, _X2).
yes

Notice the generated linked difference lists.

When debugging DCG applications, the debugger will be using the translated versions of the rules, with the difference lists.

The DCG preprocessor is a built-in predicate in Prolog, which is implemented in Prolog. It is called automatically when clauses are consulted or compiled. It can also be called directly.

expand_term(DCGclause, PROLOGclause)

The predicate that translates a DCG statement into conventional Prolog is expand_term/2. It is called automatically when a clause is consulted, reconsulted, or compiled. But it can be called directly as well. The source code is also available in the sample dcgxpand.pro.

The first argument is a DCG clause, the second is the generated Prolog clause.

For example:

?- expand_term( (a --> b, c), X ).
X = a(H52, H54) :- b(H52, H69) ',' c(H69, H54) 
yes

Applications of DCG and Difference Lists

If you consider grammar rules as being rules defining structural relationships, then difference lists can be used in any application that is either analyzing (parsing) or generating based on rules for structural relationships.

Language Translation

We can have our grammar for sentences generate a parse tree, which can be thought of as representing universal concepts of language, such as all(?) languages have the concepts of subject, verb and object, although they are expressed in different orders.

Here's the English sentences, wrapped in a module, and generating a parse tree.

:- module(english).
:- export(sentence/3).

sentence(s(S,V,O)) --> subject(S), verb(V), object(O).

subject(sb(M,N)) -->  modifier(M),  noun(N).

object(ob(M,N)) -->  modifier(M),  noun(N).

modifier(m(the)) --> [the].

noun(n(dog)) --> [dog].
noun(n(cow)) --> [cow].

verb(v(chases)) --> [chases].
verb(v(eats)) --> [eats].

:- end_module(english).

Trying it:

?- english:sentence(M, [the,dog,chases,the,cow], []).
M = s(sb(m(the),n(dog)),v(chases),ob(m(the),n(cow))) 
yes

?- english:sentence(s(sb(m(the),n(dog)),v(chases),ob(m(the),n(cow))), S, []).
S = [the, dog, chases, the, cow] 
yes

We can write a similar module for Spanish. Note that modifiers and nouns must agree in gender in Spanish, and an extra argument in the subject and object rules enforces that restriction.

:- module(spanish).
:- export(sentence/3).

sentence(s(S,V,O)) --> subject(S), verb(V), object(O).

subject(sb(M,N)) --> modifier(M, G), noun(N, G).

object(ob(M,N)) --> modifier(M, G), noun(N, G).

modifier(m(the),m) --> [el].
modifier(m(the),f) --> [la].

noun(n(dog),m) --> [perro].
noun(n(cow),f) --> [vaca].

verb(v(chases)) --> [caza].
verb(v(eats)) --> [come].

:- end_module(spanish).

We can now write a generic translate predicate, that uses the modules for different languages.

translate(LANG_IN, LANG_OUT, SENTENCE, TRANSLATION) :-
  call( LANG_IN:sentence(MEANING, SENTENCE, []) ),
  call( LANG_OUT:sentence(MEANING, TRANSLATION, []) ).

And try it:

?- translate(english, spanish, [the,dog,chases,the,cow], T).
T = [el, perro, caza, la, vaca] 
yes

?- translate(spanish, english, [la,vaca,come,el,perro], T).
T = [the, cow, eats, the, dog]
yes

Bill of Materials

In Programming in Prolog Clocksin and Mellish describe the use of difference lists for generating a list of the required basic parts for building something. This is the classic bill-of-materials application, where the rules for the relationships between components can be thought of as grammar rules. The application can be expressed using DCG.

bike --> frame, drivechain, wheel, wheel.

wheel --> spokes, rim, hub.

drivechain --> crank, pedal, pedal, chain.

spokes --> [spokes].
crank --> [crank].
pedal --> [pedal].
chain --> [chain].
rim --> [rim].
hub --> [hub].
frame --> [frame].

Trying it we can find the parts we need to build a bicycle:

?- bike(X,[]).
X = [frame, crank, pedal, pedal, chain,
     spokes, rim, hub, spokes, rim, hub] 
yes

?- wheel(X,[]).
X = [spokes, rim, hub] 
yes

?- wheel(X,Y).
X = [spokes, rim, hub | H2]
Y = H2

Command Language

DCG can be used to create a command language for an application. In this example, there is a simple airline flight reservation system in Prolog, that accepts commands to list planes, book a passenger on flight, or list passengers on a flight.

main :-
   write('Fly Amzi! Air'), nl,
   repeat,
   do_command.

do_command :-
   write('enter command> '),
   read_string(STRING),
   string_tokens(STRING, TOKENS),
   command(CLIST, TOKENS, []),
   COMMAND =.. CLIST,
   call(COMMAND),
   !,
   COMMAND == exit.
  
command([OP|ARGS]) --> operation(OP), arguments(ARGS).

arguments([ARG|ARGS]) --> argument(ARG), arguments(ARGS).
arguments([]) --> [].

operation(report) --> [list].
operation(book) --> [book].
operation(exit) --> ([exit]; [quit]; [bye]).

argument(passengers) --> [passengers].
argument(flights) --> [flights].

argument(FLIGHT) --> [FLIGHT], {flight(FLIGHT)}.
argument(PASSENGER) --> [PASSENGER].

flight(aa101).
flight(aa102).
flight(aa103).

report(flights) :-
   flight(F),
   write(F), nl,
   fail.
report(_).

report(passengers, FLIGHT) :-
   booked(PASSENGER, FLIGHT),
   write(PASSENGER), nl,
   fail.
report(_, _).

book(PASSENGER, FLIGHT) :-
   assert(booked(PASSENGER, FLIGHT)).

exit.

Trying it:

?- main.
Fly Amzi! Air
enter command> list flights
aa101
aa102
aa103
enter command> book leona aa102
enter command> book ivan aa102
enter command> list passengers aa102
leona
ivan
enter command> quit

yes

XML

XML uses tags in an input stream to define structure. It is an excellent way to pass information between applications and across networks. The XML library uses DCG to translate between XML and Prolog terms in general. It is easy to create application-specific XML translators as well.

An XML parser/generator works on a character level, rather than a word level. Here is some DCG that recognizes tags, in angle brackets, and makes atoms out of characters that form words. Note that double quotes denotes a list of character codes.

Note also that we need two DCG rules for word/3, one for parsing, one for generating, so that the correct bindings are used in atom_codes/2.

tag(TAG) -->
   "<", word(TAG), ">".

endtag(TAG) -->
   "".

solotag(TAG) -->
   "<", word(TAG), "/>".

word(WORD) --> { var(WORD), ! },
   chars(CHARS), { atom_codes(WORD, CHARS) }.
word(WORD) --> { nonvar(WORD) },
   { atom_codes(WORD, CHARS) }, chars(CHARS).

chars([X|Y]) --> char(X), chars(Y).
chars([]) --> [].

char(X) --> [X], { is_char(X) }.

is_char(X) :- X >= 0'a, X =< 0'z, !.
is_char(X) :- X >= 0'A, X =< 0'Z, !.
is_char(X) :- X >= 0'0, X =< 0'9, !.
is_char(0'_).

Trying it:

?- tag(T, "<hello>", "").
T = hello 
yes

?- endtag(hi, CHARS, ""), string_list(S, CHARS).
CHARS = [0w003c, 0w002f, 0w0068, 0w0069, 0w003e]
S = `</hi>` 
yes

Consider the flight reservation application in the previous example. It might be an embedded component in a Logic Server application designed for network use. In that case, an XML front end would have make it easy to integrate with other network components. It would have only one entry point, which would take as input an XML string, and return as output an XML string.

Tags for input include command (com), operation (op), and arguments (arg). Tags for output are a list (list) and items (item).

Here is a different version of the flight reservation application, designed for XML input and output.

xml(XML_IN, XML_OUT) :-
   string_list(XML_IN, CHARS_IN),
   command([OP|ARGS], CHARS_IN, []),
   COMMAND =.. [OP,OUTPUT|ARGS],
   call(COMMAND),
   output_list(OUTPUT, CHARS_OUT, []),
   string_list(XML_OUT, CHARS_OUT).
   
command([OP|ARGS]) -->
   tag(com),
   operation(OP),
   arguments(ARGS),
   endtag(com).

arguments([ARG|ARGS]) --> argument(ARG), arguments(ARGS).
arguments([]) --> [].

operation(report) --> tag(op), word(list), endtag(op).
operation(book) --> tag(op), word(book), endtag(op).

argument(ARG) --> tag(arg), word(ARG), endtag(arg).

output_list(L) --> tag(list), items(L), endtag(list).

items([A|Z]) --> tag(item), word(A), endtag(item), items(Z).
items([]) --> [].

flight(aa101).
flight(aa102).
flight(aa103).

report(OUT, flights) :-
   findall(F, flight(F), OUT).

report(OUT, passengers, FLIGHT) :-
   findall(P, booked(P, FLIGHT), OUT).

book([ok], PASSENGER, FLIGHT) :-
   assert(booked(PASSENGER, FLIGHT)).

Given that its awkward to type XML, here is a predicate that tests the program, using the same inputs as in the previous non-XML example.

test :-
   xml( `<com><op>list</op><arg>flights</arg></com>`,
        OUT1 ),
   write(OUT1), nl,

   xml( `<com><op>book</op><arg>leona</arg><arg>aa102</arg></com>`,
        OUT2 ),
   write(OUT2), nl,

   xml( `<com><op>book</op><arg>ivan</arg><arg>aa102</arg></com>`,
        OUT3 ),
   write(OUT3), nl,

   xml( `<com><op>list</op><arg>passengers</arg><arg>aa102</arg></com>`,
        OUT4 ),
   write(OUT4), nl.

Trying it:

?- test.
<list><item>aa101</item><item>aa102</item><item>aa103</item></list>
<list><item>ok</item></list>
<list><item>ok</item></list>
<list><item>leona</item><item>ivan</item></list>

yes

DCG Terminals

In the examples above we showed DCG terminals being generated as difference lists. This is actually done in two steps. The DCG preprocessor first translates the rule to call a built-in predicate, dcg$terminal/3. It then generates the difference lists.

For example:

?- expand_term( (noun --> [dog]), X ).
X = noun(H52, H54) :- dcg$terminal([dog], H52, H54) 
yes

?- dcg$terminal([dog], X, Y).
X = [dog | H7]
Y = H7 
yes

It is possible to override this normal DCG behavior on terminal handling. dcg$terminal/3 first looks for an optional user written override of terminal handling, by calling dcg_terminal/3. If it exists, it is used instead.

By creating a custom dcg_terminal/3, you can generate the terminals in a different way, and the two parts of the difference list can be of any structure you might like. This is because the difference list arguments are simply passed down, and are only actually used when processing terminals.

One practical application of this is for character parsing of large files. It is not practical to read a large file into memory as a Prolog list of characters, but it is possible to read it in as a list of strings representing the lines in the file.

If the difference lists input to the DCG are the list of strings representing lines, then a customized version of dcg_terminal/3 can be used to convert just the line being worked on into a list of characters.

This is the approach used by the program that parses the HTML files of this documentation, looking for tags to create index entries. It uses a colon to separate the list of characters currently being used, and the list of lines. Whenever there are not enough characters to satisfy a terminal, more are added from the next line.

dcg_terminal(Ts, Ts:[], []:[]) :- !.
dcg_terminal(Ts, T0:Lines, T1:Lines) :-
  length_lte(Ts, T0),
  !, append(Ts, T1, T0).
dcg_terminal(Ts, T0:[Line|Lines], T1:Ls) :-
  string_tokens(Line, T, $<>/"=!;&%*+-.\\:?@^~$),
  append(T0, T, T00),
  dcg_terminal(Ts, T00:Lines, T1:Ls).

The main DCG predicate is called parse_html in that application, and it is called with difference lists representing the lines in the input file.

parse_html([]:Lines, []:[])

The actual DCG parsing rules are all written exactly as they normally would.

Parsing Files

The internal dcg_terminal recognizes the case of a file parsed as a list of strings, which is to be parsed as a list of characters. That is, if you want to parse a file as a character list you don't need to create a custom dcg_terminal.

To use this format, you first read the file in as a list of strings, and store each line in the structure: line(LineNumber, String). The following code can be used to do that.

read_file(File, Lines) :-
   open(File, read, _, [alias(in)]),
   read_string(in, Line),
   read_lines(line(1,Line), Lines).

read_lines(line(_,end_of_file), []) :-
   !.
read_lines(line(N,L), [line(N,L)|Lines]) :-
   read_string(in, NextLine),
   NN is N + 1,
   !, read_lines(line(NN,NextLine), Lines).

To use the list of lines in a grammer, make the call to the top predicate of the grammar using the format file(FileName, [], Lines). Here is an example from a program that reads Prolog clauses from a file.


parse_file(FileName, Lines) :-
   clauses(file(FileName, [],Lines), file(FileName, [],[])).

In your parsing predicates, you can use a trick to get the current line number. You write a predicate, get_current_line/3 that you expand yourself, rather than letting the DCG do it. It makes use of the fact that the second argument to the file/3 structure is a list of characters of the line currently being parsed.

current_line_number(N, file(F, [],[line(N,L)|Lines]), file(F, [],[line(N,L)|Lines])) :-
   !.
current_line_number(NN, file(F, Tokens,[line(N,L)|Lines]), file(F, Tokens,[line(N,L)|Lines])) :-
    NN is N - 1.

Here is an example of it in use.

aclause -->
   current_line_number(L),
   aterm(H, L, [],VarListR),
   ".",
   ...