Prolog/Definite Clause Grammars

Prolog has a mechanism for defining certain grammars called Definite Clause Grammar notation. This makes it easy to write parsers. Note that while DCG syntax is part of the ISO standard, DCG semantics are not.

Grammar rules can be written in the form:

head --> body

For example:

sentence --> noun_phrase, verb_phrase.

Which will be translated to:

sentence(L0,LREMAINDER):-
   noun_phrase(L0,L1),verb_phrase(L1,LREMAINDER).

It means, that the sentence clause will receive L0 as input, and after parsing from a sentence from L0, it will give back LREMAINDER. Let's assume that your start symbol is sentence. Then LREMAINDER is expected to be [ ] after a successful parsing. The interpretation of the body of this clause is: if we parse a noun_phrase and a verb_phrase from our sentence, we will get back an empty list.

You can also call prolog predicates using braces.

Example

An example DCG program, which can parse numbers:

number --> digit, number_remaining.
number_remaining --> dot,number_remaining.
number_remaining --> digit,number_remaining.
number_remaining([],[]).
dot -->[0'.].
digit --> [J], {digit_code(J)}.
digit_code(J):- J >= 0'0, J =< 0'9.

Note: 0'9 means the character 9 (or more precisely, the character code of 9, because there's no distinct character datatype in SWI).

If you try to consult this program, you might get a warning, because we redefined the built-in number/2 predicate.

Running the program:

?- number("120",L).
L = [] ;
fail.

We get back one "result": it means that the parsing wasn't ambiguous. (There's only one possible parsing tree of the input.)

One of the earlier examples, revappend, can be written using DCG:

revappend([]) --> [].
revappend([X|Xs]) --> revappend(Xs), [X].

External links

Chomsky hierarchy of grammars on Wikipedia