Infinite list of terminals – Prolog grammar rules

Question

Is it possible to define an indefinite number of terminals in Prolog when working with grammar rules?

The following example describes the problem:

selection-->([if,'('],condition,[')',
then,'{'],commands,['}']);([if,'('],condition,[')',
then,'{'],commands,['}',else,'{'],commands,['}']).
condition-->[X].
commands-->[X].

Here, the "condition" and the "commands" blocks can have an indefinite number of elements. How to specify that in Prolog? The production rules for the condition and the commands I've provided here allow only one atom.

I want the following statement to be truthful, but this rule, condition-->[X]., allows only one atom between those parentheses:

selection([if,'(',a,<,b,')',then,'{',a,+,+,'}',else,'{',c,'}'], []).

Appendix

How to make the program create a syntax tree from a statement? For example, if the following statement is entered:

selection( S, [ if, '(', a, <, b, ')', then, '{', a, +, +, '}' ], [] ).,

the result should be S = selection(if(condition([a,<,b])),then(commands([a,+,+]))).

What changes to the code do I need to make?

Thank you very much in advance.

CapelliC CapelliC · Accepted Answer · 2012-12-14T06:26:41

use recursion:

condition --> [X], ( condition_separator, condition ; [] ).

condition_separator could be empty, then omit it

edit

To generate the syntax tree, the easiest way it's to add arguments to productions, reproducing the 'shape' (untested code):

selection(Tree) -->
  [if,'('], condition(Condition1), [')', then,'{'], commands(Commands1), ['}'],
  {Tree = selection(Condition1, Commands1)}
  ;
  [if,'('],condition(Condition1),[')', then,'{'], commands(Commands1),
  ['}', else,'{'], commands(Commands2),['}'],
  {Tree = selection(Condition1, Commands1, Commands2)}
  .

condition(X)-->[X].
commands(X)-->[X].

then when visiting the tree use the different arity (arguments count) of selection to recover the parsed branch.

Let's say we have command list where each command is terminated by ';': that could be

commands([C|Cs]) --> command(C), [';'], commands(Cs).
commands([]) --> [].

Infinite list of terminals – Prolog grammar rules

1 Answers