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

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

В правилах вывода неконечные символы по своей сути являются некоторыми языковыми понятиями. Условимся что конечные символы записываются в ' (одинарные кавычки), неконечные курсивом, тогда язык целых чисел мы можем записать так:

В дальнейшем изложении термин понятие будет тождественен неконечному символу. Приступи к описанию метода рекурсивного спуска:

1. Для каждого понятия создаётся отдельная распознающая процедура.

2. До начала работы процедуры текущим является первый символ разбираемого понятия, назовём его кон (сокр. от конечный и от смыслов «партия в игре», «черта», «граница»).

3. Исполняя процедуру считываем входящие символы относящиеся к понятию, либо говорим об ошибке. Если понятие содержит в себе другие понятия, то вызываем их процедуры.

4. По завершению процедуры коном становится первый символ выходящий за рамки понятия.

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

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

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

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

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

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