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

Я пытаюсь использовать 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 *)

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


parsing ocaml menhir lalr
person hugomg    schedule 29.03.2016    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Ну, во-первых, это проблема не совсем в Менгире, а в той грамматике, которую принимает Менгир, которая стоит в наборе 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 { }
person Marcelo Camargo    schedule 10.04.2018
comment
Спасибо за ответ! У меня складывается впечатление, что реальный урок здесь заключается в том, что можно сделать более явную грамматику с несколькими уровнями правила re вместо того, чтобы пытаться умничать с объявлениями приоритета. Даже в вашем последнем примере проблема действительно решается тем, что у вас есть отдельные правила re, term и base. - person hugomg; 10.04.2018