Используйте Camlp4 для анализа строки универсальных и экзистенциальных квантификаторов

Question

Я использую Camlp4 для анализа строки квантификаторов, в которых ключевые слова и переменные квантификации разделены запятой. Один пример как ниже:

exists x,y,z, forall a,b, exists h,k

Вот, exists а также forall являются ключевыми словами, x,y,z,a,b,h,k являются идентификаторами. Соответствующие токены EXISTS, FORALL а также IDENTIFIER of string,

Моя структура данных:

type quantifier =
  | Exists of string
  | Forall of string

Чтобы разобрать строку квантификаторов выше, мои правила:

id: [[
  `IDENTIFIER s-> s
]];

one_kind_quantifiers: [[
  `EXISTS; il=LIST1 id SEP `COMMA -> List.map (fun v -> Exists v) il
 |`FORALL; il=LIST1 id SEP `COMMA -> List.map (fun v -> Forall v) il
]];

quantifiers: [[
  t=LIST0 one_kind_quantifiers SEP `COMMA -> List.flatten t
]];

Однако мой парсер всегда выдает ошибку:

Stream.Error("[id] expected after COMMA (in [one_kind_quantifiers])").

Вы знаете, как решить эту проблему? Как сделать LIST1 прекратить выдавать ошибку, когда он обнаруживает элемент после `COMMA такое ключевое слово?

Большое спасибо!

(Для получения дополнительной информации, если я использую пробел для разделения переменных, на которые воздействует одно и то же ключевое слово количественного определения, например exists x y z, forall a b, exists h k, И удалить SEP `COMMA в one_kind_quantifiers правило, то синтаксический анализатор может отлично проанализировать эту новую строку).

===========================

Обновление решения:

По предложению Игоря (@ygrek) я могу написать ожидаемый синтаксический анализатор, не используя LIST1, а вручную написав правила для разбора списка строк.

id_list: [[
  `IDENTIFIER s -> [s]
 |t=`id_list; `COMMA; `IDENTIFIER s -> t@[s]
]];

one_kind_quantifiers: [[
  `EXISTS; il=id_list -> List.map (fun v -> Exists v) il
 |`FORALL; il=id_list -> List.map (fun v -> Forall v) il
]];

quantifiers: [[
  t=LIST0 one_kind_quantifiers SEP `COMMA -> List.flatten t
]];

Обратите внимание, что правило для разбора списка строк:

id_list: [[
   `IDENTIFIER s -> [s]
 | t=`id_list; `COMMA; `IDENTIFIER s -> t@[s]
]];

но нет:

id_list: [[
   `IDENTIFIER s -> [s]
 | `IDENTIFIER s; `COMMA; t=`id_list -> [s]@t
]];

Второй способ написания id_list Правило выдает ту же ошибку, что и при использовании LIST1, (Так что я думаю, что, возможно, это так, что LIST1 реализовано...)

Answer 1

camlp4 является синтаксическим анализатором рекурсивного спуска, и IIRC будет возвращать его только по первому токену каждого правила, при совпадении с первым токеном он будет продолжаться до конца правила. В этом случае для LIST1 он может совпадать с запятой, поэтому он опускается, но второй токен не такой, как ожидалось, и уже слишком поздно возвращаться назад. Я думаю раскатывать LIST1 и вставка в вашу грамматику обойдет эту проблему, но, вероятно, будет довольно уродливой.