Prolog and Definite Clause 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.