3.3 Распознаватель

На верхнем уровне выражения распознаются функцией sum(), которая внутри делает вызов scan() и возвращает представление, которое может обработано process() и утилизировано delete().

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

sum : product { +|- product }...

преобразуется в такую функцию C

void sum (void)

{

    product();

    for (;;) {

        switch (token) {

        case ’+’:

        case ’-’:

            scan(0), product(); continue;

        }

        return;

    }

}

Для каждого грамматического правила существует функция C, так что правила могут вызывать друг друга. Альтернативы переведены в операторы switch или if, итерации в грамматике порождают циклы в C. Единственная проблема заключается в том, что надо избежать бесконечной рекурсии.

token всегда содержит следующий входной символ. Если он распознан, для продвижения дальше надо вызвать scan(0)  и сохранить новый символ в token.