Обратная польская запись

Обратная польская запись (ОПЗ) или обратная польская строка предполагает запись языковых конструкций в следующем виде:
аргумент1 аргумент2 аргументn операция.
Например, выражение a+b записывается, как ab+, а выражение d+b*c+q – как dbc*+q+.
Используя этот прием, можно записывать и более сложные конструкции. Например, в процессе построения интерпретаторов и компиляторов в ОПЗ записываются в том числе и конструкции безусловного и условного переходов, а также циклические конструкции.
Этот прием можно применить и для формализации записи на естественном зыке, например фразу «автомобиль движется к городу» можно записать так
«автомобиль город двигаться к»,
фразу «автомобиль марки Нива движется к городу Томску», как
«автомобиль Нива марка город Томск имя двигаться к».
При этом каждое отношение должно иметь фиксированное число аргументов (в данном примере по два аргумента в каждом отношении).
К преимуществам ОПЗ можно отнести наличие стандартного алгоритма ее генерации при анализе языковых конструкций (как правило, КС-грамматик). Основное применение данная модель находит при решении задачи трансляции с языков высокого уровня, так как, помимо отмеченного преимущества, ОПЗ легко интерпретируема с помощью СТЕКа. Для этого просматриваем цепочку слева направо, помещая аргументы в, а как встречается символ операции – выполняем данную операцию и заменяем ее аргументы в СТЕКе на полученное значение.
Пример. dbc*+q+.
d→ CТЕК, b→ СТЕК, с-→ CТЕК;
таким образом, в стеке имеем dbc;
* – заменяем два верхних элемента в стеке на b*c;
если b*c=k, то в СТЕКе получаем dk;
+ – заменяем два верхних элемента в СТЕКе на d+k;
если d+k=p, то в СТЕКе получаем p;
q→ СТЕК;
в стеке имеем pq;
+ – заменяем два верхних элемента в стеке на p+q;
если p+q=s, то в СТЕКе имеем s.
Таким образом, в стеке имеем результат.
В тоже время для анализа естественных зыков модель все же неудобна по причинам, изложенным в 6.3.