Разработка компиляторов
Неоднозначные грамматики. Ассоциативность
Рассмотрим конфигурации, возникающие при анализе строки 1+2+3 .
| $ | 1+2+3 | Shift |
| $1 | +2+3 | Reduce [2] |
| $E | +2+3 | Shift |
| $E+ | 2+3 | Shift |
| $E+2 | +3 |
После последнего шага возникает конфликт перенос-свертка. Выбор переноса делает сложение правоассоциативным, выпор свертки - левоассоциативным. Так как левоассоциативное сложение более естественно, свертка предпочтительна. В данном случае не существует эквивалентной однозначной грамматики. Формализма грамматик не хватает для описания данной ситуации и необходимы дополнительные средства.
Таким образом, существуют ряд стандартных ситуаций, в которых возникают неоднозначные грамматики. Большая часть подобных ситуаций может быть решена преобразованием грамматик ("висящие" else , приоритет операций и т.д.), но не всегда это необходимо ("висящие" else ) и не всегда является лучшим решением. Существуют ситуации, когда подходящее преобразование грамматики не существует, в таких случаях необходимо привлекать дополнительные механизмы, как это сделано, например, для определения ассоциативности операций.
