Понятие «синтаксический анализ» присутствует во многих сферах человеческой
жизнедеятельности. Но нас интересует, что такое «синтаксический анализ» в
программировании?
Синтаксический анализ — это процесс, при котором проверяется входная
последовательность символов для того, чтобы разобрать их грамматическую
структуру. Данный процесс осуществляется специальной программой —
синтаксическим анализатором (он же «парсер»).
Синтаксический анализ в программировании: методы
Есть множество методов, чтобы провести синтаксический анализ. Но все они
сводятся к двум основным классам:
- Нисходящий класс — это когда анализ проводится от «корня» к листьям
синтаксического дерева. - Восходящий класс — это когда анализ проводится от «листьев» к «корню»
синтаксического дерева.
Наиболее популярным является нисходящий класс анализаторов, так как такие
анализаторы легко построить вручную. Самым популярным методом нисходящего
класса является метод рекурсивного спуска.
С другой стороны восходящие анализаторы считаются более эффективными, так как
способны проанализировать большое количество различных грамматик.
Если на примере разобрать разницу между нисходящими и восходящими
анализаторами, то получим следующее:
- Нисходящий анализатор начинает проверять предложение, корректно
разбивая его на слова. - Восходящий анализатор начинает проверять слова, корректно составляя из
них предложение.
Синтаксический анализ методом рекурсивного спуска
Этот нисходящий метод синтаксического анализа является самым популярным из-за
своей простоты и легкой реализации. Синтаксический анализатор методом
рекурсивного спуска выстраивается набором отдельных функций, каждая из которых
нужна для исследования отдельного символа языка, обозначенного в грамматике.
Таким анализаторам свойственны следующие принципы:
- производится последовательный перебор символов входной строки, начиная слева строки;
- каждый символ — это основание, чтобы выбрать подходящее к нему правило из группы правил;
- присутствует «взаимное уничтожение» символов входной строки и соответствующих символов из правил «правой» части;
- для каждой группы правил создается собственная функция;
- реализован процесс «процедура-распознаватель», когда сравниваются ожидаемый символ из правой части и символ входной строки;
- когда символ из правой части полностью совпадает с символом входной строки, то символ входной строки игнорируется и функция переходит к другому символу из правой части;
- когда нет совпадения между терминальным символом и очередным символом входной строки — такая ситуация трактуется как синтаксическая ошибка;
- когда в правой части возникает нетерминальный символ, то для его распознавания нужно создать соответствующую функцию.
Нисходящий синтаксический анализатор методом рекурсивного спуска имеет
следующий общий вид:
class Parser
{
//указываем массив для входа и начала анализа
Lexem* inputLexems;
//указываем текущую позицию
Lexem* inputPtr;
void parseExpr();
void parseItem();
void parseFactor();
public:
Parser (Lexem* input);
void parse();
};
Подобные анализаторы могут быть использованы для синтаксического анализа
различных выражений, начиная от простых текстовых предложения и заканчивая
сложными математическими формулами. Вышеуказанный парсер — это пример на
языке С или С++ для математического выражения.
Синтаксические анализаторы(они же парсеры) могут принимать различную форму,
которая зависит от поставленной задачи и языка программирования, на котором они
организуются.
Возможно вам будет интересно почитать статью “jQuery: что это такое?“
Иногда лень писать подобные парсеры, чтобы провести синтаксический анализ
методом рекурсивного спуска. Чтобы облегчить и эту задачу, есть генераторы
парсеров рекурсивного спуска, наиболее известные из них:
- TMG;
- Java CC;
- Coco/R;
- ANTLR;
- Spirit Parser Framework;
- parboiled (Java);
- и др.
