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

       

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


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



Содержание  Назад  Вперед







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий