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

Обратная польская запись (ОПЗ) или обратная польская строка предполагает запись языковых конструкций в следующем виде:

аргумент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.

6.3. Недостатки применения аппарата формальных грамматик

Модель формальных грамматик имеет два основных недостатка.

A) В естественном языке очень много понятий, следовательно, в грамматике будет очень много нетерминалов.

B) Доказано, что естественные языки относятся к классу 0 по Хомскому, следовательно, задача распознавания и генерации фраз естественного языка алгоритмически неразрешима.

Второе ограничение в принципе невозможно преодолеть.

Исследовательский опыт позволяет констатировать неэффективность применения формальных грамматик и связанных с ними моделей, таких как конечные и магазинные автоматы, ОПЗ, для анализа естественных языков.

Существует несколько приближенных моделей естественного языка, использующихся на практике. Например, модель непосредственных составляющих, модель синтаксического управления, модель глубинных или семантических падежей, модель расширенных сетей переходов. В последнее время все более широкое применение находит применение нейронных сетей.

Большая часть моделей основывается на принципах, установленных в семиотике – науке о знаковых системах, и прежде чем рассматривать конкретные модели, необходимо в общих чертах познакомиться с семиотикой.