Менгир - правила ассоциативности для сокращения последовательностей выражений

Question

Написание парсера для лямбда-выражений,

data expr = Symbol of string | Lambda of string * expr | App of expr * expr

При написании .mly файл, как я могу выразить идею, что последовательность выражений

e1 e2 e3 e4 

должен быть разобран как

App ((App (App e1 e2) e3) e4)

Используя правила:

%public expr_expr:
    | ID        { Symbol ($1) }
    | NUMBER    { Symbol ($1) }
    | LPAREN expr_expr RPAREN { ($2) }
    | LAMBDA ID ARROW expr_expr { Lambda ($2, $4) }
    | expr_expr expr_expr { Apply ($1, $2) }

дает структуру (e1 , (e2 , (e3 , e4))) в отличие от (((e1, e2), e3), e4), Есть ли способ управления ассоциативностью правила в отличие от токена?

Answer 1

Отказ от ответственности: я использую ocamlyaccне menhirпоэтому я основываю свой ответ на первом. AFAIUI, последний обратно совместим с ним, поэтому я предполагаю, что мой ответ может быть полезен в любом случае.

Ссылаясь на документацию http://caml.inria.fr/pub/docs/manual-ocaml/lexyacc.html:

Правила также могут содержать директиву символа%prec в правой части, чтобы переопределить приоритет по умолчанию и ассоциативность правила с приоритетом и ассоциативностью данного символа.

Так что я бы попробовал с

%left Application

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

| expr_expr expr_expr { Apply ($1, $2) } %prec Application

Это делает Application фиктивный символ, используемый только для присвоения ассоциативности и приоритета.

Примечание 1: Вышесказанное отчасти является догадкой с моей стороны. Очевидно, я никогда (успешно) не пробовал себя таким образом. Когда я однажды написал лямбда-грамматику, я применил ассоциативность, изменив грамматику.

Примечание 2: Если это не работает, как указано выше, вы можете взглянуть на исходный код OCaml. Язык OCaml имеет такой же синтаксис для приложения.