Definite Clause Grammars (DCGs)

Definite Clause Grammars (DCGs) are convenient ways to represent grammatical relationships for various parsing applications. Typically it is used on either a character basis, tokenizing an input stream, or on a word basis, interpreting either formal or natural language input.

For details on DCGs, refer to Adventure in Prolog or Programming in Prolog by Clocksin & Mellish, as well as the various sample programs that use DCG.

Often it takes an input list of characters or words and translates it into Prolog structures that are manipulated by the program. It can go the other way as well, taking the Prolog structures as input and generating lists of characters or words.

So, it can be used to extract the meaning from a list of words, which might be a sentence or part of a formal language, or it can be used to generate sentences or commands based on Prolog structures.

For example, the following DCG translates lists of words, which might be from input commands, into Prolog equivalents that can be executed. It takes commands of the form 'open file test for input' where the word 'for' is optional.

Mechanically, Prolog DCG is simply a shorthand notation for predicates that manipulate difference lists. The DCG translator takes clauses of the above form and translates them into normal Prolog clauses, with two additional arguments that represent difference lists which are propagated from goal to goal.

So, to call a DCG predicate, you put in the difference lists, where the second list is the empty list. To test the above DCG from the listener:

Like most Prolog predicates, it can be used to generate commands from Prolog as well as parse them:

In the DCG example, both trans and mode are DCG predicates. Sometimes you want to include, in the DCG rules, Prolog predicates that do not need to be embellished with the difference lists. You specify this by enclosing those clauses in curly brackets { }.

Suppose there was a list of files that a user was allowed to open, and you wanted the DCG to make sure the file specified by the user was on that list. The first DCG rule would then be rewritten as follows:

It is not necessary to enclose the cut (!) primitive in curly brackets.

Notice that the DCG has two types of goals. The goals which are represented in list notation, with square brackets [ ] are called terminals, meaning they call for direct extraction of information from the input list. The other goals are non-terminal, meaning they rely on other DCG rules to get their results.

expand_term(DCGclause, PROLOGclause)

The predicate that translates a DCG statement into conventional Prolog is expand_term/2. This predicate can be called directly. The first argument is a DCG clause, the second is the generated Prolog clause.

While this predicate is compiled into the core Prolog library, alib.plm, it is also available in source form in the samples library in the file DCGXPAND.PRO.

In normal DCG, the terminal lists are translated into goals that convert the single list into a difference list, where the difference is exactly the list presented. You can see how this works by calling the DCG translator directly.

The built-in predicate dcg$terminal creates the difference list. You can use it directly as well to see how it works.

Here is the definition of dcg$terminal.

dcg_terminal(LIST, DIFFLIST1, DIFFLIST2)

Notice that dcg$terminal attempts to call dcg_terminal/3. This is an optional user-defined predicate, meaning you can define dcg_terminal/3 in your application to provide any type of terminal handling you like.

Copyright ©1987-2000 Amzi! inc. All Rights Reserved.