Optional or Repeated Items in Prolog DCG

Question

So I'm writing a simple parser for Pascal in SWI-Prolog using Definite Clause Grammars.

I don't understand how to implement repeating (2 or more) or optionally repeating (1 or more) predicates.

For example, in EBNF, for Pascal's "program" is:

"PROGRAM" identifier "(" identifierlist ")" ";" block "."

Where "identifierlist" is:

identifier { "," identifier }

and "identifier" is:

letter { letter | digit }

I know in prolog's DCG form program is:

program --> ["PROGRAM"], identifier, ["("], identifierlist, [")"], [";"], block, ["."].

How do I implement "identifierlist" or even "identifier", which contains an optionally repeating number of "identifier" or "letter" or "digit" predicates?

When you say "optionally repeating" do you mean it could be empty? Your definition of identifierlist doesn't seem to indicate so. — lurker
If it could be empty "identifierlist --> []." should do the trick. So, I don't believe I'm referring to an empty case. — MisterCrazy8

lurker lurker · Accepted Answer · 2018-03-02T19:59:35

In Prolog, you can just about write it exactly as the EBNF as long as the EBNF is really what you intend.

identifierlist = identifier { "," identifier }

You could also write this as:

identifierlist = identifier
identifierlist = identifier , identifierlist

In Prolog, you would write this as:

identifier_list --> identifier.
identifier_list --> identifier, ",", identifier_list.

If you want to include an empty identifier list, then it's a little more elaborate:

identifier_list --> [].
identifier_list --> nonempty_identifier_list.

nonempty_identifier_list--> identifier.
nonempty_identifier_list--> identifier, ",", nonempty_identifier_list.

Your original EBNF does not include an empty identifer list. If it did, the above code might look a lot like the EBNF.

nonempty_identifier_list

nonempty_identifier_list --> identifier, ( [] | ",", nonempty_identifier_list ).

Optional or Repeated Items in Prolog DCG

1 Answers