Mathos

Префиксная и постфиксная запись также именуются прямая и обратная польская нотация (далее ОПН), в честь её изобретателя польского логика Яна Лукасевича. Отличительная их черта, то что в них не используются скобки для обособления вычисления.

Получение ОПН из инфиксной записи

Используем рекурсивный спуск по рассмотренной нами грамматике, где в качестве чисел целые без знака:

Грамматика с унарным минусом и плюсом:
Г: В -> ДС
С -> ε | +ДС | -ДС
Д -> РП | -Д | +Д
П -> ε | *РП | /РП
Р -> ч | (В)

Звенья цепочки ОПН опишем набором трёх типов:
1. Операнд - целые числа.
2. Одноместный оператор - однооп, это унарный минус и плюс.
3. Двуместный оператор - двуоп, это минус, плюс, умножить, делить.

Ниже представлено полное описание звена ОПН:

Соберём звенья в список, который будет представлять нашу ОПН. Для этого отметим 3 действия на отделах рисунка порядка:
Д1 - Создать хрон. Переменная хранящая звено до момента добавления в список.
Д2 - Запомнить. Помещаем встреченное звено в хрон.
Д3 - Добавить. Записываем в список ОПН.

Ниже показаны отделы и процедуры со встроенными действиями в разбор:

Так мы добавляем в первую очередь операнды, затем операторы в порядке их приоритетов. Всмотритесь в процедуру «Дополнениее». В качестве хрона используется стог (англ. stack), так как запоминаются несколько знаков сразу, их следует вспомнить в обратном порядке.

Осмыслим следующее: рекурсивный разборщик выступает теперь не только в качестве распознавателя, но и переводчика. Ведь мы получили цепочку принадлежащую другому формальному языку, который можно описать так:

Грамматика обратной польской нотации:
Г:В -> ч | П`П
П`-> чПО
П -> ВОП | ε

где:

В - ВЫРАЖЕНИЕ
О - ОПЕРАТОР
П - ПРАВОЕ_ПОДВЫРАЖЕНИЕ
П`- ПОДВЫРАЖЕНИЕ
ч - ЧИСЛО

Остановитесь на минутку, осмыслите.

Вычисление ОПН

Ниже изображена схема устройства вычисления ОПН - Стог-машина (Stack machine), а на следующем её описание. Для примера использована ОПН:

1 2 3 * + 4 -

Которая получена из инфиксной записи:

1 + 2 * 3 - 4

Стог-машина состоит из:

1. Стога - в котором хранятся промежуточные значения.

2. Набора двухместных и одноместных операций.

3. Движка - который читает ОПН, управляет стогом и обращается к набору операций.

ОПН обладает свойством: действия применяются последовательно при её чтении, на чём и основана работа стог-машины:

1. Если звено операнд, то кладём число в стог.

2. Если звено однооп, снимаем верхнее число обрабатываем, итог кладём в стог.

3. Если звено двуоп, снимаем два верхних числа и применяем операцию. Причём первое значение операции - второе верхнее, а второе - первое верхнее. Итог кладём в стог.

4. По окончанию чтения ОПН, итог вычисления оказывается на дне стога, одним.

В заключении

Не стоит думать, что рассмотренный способ единственный для получения ОПН. Есть так же алгоритм Дейкстры перевода выражения в ОПН, но я не знаю стоит ли его разобрать или сразу перейти к обсуждению включения действий в «Провидца», ранее нами рассматриваемого.

Поэтому решение будет зависить от вас:

Ну на это всё, быть добру, хорошего настроения. Подписывайся. =)
Точно! Для любознательных и внимательных читателей, ещё одна не позиционная система счисления.

LL-грамматика

LL(k)-грамматикой называется КС-грамматика, в которой выбор правила в ходе левостороннего разбора однозначно определяется не более чем k очередным символом входной цепочки, считываемой слева на право.

Своё название она получила из двух слова left left. что имеется ввиду левосторонее чтение, левостороний разбор.

Самой удобной для распознавания является грамматика которая позваляет опередлить правило по первому прочтённому символу, то есть LL(1)-грамматика.

Под рекурсивным спуском обычно подразумевают, предопределённый способ нисходящего разбора КС-языков, порождаемых ЛЛ(1)-грамматиками.

ЛЛ-грамматика праворекурсивна и множества направляющих символов в её правилах не пересекаются, что соответствует вышеуказанным требованиям.

Заключение

Эти правила касаются только лишь для метода рекурсивного спуска и ЛЛ-разбора по табелю (табличный анализатор), который рассмотрим в следующих статьях.

Заметим, что в понятиях «Сумма» и «Произведение» у нас имеется правая рекурсия. Поэтому следует заменить рекурсию на циклы, но ещё видим, что после конечных у нас рассматриваются одноименные понятия, посему объединим в один общий цикл, где кон будет сверяться со множеством:

Рисунок готов, теперь мы можем приступить к описанию процедур:

Конечно у нас есть несколько допущений: 1. Алгоритм рассматривает строки без пробелов, думаю не сложно реализовать их пропуск на вашем любимом языке. 2.Понятие «Сумма» включает в себя вычитание, а «Произведение» деление, надеюсь читатель простит мне это допущение, так как можно представить вычитание и деление в виде их обратных операций. 3. Процедура «Результат», так как отдел рисунка порядка ветвится только на две ветви, я не стал проверять соответствует ли кон символам маякам, коими являются {+, -, цифра}.

Хорошо когда есть готовая и верная грамматика, для рекурсивного спуска по ней достаточно легко написать распознаватель. Какими она должна обладать свойствами? Об этом мы поговорим в следующий раз и вы поймете почему грамматика G(см.ниже) не подходит, хотя она и однозначна и даёт верное семантическое дерево:

G:
E → T | E + T | E – T
T → M|T * M| T / M
M → x | (E)

Послесловие: Сегодня хороший день, сегодня мы разобрались со скобочками. Не так уж это и сложно. Подписывайся. =)

Грамматика с унарным минусом и плюсом:
Г: В → ДС
С → ε | +ДС | -ДС
Д → РП | -Д | +Д
П → ε | *РП | /РП
Р → ч | (В)

Первой вызывается процедура стартового понятия, то есть стартового неконечного символа грамматики. Первый кон - первый символ входящей цепочки. По окончанию процедуры поток символов должен быть завершён. Общий вид можно описать так:

Название «рекурсивный спуск» исходит из того, что при наличии самовложения в грамматике вызовы процедур будут рекурсивными. Распознавание начинается со стартового неконечного, поэтому разбор нисходящий.

На прошлом уроке мы рассматривали рисунок порядка, так вот каждый его отдел представляет из себя схему алгоритма отдельной процедуры. Ниже в таблице участки отдела обозначены: У, У₁, У₂, …, Уₙ. Их соответствующие фрагменты процедуры: Ф(У), Ф(У₁), Ф(У₂), … Ф(Уₙ), будем считать что они вынесены в свои процедуры:

Принцип анализа по схемам отделов состоит в том, что сверяя очередной символ с маяком (см. пояснение п.4), мы выбираем путь как дальше будут сверятся символы распознаваемой цепочки.

В следующей статье мы рассмотрим разбор арифметических выражений.

З. Ы. Минутка этимологии: Слово процедура происходит от лат. procedere, которое состоит из pro и cedere. Сedere значит «идти» или «двигаться», pro - «вперёд», от сюда procedere - продвигаться, проходить. Слово рекурсия происходит от лат. recursio, re - указывает на повторность действия, так же как «пере», cursio однокоренное с cursus - курс, путь, то есть recursio - это перепутье, только в том узком смысле, что пересечение дороги ведёт к той же дороге.
Не забудь подписаться.