Prolog - parsing functions with DCG

Question

I need to parse a string representing function like this:

<fsignature>"(" <term1>, <term2> ... <termn>")"

The function' signature and terms also have to be controlled further for the function to be accepted. I've written this DCG in Prolog:

fsign --> {is_leg(A)}, [A].
terms --> (funct, funct; terms).
terms --> (terms, terms; term).
term --> {is_term(T)}, [T].

But it doesn't seem to work, when I try to use phrase(funct, [foo, "(", a, a, ")"]). it goes into overflow. is_leg just checks if the string is legal (a string starting with a character), while is_term should check if the term is a literal (either a constant, a variable or a function).

What is that it's not working? I figure, probably the variables - should I put them as arguments of the nonterminals?

Thanks for any help.

Something like, terms --> (terms, terms ; term). is the same as: terms --> terms, terms. and terms --> term. The first is clearly going to be an infiinite recursion. It's unclear what you want this rule to say. — lurker
The functions could have arity n, so it could possibly have an infinite number of arguments, that's why I put in that rule. The language should be infinite, but it should tell me which strings are accepted and what aren't, shouldn't it? — nass.hbs
You don't mean it would have an infinite number of arguments, do you? You really mean it could have any number of arguments, but any given term has a finite number. There's just no limit to how many. At some point, the parsing has to finish, meaning the input sequence has a finite number of elements. — lurker

lurker lurker · Accepted Answer · 2017-02-03T17:48:06

If your expressions all look like this:

<fsignature> "(" <term1> <term2> ... <termn> ")"

Then writing this out in terms of DCG, it should look something like this (minus any string validation predicates you're suggesting):

expression --> fsignature, ['('], terms, [')'].
fsignature --> ...      % whatever fsignature looks like
terms --> term.         % "terms" is a single term, or...
terms --> terms, term.  %   ... more terms followed by a single term.
term --> ...            % whatever a term looks like

You can also write the definition of terms as:

terms --> term | terms, term.

Note that the non-recursive definition of terms occurs before the recursive one. Also, the definition for terms above assumes that you must have at least one term (this requirement wasn't stated in your question).

Prolog - parsing functions with DCG

1 Answers