Очевидно, что следующее неоднозначна:
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
были соответствующими.
То есть не хватает информации. Вам нужно по крайней мере, показ работ, участвующих в конфликте. – rici
@rici существует более 500 правил. Я написал только те, которые связаны с вышеперечисленными терминалами. Таким образом: 'expr: NUMBER | NUMBER ',' expr | expr ',' NUMBER ',' NUMBER' –
Это очень отличается от вашего вопроса или вашего предыдущего комментария. Если это действительно часть вашей грамматики, то это причина конфликта. Предлагаю вам отредактировать свой вопрос, так что это можно ответить. – rici