Разработка компиляторов
Неоднозначные грамматики. Конфликт перенос-перенос
Второй тип конфликта, который может возникнуть, это так называемый конфликт перенос-перенос ( reduce/reduce ), который возникает, когда на вершине стека анализатора возникает строка терминалов, к которой может быть применена свертка по двум различным правилам.
Пример. Рассмотрим грамматику G 2 ('id', '(', ')', '=' и ',' - терминалы) .
| (1) | stmt | -> | id (parameters_list) |
| (2) | stmt | -> | expr = expr |
| (3) | parameter_list | -> | parameter_list, parameter |
| (4) | parameter_list | -> | Parameter |
| (5) | parameter | -> | Id |
| (6) | expr | -> | id (expr_list) |
| (7) | expr | -> | Id |
| (8) | expr_list | -> | expr_list, expr |
| (9) | expr_list | -> | Expr |
В процессе разбора входной цепочки id (id, id) происходит следующее:
| $ | id (id, id) | shift |
| $ id | (id, id) | shift |
| $ id ( | id, id) | shift |
| $ id (id | , id) | shift |
Очевидно, что после выполнения последнего шага необходимо произвести свертку находящегося на вершине стека терминала id . Но какое правило использовать? Если использовать правило (5), то будет получен вызов процедуры, если использовать правило (7), то получится вырезка из массива. Чтобы избежать неоднозначности, в первом правиле можно заменить терминал id на другой терминал, например, procid . Но в этом случае, чтобы вернуть правильный лексический класс, лексический анализатор должен выполнить сложную работу по определению, является ли данный идентификатор обозначением процедуры или массива.
