A sequence of optional grammar rules with menhir

Question

I would like to implement the following grammar in OCaml using Menhir parser.

There should be four different statement coming each after another, however, any three of them can be missing. So any program contains at least one of these statements, but can contain more coming in some specific order.

Here is the grammar:

main =  A  (B) (C) (D)
     | (A)  B  (C) (D)
     | (A) (B)  C  (D)
     | (A) (B) (C)  D

Is it possible to express it in a more concise representation?

Here is an example of parser.mly for this grammar:

%token <char> ACHAR BCHAR CCHAR DCHAR
%token EOF

%start <char option list> main
%type <char> a b c d
%%

main:
    a option(b) option(c) option(d) { [Some($1); $2; $3; $4] }
|   option(a) b option(c) option(d) { [$1; Some($2); $3; $4] }
|   option(a) option(b) c option(d) { [$1; $2; Some($3); $4] }
|   option(a) option(b) option(c) d { [$1; $2; $3; Some($4)] }
| EOF { [] }

a:
    ACHAR { $1 } (* returns 'A' *)

b:
    BCHAR { $1 } (* returns 'B' *)

c:
    CCHAR { $1 } (* returns 'C' *)

d:
    DCHAR { $1 } (* returns 'D' *)

For this case menhir produces warnings:

Warning: production option(a) -> a is never reduced.
Warning: production option(d) -> d is never reduced.

and cases such as A B C D, A, A C, B D are not matched. How to improve the grammar/parser implementation in order to fix this?

Answer 1

Try this:

main:
    a option(b) option(c) option(d) { [Some($1); $2; $3; $4] }
|   b option(c) option(d) { [None; Some($1); $2; $3] }
|   c option(d) { [None; None; Some($1); $2] }
|   d { [None; None; None; Some($1)] }

I removed the last option, which matches the empty sequence, because it contradicts your requirement that at least one of a, b, c or d be present. If you are prepared to accept empty, you could just use

main:
    option(a) option(b) option(c) option(d) { [$1; $2; $3; $4] }

although you might want to adjust the action to return [] in the case where all four options are None.

Answer 2

You can write a? instead of option(a). Also if you want to return four elements, you should use a tuple instead of a list.