Bison shift уменьшить конфликт в запятой

Question

У меня есть странные предупреждения о сдвиге, независимо от того, что я меняю. Сокращенная грамматика:

expr : NUMBER 
    | NUMBER ',' expr 
    | expr ',' NUMBER ',' NUMBER 

Bison сообщает о смене сокращения на 2-ом правиле с запятой. Я попытался установить приоритет:

но предупреждение остается неизменным. Может кто-нибудь объяснить мне, что мне здесь не хватает?

Answer 1

Очевидно, что следующее неоднозначна:

expr : NUMBER %prec num_p 
    | NUMBER ',' expr %prec exp_p 
    | expr ',' NUMBER ',' NUMBER 

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

Рассмотрите, например, различные деревья разбора, которые могли бы произвести 1, 2, 3, 4, 5. Вот только две (с указанием номера, продукция которых была использована для расширения expr):

expr(2)      expr(3) 
    / \      / | \ 
/  \     / | | 
| expr(2)    / | | 
| / \    / | | 
| / \    expr(3) | | 
| / expr(3)  /| \  | | 
| | /| \  /| \ | | 
| |expr(1)| \  expr(1)| | | | 
| | | | |  | | | | | 
1 , 2 , 3 , 4 , 5  1 , 2 , 3 , 4 , 5 

Оба указанных выше деревьев, в некотором смысле, максимальной. Один слева имеет как можно больше одиночных NUMBER, используя производство 2, пока осталось только 2 NUMBER. 3. Правило применяет производство 3 столько раз, сколько возможно. (Было бы необходимо одно приложение производства 2, если список номеров имел бы четную длину.)

Чтобы устранить двусмысленность, нам нужна четкая формулировка намерения. Но мне кажется маловероятным, что его можно разрешить с помощью объявления приоритета. Помните, что отношения приоритета всегда находятся между возможной редукцией (в верхней части стека анализатора) и символ ожидания. Они никогда не сравнивают два символа взгляда и две постановки. Если выигрышный символ выигрывает, он смещается в стек; если выигрыш уменьшается, стек уменьшается. Это не сложнее.

Поэтому, если приоритет может помочь, соответствующий токен должен быть ',', а не NUMBER. NUMBER всегда должен быть смещен в стек синтаксического анализа. Так как никакое производство не заканчивается ',', никогда невозможно уменьшить стек, если NUMBER является символом lookahead. В отличие от этого, когда ',' является символом вида, обычно можно либо уменьшить верхнюю часть стека анализатора, либо сдвинуть ',' при подготовке к другому уменьшению.

Единственное место, где это решение возможно даже в том случае, когда мы видели NUMBER и смотрим на ',', поэтому мы должны решить, следует ли применять производство 1, в рамках подготовки к производству 3, или сдвигать ',' , оставив производство 2 единственным вариантом. Ни одно из этих решений не может преуспеть: если мы решили уменьшить, возможно, что производство 3 окажется невозможным, потому что в списке недостаточно номеров; если мы выберем смещение, то производство 3 никогда не будет использоваться.

В алгоритме слева направо алгоритм, который дает правильный синтаксический анализ выше, невозможен, потому что мы не можем знать, имеет ли список четную или нечетную длину до тех пор, пока мы не достигнем конца, слишком поздно, чтобы ретроактивно уменьшить первые два числа. С другой стороны, левый синтаксический анализ требует рассмотрения четырех токенов, а не одного, чтобы решить, в какой момент прекратить использование произведения 2. Это позволяет построить грамматику LR (1), поскольку существует способ переписать любую грамматику LR (k) как грамматику LR (1), но результирующая грамматика обычно сложна.

Я подозреваю, что ни то, ни другое не было вашим намерением. Чтобы рекомендовать резолюцию, необходимо будет знать, каково точное намерение.

Одним из возможных вариантов (мотивировано комментарий) является то, что expr также включает в себя то, что не является ни число, ни список номеров:

expr: NUMBER 
    | complex_expression 

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

• список, содержащий NUMBER с с возможно complex_expression в конце;

• список, содержащий четное число NUMBER s с возможно complex_expression в начале.

Что остается неоднозначным в приведенной выше формулировке представляет собой список, состоящий только из NUMBER с, так как первый или последний номер может быть проанализирован как expr. Здесь есть лишь несколько разумных возможных резолюций:

• список NUMBER с всегда быть проанализирован как первый вариант (expr в конце)

• список NUMBER s анализируется, как второй вариант (expr в начале) тогда и только тогда, когда в списке есть нечетное число элементов.

Первая резолюция намного проще, поэтому мы можем начать с нее. В этом случае первый элемент в списке, по существу, определяет, как будет обрабатываться список, поэтому невозможно сначала уменьшить NUMBER до expr. Мы можем выразить, что путем разделения различных типов expr:

expr: list_starting_expr | list_ending_expr 
list_starting_expr: complex_expression ',' NUMBER ',' NUMBER 
        | list_start_expr ',' NUMBER ',' NUMBER 
list_ending_expr : complex_expression 
        | NUMBER ',' list_ending_expr 
        | NUMBER 

Последнее производство в приведенном выше примере позволяет получить список полностью из NUMBER с до быть разобрано как list_ending_expr.

Он также содержит список, содержащий только один complex_expression, который обрабатывается как list_ending_expr, а list_starting_expr должен иметь как минимум три элемента. Без этого список, состоящий только из complex_expression, был бы неоднозначным. В примере грамматики в вопросе неявно запрещен список, содержащий только complex_expression; которые могут быть воспроизведены путем изменения базовой продукции на list_ending_expr от list_ending_expr: complex_expression до list_ending_expr: NUMBER ',' complex_expression.

Но что, если мы хотим получить вторую резолюцию? Мы все еще можем распознавать язык, но построение правильного дерева разбора может потребовать некоторой операции. Мы можем начать с выделения случая, когда список состоит только из NUMBER с.

expr: list_starting_expr | list_ending_expr | ambiguous_list 
list_starting_expr: complex_expression ',' NUMBER ',' NUMBER 
        | list_starting_expr ',' NUMBER ',' NUMBER 
list_ending_expr : NUMBER ',' complex_expression 
        | NUMBER ',' list_ending_expr 
ambiguous_list : NUMBER 
        | NUMBER ',' ambiguous_list 

Несмотря на часто повторяемые утверждения, что право рекурсии следует избегать в снизу вверх грамматик, здесь важно, чтобы ambiguous_list и list_ending_expr быть правым рекурсии, потому что мы не можем различать две возможности, пока мы не достигнем конец списка.

Теперь мы можем использовать семантическое действие, чтобы просто подсчитать количество элементов в списке. Это действие должно быть связано с уменьшением ambiguous_list к expr:

expr: list_starting_expr | list_ending_expr 
    | ambiguous_list { 
     if (count_elements($1) % 2 == 1) { 
      $$ = make_list_starting_expr($1); 
     } 
     else { 
      $$ = make_list_starting_expr($1); 
     } 
     } 

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

expr: list_starting_expr 
    | list_ending_expr 
    | even_list_of_numbers 
    | odd_list_of_numbers 
list_starting_expr : complex_expression ',' NUMBER ',' NUMBER 
        | list_starting_expr ',' NUMBER ',' NUMBER 
list_ending_expr : NUMBER ',' complex_expression 
        | NUMBER ',' list_ending_expr 
odd_list_of_numbers : NUMBER 
        | NUMBER ',' NUMBER ',' odd_list_of_numbers 
even_list_of_numbers: NUMBER ',' NUMBER 
        | NUMBER ',' NUMBER ',' even_list_of_numbers 

Это может быть более значимым написать это как:

expr: expr_type_one | expr_type_two 
expr_type_one: list_starting_expr | even_list_of_numbers 
expr_type_two: list_ending_expr | odd_list_of_numbers 
/* Remainder as above */ 

Примечание: Вышеуказанные грамматики, как и грамматика в исходном вопросе, не позволяют expr состоять только из complex_expression. Если это было желательно, чтобы обработать случай только одного complex_expression, то, что синтаксис может быть добавлен непосредственно в спектаклях для expr (или какой из expr_type_one или expr_type_two были соответствующими.

Answer 2

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

expr : NUMBER 
    | expr ',' NUMBER 
    ; 

Теоретической земли можно найти там: https://cs.stackexchange.com/questions/9963/why-is-left-recursion-bad