Prolog and Definite Clause Grammar

Learning prolog is much more fascinating than what I thought it would be.I just studied how to create a CFG (Context Free Grammar) recognizer in prolog. Even though, you could do it in various methods, the best way is to use DFG(Definite Clause Grammar). DFG can be considered as a simple tool provided by Prolog for encoding CFG. But DFG’s go much beyond that. It is possible to write recognizers for non context free grammars in DFG. In fact DFG’s are syntactic sugar provided by prolog.A recognizer for CFG is a machine (program) which accept all the strings defined by the grammar.

Let’s write the grammar for accepting infix expression with operators +,x and numbers 0,1 ie., 1+0, 1*1+0, etc belongs to the language. The grammar can be written as :-

E-> T+E|T

T-> F*T|F

F-> 0,1.

So now let us convert this to a DFG. First of all let us define all lexicons ie., +,*,0,1

lex(+,add).
lex(*,mul).
lex(’0′,f).
lex(’1′,f).

This means that the symbol + belongs to the category add. If we want to add another symbol – to the grammar which has the same priority of +, we just have to add lex(-,add).

Now let us write a simple grammar that would go with the lexicon.

f –> [W],{lex(W,f)}.
a –> [W],{lex(W,add)}.
m –> [W],{lex(W,mul)}.

The new rule ‘f’ says that it contain a list with a W and an extra constrain that “It’s ok as long as W matches with something defined as lexicon f”. Similar is the case with a and m.

Now it is time to define the rules..

e –> t.
e –> t,a,e.
t –> f.
t –> f,m,t.

Copy all those things written in green into a file ‘infix.pl’. Now reconsult the file in prolog interpreter ie., take your prolog interpreter and type

|?-[infix].

Now it is time for some action. Let’s check if a sentence belong to the grammar. Type as follows.

!?-e(['1',*,'1',+,'0'],[]).

and you will get an answer ‘yes’, this shows that the sentence belong to the grammar. Quering e(x,[]), gives all values X can take(This will be an infinite one).

Look how simple is the code when compared to the C or Java program for the same.

Another interesting thing we could do is to create the DCG such that we get the parse tree for a sentence. Will be writing about it soon.

This entry was posted in Uncategorized. Bookmark the permalink.

4 Responses to Prolog and Definite Clause Grammar

  1. anonymous says:

    hi vivek! i need some help with prolog programming, maybe you should help me!!
    my msn messenger is deicq@hotmail.com

    tks!

  2. pramode_ce says:

    Cool stuff!

  3. vivek_b says:

    Sir, it is great to have your appreciation.

Leave a Reply

Your email address will not be published. Required fields are marked *

8 + two =

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>