Сдвиг / уменьшение конфликта с вложенными списками

Question

Я работал над "Современной реализацией компилятора в ML", преобразовывая SML в OCaml, когда я иду. Книга определяет язык под названием Тигр, который имеет let ... in ... end синтаксис для объявления типов, переменных и функций в области видимости для данного выражения. Кроме того, смежные объявления одного и того же вида должны быть сгруппированы вместе, чтобы обеспечить взаимную рекурсию.

Я попытался представить это Менгир со следующим фрагментом грамматики:

%right FUNCTION TYPE

.
.
.

decs: l = list(dec) { l }

dec:
  | l = nonempty_list(tydec) { A.TypeDec l }
  | v = vardec { v }
  | l = nonempty_list(fundec) { A.FunctionDec l }

tydec:
  | TYPE; name = ID; EQUAL; ty = ty {
      A.{
        type_name = Symbol.symbol name;
        type_ty = ty;
        type_pos = Position.make $startpos $endpos
      }
    }

С этим я получаю конфликт сдвига / уменьшения, но Менгир решает его так, как мне бы хотелось. Я хочу nonempty_list(typec) быть жадным до смежных TYPE декларации сгруппированы вместе. То есть с разрешением конфликта Менгиром мой сгенерированный AST выглядит примерно так:

(LetExp
  (decs
    ((TypeDec
      (((type_name (my_type)) (type_ty (NameTy (int))))
       ((type_name (my_type2)) (type_ty (NameTy (string))))
    ))))
  (body (SeqExp ())))

Я хотел бы избавиться от предупреждения, но не могу решить конфликт так же, как Менгир. Я пытался использовать %inline tydecчто делает предупреждение уйти, но сдвиг TYPE не применяется, как я ожидал. Вместо этого предпочтение отдается списку в decs, получая AST, который выглядит так:

(LetExp
  (decs
    ((TypeDec
      (((type_name (my_type)) (type_ty (NameTy (int))))))
     (TypeDec
      (((type_name (my_type2)) (type_ty (NameTy (string)))
  )))))
  (body (SeqExp ())))

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

Я уверен, что мне здесь не хватает чего-то фундаментального. Дайте произведения, которые дают списки списков, как я могу сделать внутренний список жадным?

Answer 1

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

Допустим, у нас есть некоторый язык со следующим синтаксисом:

vardef  i = 42
        j = 24
typedef all_new_int  = int
        all_new_bool = bool

в этом случае вполне логично определить что-то вроде этого:

decs: l = list(dec) { l }

dec:
  | l = TYPEDEF nonempty_list(tydec) { A.TypeDec l }
  | ...

и в этом случае из-за typedef у нас нет никаких конфликтов. Теперь, если такого "разделителя" нет, а просто:

    var i = 42
    var j = 24
    type all_new_int  = int
    type all_new_bool = bool

Зачем пытаться перегруппировать эти два типа объявлений? Это не блок (как в предыдущем примере), а два отдельных объявления. Таким образом, AST должен быть согласован с языком. Я знаю, что это не ответ, который вы ищете, но я пытаюсь сказать, что вам не нужно nonempty_list в dec:

decs: l = list(dec) { l }

dec:
  | l = tydec { [A.TypeDec l] }
  | v = vardec { v }
  | l = fundec { [A.FunctionDec l] }

И в этом случае, возможно, ваш dec не нужно возвращать список. Да, ваш AST будет таким же, как и для %inline tydec, но это связано с языком.

Кстати, из менгирской документации:

фактический + является синтаксическим сахаром для nonempty_list(фактический)

---

Редактировать:

Если вы не хотите менять свою структуру (по какой-то причине), вы всегда можете переписать свои правила, например, эти две грамматики абсолютно одинаковы:

1) со смещением / уменьшением

%token <int> INT
%token NONE
%token EOF

%start <int option list list> main

%%

main: l = op_list* EOF { l }

op_list:
      l = num+ { l }
    | NONE   { [None] }

num: i = INT { Some i }

2) Без сдвига / уменьшения

%token <int> INT
%token NONE
%token EOF

%start <int option list list> main

%%

main: ll=main2 EOF { ll }

main2:
    { [] }
    | n=num ll=main2 { match ll with
                       | ((Some i)::l)::ll -> ((Some i)::(Some n)::l)::ll
                       | _ -> [Some n]::ll
                     }
    | NONE ll=main2 { [None]::ll }

num: i=INT { Some i }

Еще раз, вот когда я вижу 0 NONE 1 2 NONE 3 я думаю о [0; None; 1; 2; None; 3] и не [[0]; [None]; [1; 2; 3]; [None]; 3] но если второе решение более простое для будущего использования, тогда хорошо. Я уверен, что вы можете сделать это с %prec и компания (%left, %right,...), но в любом случае вам нужно переписать свои правила. Когда у вас есть конфликт, вам нужно разрешить его, магии нет.

6.3 Как решаются серьезные конфликты в конце? Не указано, как решаются серьезные конфликты. Менгир пытается имитировать спецификацию ocamlyacc, то есть разрешать конфликты сдвига / уменьшения в пользу сдвига и разрешать конфликты уменьшения / уменьшения в пользу производства, которое в текстовом виде появляется раньше в спецификации грамматики. Однако эта спецификация является противоречивой в случае трехсторонних конфликтов, то есть конфликтов, которые одновременно включают в себя действие сдвига и несколько действий сокращения. Кроме того, приоритет текста может быть неопределенным, когда спецификация грамматики разделена на несколько модулей. Короче говоря, философия Менгира заключается в том, что нельзя допускать серьезных конфликтов, поэтому вас не должно волновать, как они разрешаются.