От перепутья к перепутью, часть вторая: Разбор языка арифметики⁠⁠

Предыдущая статья: От перепутья к перепутью, часть первая: Порядковый разбор КС-языков методом рекурсивного спуска в vk.com

Г: В → ДС
С → ε | +ДС | -ДС
Д → РП
П → ε | *РП | /РП
Р → ч | (В)

Представляю вам грамматику языка арифметики, давайте построим рисунок порядка и обозначим понятиями все неконечные, ε - записываем так '' (между кавычками ничего нет):

Выражение → Дополнение Сумма
Сумма → '' | ''+' Дополнение Сумма | '-' Дополнение Сумма
Дополнение → Результат Произведение
Произведение →'' | '*' Результат Произведение | '/' Результат Произведение
Результат → Целое | '(' Выражение ')'

В качестве чисел у нас выступят только целые, уже нами рассмотренные. Поэтому мы их включим в наш рисунок:

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

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

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

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

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

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

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