Разработка компиляторов

       

Неоднозначные грамматики. Конфликт перенос-перенос


Второй тип конфликта, который может возникнуть, это так называемый конфликт перенос-перенос ( 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 . Но в этом случае, чтобы вернуть правильный лексический класс, лексический анализатор должен выполнить сложную работу по определению, является ли данный идентификатор обозначением процедуры или массива.



Содержание раздела