15.1.1 Метод рекурсивного спуска

Язык арифметических выражений достаточно прост и практически всем понятно, как записывать эти выражения. Арифметические выражения строятся из идентификаторов, констант, знаков операций и скобок, кроме того можно записывать еще и некоторый функции, например, корень квадратный, sin, cos и т.д.
Примеры арифметических выражений:
1. x+1/(10+y)
2. c+sin(a*x+2)
3. (count+1)*(count-1)
Грамматика языка арифметических выражений записана ниже.
<E> = <T> + <E>
<E> = <T> - <E>
<E> = <T>
———-
<T> =<D> * <E>
<T> =<D>/<E>
<T> =<D>
———–
<D> = (<E>)
<E> = <идентификатор>
<D> = <константа>
Идентификатор - последовательность букв и цифр, начинающаяся с буквы.
Константа - вещественное число.

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

Рассмотрим работу метода рекурсивного спуска на примере. Пусть есть входная строка x+10*(a+1). Первоначально начинает работу функция РазборE, она вызывает функцию РазборT (строка 2). Функция РазборT вызывает РазборD (строка 12). Функция РазборD проверяет на входе открывающую скобку, на входе символ "x"- это буква, значит следует идентификатор (см. строка 24). Функция РазборD берет идентификатор x и сдвигает вход на следующий символ. После вызова функции РазборD управление возвращается на строку 22 функции РазборТ. На входе при этом стоит символ "+", поэтому происходит выход из цикла и возврат в функцию РазборE на выполнение строки 3. Входим в цикл, проверяем на входе "+", да - сдвигаем вход на следующий символ ("1") и вызываем снова функцию РазборТ. Та в свою, очередь вызывает РазборD, которая забирает из входной строки константу "10", сдвигает вход (на входе будет символ "*") и возвращает управление в функцию РазборТ в строку 13, где записан цикл, входим в цикл и проверяем на знак умножить. Да, совпало, сдвигаем вход (на входе будет символ ")") и вызываем функцию РазборD. Проверяем на входе: стоит скобка открывающая - да, совпало, сдвигаем вход и вызываем функцию РазборE (вот она рекурсия, функция РазборE вызывается второй раз) . Функция РазборE совместно с функциями РазборТ и РазборD производит разбор выражения в скобках, после завершения последнего вызова функции РазборE на входе будет закрывающая скобка и управление будет передано в строку 22, сразу после вызова РазборE, где ожидается закрывающая скобка. Далее производится сдвиг и возврат в функцию РазборТ, откуда возврат в функцию РазборE в строку 04, поскольку на входе больше ничего нет, функция РазборE завершает работу.

Таблица 15.1
01	Функция РазборE()
02	вызвать РазборT()
03	цикл
04	если на входе "+", то сдвиг и вызвать РазборT()
05	иначе
06	если на входе "-", то сдвиг и вызвать РазборT()
07	иначе выход из цикла
08	конец цикла
09	конец функции РазборE
10
11	Функция РазборT()
12	вызвать РазборD()
13	цикл
14	если на входе "*" , то сдвиг и вызвать РазборD()
15	иначе
16	если на входе "/", то сдвиг и вызвать РазборD()
17	иначе выход из цикла
18	конец цикла
19	конец функции РазборT
20
21	Функция РазборD()
22	если на входе "(" , то сдвиг и вызвать РазборЕ(), ждать " )"
23	иначе
24	если на входе буква, то взять идентификатор
25	иначе
26	если на входе цифра, то взять константу
27	иначе выдать ошибку, сдвиг входа
28	иначе выдать ошибку, сдвиг входа 29 конец функции РазборD