Синтаксический анализатор методом рекурсивного спуска. Что это такое?

Понятие «синтаксический анализ» присутствует во многих сферах человеческой жизнедеятельности. Но нас интересует, что такое «синтаксический анализ» в программировании?

Синтаксический анализ — это процесс, при котором проверяется входная последовательность символов, для того чтобы разобрать их грамматическую структуру. Данный процесс осуществляется специальной программой — синтаксическим анализатором (он же «парсер»).

 

Синтаксический анализ в программировании: методы

Есть множество методов, чтобы провести синтаксический анализ. Но все они сводятся к двум основным классам:

  1. Нисходящий класс — это когда анализ проводится от «корня» к «листьям» синтаксического дерева.

  2. Восходящий класс — это когда анализ проводится от «листьев» к «корню» синтаксического дерева.

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

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

Если на примере разобрать разницу между нисходящими и восходящими анализаторами, то получим следующее:

  1. Нисходящий анализатор начинает проверять предложение, корректно разбивая его на слова.

  2. Восходящий анализатор начинает проверять слова, корректно составляя из них предложение.

 

Синтаксический анализ методом рекурсивного спуска

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

Таким анализаторам свойственны следующие принципы:

  • производится последовательный перебор символов входной строки, начиная с левой части строки;

  • каждый символ — это основание, чтобы выбрать подходящее к нему правило из группы правил;

  • присутствует «взаимное уничтожение» символов входной строки и соответствующих символов из правил «правой» части;

  • для каждой группы правил создается собственная функция;

  • реализован процесс «процедура-распознаватель», когда сравниваются ожидаемый символ из правой части и символ входной строки;

  • когда символ из правой части полностью совпадает с символом входной строки, то символ входной строки игнорируется и функция переходит к другому символу из правой части;

  • когда нет совпадения между терминальным символом и очередным символом входной строки — такая ситуация трактуется как синтаксическая ошибка;

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

Нисходящий синтаксический анализатор методом рекурсивного спуска имеет следующий общий вид: 

class Parser

{

    //указываем массив для входа и начала анализа 

    Lexem* inputLexems;

    //указываем текущую позицию

    Lexem* inputPtr;

    void parseExpr();

    void parseItem();

    void parseFactor();

public:

    Parser (Lexem* input);

    void parse();

} ;

 

Подобные анализаторы могут быть использованы для синтаксического анализа различных выражений, начиная от простых текстовых предложений и заканчивая сложными математическими формулами. Вышеуказанный парсер — это пример на языке С или С++ для математического выражения. 

Синтаксические анализаторы (они же парсеры) могут принимать различную форму, которая зависит от поставленной задачи и языка программирования, на котором они организуются.

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

  • TMG;

  • Java CC;

  • Coco/R;

  • ANTLR;

  • Spirit Parser Framework;

  • parboiled (Java); 

  • и др.