8.3 Concluding Remarks
We now have a fairly useful picture of what DCGs are and what they can do for us. To conclude, let’s think about them from a somewhat higher level, from both a formal and a linguistic perspective.
First the formal remarks. For the most part, we have presented DCGs as a simple tool for encoding context free grammars (or context free grammars enriched with features such as subject and object ). But DCGs go beyond this. We saw that it was possible to write a DCG that generated a language that was not context free. In fact, any program whatsoever can be written in DCG notation. That is, DCGs are a full-fledged programming language in their own right (they are Turing-complete, to use the proper terminology). And although DCGs are usually associated with linguistic applications, they can be useful for other purposes.
How good are DCGs from a linguistic perspective? Well, mixed. At one stage (in the early 1980s) they were pretty much state of the art. They made it possible to code complex grammars in a clear way, and to explore the interplay of syntactic and semantic ideas. Certainly any history of parsing in computational linguistics would give DCGs an honourable mention.
Nonetheless, DCGs have drawbacks. For a start, their tendency to loop when the goal ordering is wrong (we saw an example in the previous chapter when we added a left-recursive rule for conjunctions) is annoying; we don’t want to think about such issues when writing serious grammars. Furthermore, while the ability to add extra arguments is useful, if we need to use lots of them (and for big grammars we will) it is a rather clumsy mechanism.
It is important to notice, however, that these problems come up because of the way Prolog interprets DCG rules. They are not inherent to the DCG notation. Any of you who have studied parsing algorithms probably know that all top-down parsers loop on left-recursive grammars. So, it is not surprising that Prolog, which interprets DCGs in a top-down fashion, loops on the left-recursive grammar rule s --> s conj s . If we used a different strategy to interpret DCGs, for example a bottom-up strategy, we would not run into the same problem. Similarly, if we didn’t use Prolog’s built-in interpretation of DCGs, we could use the extra arguments for a more sophisticated specification of features, one that would facilitate the use of large feature structures.
Summing up, nowadays DCGs are probably best viewed as a nice notation for defining context free grammars enhanced with some features, a notation that (ignoring left-recursion) doubles as a parser/recogniser. That is, they are best viewed as a convenient tool for testing new grammatical ideas, or for implementing reasonably complex grammars for particular applications. DCGs are no longer state of the art, but they are useful. Even if you have never programmed before, simply by using what you have learned so far you are ready to start experimenting with reasonably sophisticated grammar writing. With a conventional programming language (such as C++ or Java) it simply wouldn’t be possible to reach this stage so soon. Things would be easier in functional languages (such as Lisp, Caml, or Haskell), but even so, it is doubtful whether beginners could do so much so early.
