"Правило бесполезно в парсере" с двумя операторами подряд

Я хочу написать грамматику с оператором, подобным оператору двоеточия Matlab, где "a:b" и "a:b:c" означают несколько разные вещи. И я бы предпочел, чтобы оператор был неассоциативным, так как "a:b:c:d" и т. д. не имело бы смысла.

Вот урезанная версия моей грамматики, чтобы показать, как я пытался это сделать: 

%union {
  int ival;
}

%token tINT

%nonassoc ':'

%%

program: { }
       | expression ';' { }

expression: tINT { }
          | expression ':' expression { }
          | expression ':' expression ':' expression { }

По какой-то причине Бизон игнорирует второе правило двоеточия, сообщая следующее: 

test.y:16.13-56: warning: rule useless in parser due to conflicts [-Wother]
           | expression ':' expression ':' expression { }
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Почему Бизон не понимает, чего я хочу здесь, и как я могу измениться? моя грамматика так работает?

Edit: в случае, если это поможет, выход из "bison-v" содержит

State 7

    4 expression: expression . ':' expression
    4           | expression ':' expression .
    5           | expression . ':' expression ':' expression
    5           | expression ':' expression . ':' expression

    ':'  error (nonassociative)

    $default  reduce using rule 4 (expression)
Хотя я все еще не понимаю, почему Бизон не должен этого допустить, и как это решить.
3 3
bison

3 ответа:

Вы указали, что оператор': 'неассоциативен. Удалите это, и вместо этого вы получите ожидаемые конфликты из A: B:C, которые можно разобрать как один из A:B:C, (A:B): C и A: (B: C).

Но поскольку вы хотите, чтобы он был неассоциативным, вот один из способов: 
%token tINT

%%

program: { }
        | colonexpression ';' { }
        ;

colonexpression: expression { }
        | expression ':' expression ':' expression { }
        | expression ':' expression { }
        ;

expression: tINT { }
        ;

%%
2

Ах! После долгих мучений я наконец нашел способ, который работает и все еще позволяет мне использовать приоритет "правильным" способом, хотя он требует, чтобы я назначил приоритет всем терминалам, которые могут появиться в выражении, если я хочу избежать тонн предупреждений shift/reduce. Кроме того, ему нужен фиктивный маркер, чтобы придать правилу с одним двоеточием соответствующий приоритет (немного ниже, чем':', чтобы избежать понятного конфликта shift-reduce).

Я не совсем доволен тем, что должен назначьте приоритет терминалам типа tINT, поскольку в моей реальной грамматике есть куча таких вещей, но я полагаю, что это придется сделать, если никто не имеет лучшей идеи.

%union {
  int ival;
}

%token tINT

%precedence nCOLON
%nonassoc ':'
%precedence tINT

%%

expression: tINT { }
          | expression_colon expression %prec nCOLON { }
          | expression_colon expression ':' expression { }

expression_colon: expression ':'
1

Не могли бы вы просто сделать его левоассоциативным с соответствующим приоритетом, а затем, как часть вашего кода действия, выдать ошибку, если там больше 2 двоеточий? То есть, не пытайтесь обрабатывать это в грамматике, но сделайте это семантическим ограничением, применяемым в коде C.

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

expression
    : expression ':' expression
    {
        if (Head($1) == DoubleColon)
            yyerror("Three-colon expressions are not allowed.");
        else if (Head($1) == Colon)
            $$ = DoubleColon(element_of($1, 1), element_of($1, 2), $3);
        else
            $$ = Colon($1, $3);
    }

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

Это интересная проблема. Я столкнулся с этим в синтаксическом анализаторе, который я писал, и я никогда не мог прийти к общему решению. В моем случае два двоеточия имели разные контексты и разные прецеденты. Это похоже на что-то автомат сокращения сдвига должен быть в состоянии это сделать, но не ясно, как сказать зубру, чтобы он сгенерировал нужные вам таблицы переходов. В конце концов, я должен был решить ее с помощью взлома лексера, который вызывает обратно в синтаксический анализатор, чтобы сделать "имитированный синтаксический анализ", метод, который Bison 3.0 использует в своей функции LAC.
1