[mercury-users] Parsing grammars using DCG

[Ralph Becket]

Douglas Michael Auclair, Sunday, 13 January 2002:
> 
> I'm working on a parser for grammars following BNF -- my code is (lifted 
> directly from Bratko's /Prolog: Programming for Artificial Intelligence/, 
> chapter 21):
> 
> ...
> :- pred move(list(string), list(string)).
> :- mode move(di, in) is semidet.
> 
> :- pred step(list(string), list(string)).
> :- mode step(di, in) is semidet.
> ...
> 
> move --> step.
> move --> step, move.
> 
> step --> [ "up" ].
> step --> [ "down" ].
> 
> 
> I've got the modes wrong here (DCG is a bit magical to me right now) ... 

The thing to do is to look at the syntax section of the Mercury
reference manual which explains how DCG code is translated into ordinary
code.

The typical parsing use for DCGs has the last two arguments (the DCG
arguments) for each production (DCG predicate) as the input token stream
for the production and the remainder of the input token stream after
matching the production respectively.

So the modes you want here are

:- mode move(in, out) is semidet.
:- mode step(in, out) is semidet.

The di mode stands for "destructive input", which is not what you
want.

> what I intend is to slurp in a file of this language and return a parse 
> tree (and, eventually, attach meaning to the parse nodes, e.g. "up" directs 
> a robot arm up 1 cm; "down", down 1 cm).  A bit lost here, what corrections 
> do I need to make, or what references/tutorials do I need to study to learn 
> about coverting files to input tokens and assigning proper mode 
> declarations for DCG over streams/lists/strings?

Once you've understood DCGs, it's almost certainly worth reading
something on classical parsing theory (e.g. selected parts of the Red
Dragon book) and then looking at moose, a yacc like program, in the
Mercury extras distribution.

- Ralph
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------