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

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

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

Метод рекурсивного спуска (англ. Recursive descent parser ) — алгоритм нисходящего синтаксического анализа, реализуемый путём взаимного вызова процедур, где каждая процедура соответствует одному из правил контекстно-свободной грамматики или БНФ. Применения правил последовательно, слева-направо поглощают токены, полученные от лексического анализатора. Это один из самых простых алгоритмов синтаксического анализа, подходящий для полностью ручной реализации.

Варианты реализации [ править | править код ]

Предсказывающий парсер [ править | править код ]

Для парсеров этого типа нужна подходящая КС-грамматика, конкретно LL(k) грамматика, позволяющая по очередному токену или токенам однозначно выбрать (предсказать) один из альтернативных вариантов раскрытия каждого нетерминала.

Такой парсер работает за линейное время.

Вариантом является LL-парсер — реализация предсказывающего парсера с автоматическим построением «таблицы предсказания», определяющей по заданному нетерминалу и очередному токену подходящее правило для раскрытия нетерминала.

Парсер с возвратом [ править | править код ]

Вместо предсказания парсер просто пытается применить все альтернативные варианты правил по порядку, пока одна из попыток не увенчается успехом.

Такой парсер может потребовать экспоненциального времени работы, и не всегда гарантирует завершение, в зависимости от грамматики. Уязвим для левой рекурсии.

Классы синтаксических анализаторов

Большинство известных методов анализа принадлежат одному из двух классов, один из которых объединяет нисходящие (top-down) алгоритмы, а другой – восходящие (bottom-up) алгоритмы. Происхождение этих терминов связано с тем, каким образом строятся узлы синтаксического дерева: либо от корня (аксиомы грамматики) к листьям (терминальным символам), либо от листьев к корню.

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

  • Они могут быть проанализированы без возвратов
  • Первая буква L означает, что мы просматриваем входную цепочку слева направо (left-to-right scan)
  • Вторая буква L означает, что строится левый вывод цепочки ( leftmost derivation).
Читайте также:  Скайп вход на свою страницу сразу

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

С другой стороны, восходящие анализаторы могут анализировать большее количество грамматик, чем нисходящие, и поэтому именно для таких методов существуют программы, которые умеют автоматически строить анализаторы. С восходящими анализаторами связаны LR -грамматики. В этом обозначении буква L по-прежнему означает, что входная цепочка просматривается слева направо (left-to-right scan ), а буква R означает, что строится правый вывод цепочки ( rightmost derivation ). С помощью LR -грамматик можно определить большинство использующихся в настоящее время языков программирования.

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

Одним из наиболее простых и потому одним из наиболее популярных методов нисходящего синтаксического анализа является метод рекурсивного спуска (recursive descent method) .

Для объяснения принципов, лежащих в основе метода рекурсивного спуска, рассмотрим задачу вычисления значения арифметической формулы. Будем рассматривать формулы, состоящие из целочисленных значений, бинарных операций сложения ( + ), вычитания ( ), умножения ( * ) и деления нацело ( / ), а также круглых скобок. Как обычно, приоритеты операций умножения и деления равны и их приоритет больше, чем приоритеты операций сложения и вычитания, причем приоритеты этих операций также равны. Будем называть операции + и операциями типа сложения, а операции * и / – операциями типа умножения. Круглые скобки используются для изменения стандартного порядка выполнения операций. Наша задача заключается в написании программы, вычисляющей значение формулы.

Изучаемые нами формулы можно представить следующим образом:

где Ti – это формула вида F1i *F2i *…*Fmi . В свою очередь , Fji – это либо число, либо произвольная формула, заключенная в круглые скобки.

Представим себе процесс вычисления значения формулы. Вначале вычисляется F11, далее мы выясняем, какая операция следует за F11 . Если это операция типа умножения, то мы, зная ее левый операнд , вычисляем правый операнд и выполняем операцию. Тем самым, мы получим левый операнд для возможных следующих операций типа умножения. Когда мы закончим вычисление формулы F1*F2*…*Fn , то, возможно, увидим далее операцию типа сложения, и процесс вычисления такой формулы будет аналогичен только что описанному процессу.

Читайте также:  При включении 3g пропадает сеть андроид

Вычисление значения формулы

Итак, мы можем разделить все формулы на следующие классы:

  • Простейшие формулы: числа и произвольные формулы, заключенные в круглые скобки, например, 354, (17+3-18)
  • Формулы, содержащие операции типа умножения, т.е. умножение и деление, например, 18*2*(35+2)*7
  • Формулы, содержащие операции типа сложения, т.е. сложение и вычитание, например, 18*2*(35+2)*7+354+ (17+3-18)*(12-7) .

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

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

Опишем процедуру, вычисляющую значение простейшей формулы:

Доброго времени суток, уважаемые Хабровчане!

Хочу поделится с вами реализацией алгоритма «Метод рекурсивного спуска» на примере написания парсера формул с поддержкой переменных и функций на языке Java

Эта статья в (скорее всего, во всяком случае я надеюсь 🙂 ) будет интересна для новичков, или кому-то применить как фундамент для своего решения данной задачи.
Кому интересно — прошу под кат

Разработать парсер формул который:

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

Вступление

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

Также имеет значение приоритет подзадачи. Меняя приоритет подзадачи поменяется и поведение парсера.
Поскольку мы будем реализовывать парсер математических формул, то для расставления приоритетов мы будем руководствоваться приоритетами математических операций:

  1. функция и переменная
  2. скобки
  3. умножение и деление
  4. сложение и вычитание
Читайте также:  Почему плохо заводится ваз 2109 карбюратор

Полетели

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

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

Из метода который осуществляет сложение/вычитание мы будем вызывать умножение/деление и так далее

Для общего понимания, немного упростим задачу, сделаем парсер, который лишь выполняет операции сложения и вычитания:

Выведет нам:
PlusMinus: 10.0

В данном парсере мной было реализованы следующие функции (расширить этот список своими функциями можно добавив соответствующее условие в processFunction ):

  • sin
  • cos
  • tan

Над обработкой ошибок я особо не заморачивался (что бы не засорять «полезный» код), а то в итоге кода по обработке ошибок может быть больше чем кода для самого парсера 🙂

Вот полный листиннг класса без упрощения:

Выведет:
2+2*2=6.0
2+X*2=6.0
sin(90)+4-cos(0)=4.0
2–4=6.0
Error while parsing ‘2**3*5—–7’ with message: can’t get valid number in ‘*3*5—–7’
Error while parsing ‘3.5.6-2’ with message: not valid number ‘3.5.’

Скачать весь проект можно тут ( спасибо flexoid за подсказку, куда можно сохранить архив)
Спасибо за внимание!

Leave a Reply

Ваш адрес email не будет опубликован. Обязательные поля помечены *

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>