В Менгире возможно ли сделать правило левоассоциативным, если у него нет оператора?

Question

Я пытаюсь использовать Menhir для написания парсера для языка регулярных выражений. Моя желаемая грамматика, прежде чем я изменю ее, чтобы устранить неоднозначности, выглядит немного как следующий пример. Обратите внимание, что "последовательность / конкатенация" неявна, и с этой операцией не связан токен.

%token LPAREN RPAREN
%token CHAR STAR PIPE
%token EOF

%start <unit> parse

%%

parse: re EOF {()}

re:
  | LPAREN re RPAREN {()}  (* Grouping *)
  | CHAR             {()}  (* Single character *)
  | re STAR          {()}  (* Kleene star *)
  | re re            {()}  (* Sequencing / Concatenation *)
  | re PIPE re       {()}  (* Alternation *)

Если бы у меня был токен для конкатенации, я мог бы удалить неоднозначности, просто используя объявления приоритетов

%token LPAREN RPAREN
%token CHAR STAR PIPE
%token CONCAT
%token EOF

%left PIPE
%left CONCAT
%nonassoc STAR

%start <unit> parse

%%

parse: re EOF {()}

re:
  | LPAREN re RPAREN   {()}  (* Grouping *)
  | CHAR               {()}  (* Single character *)
  | re STAR            {()}  (* Kleene star *)
  | re CONCAT re       {()}  (* Sequencing / Concatenation *)
  | re PIPE re         {()}  (* Alternation *)

Однако я не могу заставить работать вещи без токена CONCAT в правиле конкатенации. Я пытался с помощью %prec декларация, но остались еще некоторые сдвиги / сокращения конфликтов.

%token LPAREN RPAREN
%token CHAR STAR PIPE
%token CONCAT
%token EOF

%left PIPE
%left CONCAT
%nonassoc STAR

%start <unit> parse

%%

parse: re EOF {()}

re:
  | LPAREN re RPAREN   {()}  (* Grouping *)
  | CHAR               {()}  (* Single character *)
  | re STAR            {()}  (* Kleene star *)
  | re re %prec CONCAT {()}  (* Sequencing / Concatenation *)
  | re PIPE re         {()}  (* Alternation *)

Я думаю, это может быть из-за того, что менгир не может сказать, что секвенирование должно быть левоассоциативным, но я не уверен на 100%, является ли это причиной проблемы.

Пока единственное решение, которое я мог найти, заключалось в re Правило в кучу различных правил, которые делают уровни приоритета и ассоциативности явными:

%token LPAREN RPAREN
%token CHAR STAR PIPE
%token EOF

%start <unit> parse

%%

parse: re EOF {()}

re: re3 {()}

re0:
  | LPAREN re RPAREN {()}  (* Grouping *)
  | CHAR             {()}  (* Single character *)

re1:
  | re0              {()}
  | re0 STAR         {()}  (* Kleene star *)

re2:
  | re1              {()}
  | re2 re1          {()}  (* Sequencing / Concatenation *)

re3:
  | re2              {()}
  | re3 PIPE re2     {()}  (* Alternation *)

Хотя этот последний пример работает нормально, мне действительно любопытно, можно ли было бы устранить все недостатки и конфликты, просто используя декларации приоритетов и ассоциативности, без необходимости переписывать грамматику.

Answer 1

Ну, во-первых, это не совсем проблема Менгира, но в виде грамматики, которую Менгир принимает, что стоит в LR(1) задавать. Если грамматика, которую вы предоставляете, не нуждается в предшествующих аннотациях, грамматика принимается за SLR(1)подмножество LR(1),

Ваш последний пример работает, потому что у вас есть произведения для каждого уровня приоритета (например, синтаксический анализ грамматик выражений, которые однозначны по своей природе), и определенно это не плохой способ написания; несколько современных компиляторов используют эту нотацию для обработки более сложных языков.

Чтобы понять вашу проблему, давайте сначала попросим Менгира объяснить, где живут конфликты:

menhir --explain parser.mly

Это сгенерирует parser.conflicts файл с объяснением того, в каких состояниях он может выполнять оба действия, уменьшать и сдвигать:

...
** In state 8, looking ahead at STAR, shifting is permitted
** because of the following sub-derivation:

re re
   re . STAR

** In state 8, looking ahead at STAR, reducing production
** re -> re re
** is permitted because of the following sub-derivation:

re STAR // lookahead token appears
re re .

** Conflict (shift/reduce) in state 7.
** Tokens involved: STAR PIPE LPAREN CHAR
** The following explanations concentrate on token STAR.
** This state is reached from parse after reading:

re PIPE re

** The derivations that appear below have the following common factor:
** (The question mark symbol (?) represents the spot where the derivations begin to differ.)

parse
re EOF
(?)

Грамматика действительно неоднозначна для LR(1), так:

CHAR CHAR STAR

может быть вычислено как:

• (CHAR CHAR) STAR
• CHAR (CHAR STAR)

Другой способ переписать вашу грамматику без конфликтов - сделать возможным объединение через list:

re:
| term PIPE re
| term { } (* Left associativity *)

term:
| list(base STAR* { }) { } (* Concatenation is taken by list *)

base:
| CHAR
| LPAREN re RPAREN { }