Definite Clause Grammars in Lisp – Part 4

In a series of articles written earlier, I had shown how it is possible to model Definite Clause Grammars (DCG) in LispWorks Lisp (Enterprise Edition). We use defgrammar in Common Prolog (available as part of KnowledgeWorks package) to define our grammar rules.

Here is a toy English grammar represented using defgrammar:

DCG Using Defgrammar

This corresponds to the following Prolog DCG grammar:

Corresponding Prolog DCG

You will notice that the Prolog syntax is less verbose and hence more expressive than the defgrammar version (you can ignore the minor difference in the naming of non-terminal names).

We need not lose heart because Lisp is a “programmable programming language”, and we can improve the existing syntax to suite our preference!

Here is the improved version of the same defgrammar:

Simplified Defgrammar

If you look at the grammar carefully, you will notice that it does not explicitly build the parse tree, whereas the other two versions do! The tree building happens inside the generated defgrammar code.

So, what is the trick? The trick is that we write suitable macros to convert our simpler syntax to the corresponding defgrammar version:

The Core Macros

The above shows the core logic involved in the syntax transformation. The full source code is available here.

Let us now check the grammar with some sample sentence fragments:

Sample Session

Here is a sample session in Sicstus Prolog 4.7.0 for the Prolog DCG:

Sample Session – Prolog

You can see that the outputs match.

Here comes an important question: If I have to implement an NLP parser in DCG, is it better to do this in Prolog directly, or use defgrammar (perhaps using the tricks shown here) in Lisp?

I guess the answer is not straightforward. If you are a Lisp programmer (using LispWorks) and you are not comfortable with Prolog, then defgrammar is probably the natural approach. The other advantage is that you can easily integrate this with other Lisp code, if needed. In my case, I would prefer using Prolog directly (especially Sicstus Prolog) since I can get better performance on large grammars. 

This article concludes the series on using DCG in Lisp. Hope you find this series useful.

The Lisp source is available here .

Have a nice weekend! 

Tags: DCG, Definite Clause Grammar, LISP, Prolog