Prolog/Definite Clause Grammars
From Wikibooks, the open-content textbooks collection
Prolog has a mechanism for defining certain grammars called Definite Clause Grammars. It makes easy to write parsers.
Note that DCG syntax is not part of the official Prolog standard, although it is a de-facto standard.
Grammar rules can be written in the form:
head --> body
e.g.
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 expexted to be [ ] after a succesful 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.
[edit] 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.
Notes: 0'9 means the character 9 (or more precisely, the charactercode 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 ambigous. (There's only one possible parsing tree of the input.)
