В оптимизирующем компиляторе нередко возникает необходимость представить вычисления в символьном виде. Для этого используются PS-формы (PSF - Product-Summ Form), которые позволяют представить арифметическое выражение в виде суммы произведений. Пример PS-формы: 8 + x - 5y + 3xy где 'x' и 'y' - некоторые переменные. В PS-формах используется только три арифметических оператора: '+', '-' и '' Возведения в степень нет, вместо него используется многократное умножение, например xxx. Скобки не используются.
Мы будем рассматривать только PS-формы в каноническом виде, которые обладают следующими свойствами:
- константные множители в слагаемых могут находиться только в начале слагаемого; как следствие, в слагаемом может быть только один константный множитель;
- PS-форма не упрощается, т.е. в ней нельзя сократить какие-либо слагаемые; например: x + y -- канонический вид 2*x + y - x -- НЕ канонический вид (можно упростить до 'x + y')
За исключением указанного выше ограничения, порядок слагаемых и множителей внутри слагаемого не имеют значения. Например, следующие PS-формы: x + yz yz + x z*y + x эквивалентны.