Разработка компиляторов
Грамматики восходящего переписывания
Поскольку системы команд предоставляют большое разнообразие способов вычислений, ожидается, что практически любая грамматика будет неоднозначной. Однако небольшой модификацией этих неоднозначностей можно избежать.
Именно, снабдим каждое правило стоимостью и определим стоимость вывода как сумму стоимостей правил, входящих в его состав. Далее среди всех выводов нас будут интересовать только те, которые имеют наименьшую стоимость. Кроме того, будем считать, что выводы наименьшей стоимости для нас неразличимы, то есть нам совершенно все равно, какой из них выбрать. Таким образом грамматика становится однозначной с точностью до вывода минимальной стоимости.
Неформально говоря, каждое правило описывает либо машинную команду, либо ее операнд. Стоимость при этом отображает некоторое представление о сложности команды или операнда.
