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

       

Неоднозначные грамматики. Ассоциативность


Рассмотрим конфигурации, возникающие при анализе строки 1+2+3 .

Содержимое стека Необработанная часть входной цепочки Действие
$1+2+3Shift
$1+2+3Reduce [2]
$E+2+3Shift
$E+2+3Shift
$E+2+3

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

Таким образом, существуют ряд стандартных ситуаций, в которых возникают неоднозначные грамматики. Большая часть подобных ситуаций может быть решена преобразованием грамматик ("висящие" else , приоритет операций и т.д.), но не всегда это необходимо ("висящие" else ) и не всегда является лучшим решением. Существуют ситуации, когда подходящее преобразование грамматики не существует, в таких случаях необходимо привлекать дополнительные механизмы, как это сделано, например, для определения ассоциативности операций.



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