Basic Concepts

Boost , ,

Basic Concepts

Есть несколько основных понятий, которые необходимо хорошо понять: 1)Парсер, 2)Матч, 3)Сканери 4Семантические действия. Эти основные понятия взаимодействуют друг с другом, и функциональные возможности каждого переплетаются по всей структуре, чтобы сделать его одним целостным.

The Parser

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

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

Клиентам фреймворка вообще не нужно писать собственные парсеры с ручным кодированием. Spirit имеет огромный репертуар предварительно определенных парсеров, охватывающих все аспекты синтаксиса и семантического анализа. Мы рассмотрим этот репертуар парсеров в следующих разделах. В редких случаях, когда конкретная функциональность недоступна, очень легко написать пользовательский парсер. Легкость в написании сущности парсера является основной причиной расширяемости Духа.

Primitives and Composites

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

    real_p >> *(',' >> real_p)

real_p— примитивный парсер, который может разбирать реальные числа. Процитированная запятая,в выражении является ярлыком и эквивалентнаch_p',', который является еще одним примитивным парсером, который распознает одиночные символы.

Выражение выше соответствует следующему дереву:

Выражение:

    ',' >> real_p

,, [скрыто], [скрыто]. Последовательностьпарсера представляет собой составной парсер, содержащий два парсера: один на левой стороне (lhs),ch_p',; и другой на правой стороне (rhs),real_p. Этот составной парсер при вызове последовательно называет свои lhs и rhs и сообщает об успешном матче, только если оба успешны.

Парсерпоследовательностипредставляет собой двоичный композит. Состоит из двух парсеров. Существуют также унарные композиты. Унарные композиты содержат только один предмет. Как и бинарный композит, унарный композит может изменить поведение встроенного субъекта. Одним из таких примеров является. Звезда Клин. Звезда Клин, когда ее призывают к разбору, называет свой единственный объект нулем или более раз. «Ноль или больше» означает, что звезда Клин всегда возвращает успешный матч, возможно, соответствующий нулевой струне: «.

Выражение:

    *(',' >> real_p)

Обертывает всю последовательность композита выше внутриkleene_star.

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

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

Нисходящий спуск пересекает иерархию. Внешняяпоследовательностьназывает самый левыйreal_pпарсером. В случае успехаклен_звезданазывается следующей.kleene_starвызывает внутреннююпоследовательностьмногократно в петле, пока она не не совпадет, или вход исчерпан. Внутриch_p(',')и затемreal_pназываются последовательно. Следующая диаграмма иллюстрирует происходящее, несколько напоминающее синтаксические диаграммы Паскаля.

Гибкость объектного встраивания и композиции в сочетании с рекурсией открывает уникальный подход к разбору. Подклассы могут свободно формировать агрегаты и алгоритмы произвольной сложности. Сложные парсеры могут быть созданы с составом лишь нескольких примитивных классов.

Рамки предназначены для того, чтобы быть полностью открытыми и расширяемыми. Новые примитивы или композиты, от тривиальных до сложных, могут быть добавлены в любое время. Композиция происходит (статически) во время компиляции. Это возможно благодаря выразительной гибкости шаблонов экспрессии C++ и метапрограммирования шаблонов.

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

The Scanner

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

Знание тонкостей этих политик в большинстве случаев не требуется. Однако знание базового API сканера необходимо для написания полностью соответствующих парсеров Spirit. API сканера будет описан в отдельном разделе. Кроме того, для опытных пользователей и любителей приключений среди нас полный раздел будет посвящен политике сканирования. Политика сканера делает Spirit очень гибким и расширяемым. Например, некоторые политики могут быть изменены для фильтрации данных. Практическим примером является политика сканера, которая не различает верхний и нижний регистры, что делает его полезным для разбора нечувствительных входных данных. Другим примером является политика сканера, которая удаляет белые пространства от входа.

The Match

Парсер имеет концептуальную функцию члена разбора, которая принимает сканер и возвращает объект соответствия. Основная функция объекта соответствия состоит в том, чтобы сообщить об анализе успеха (или неудачи) обратно вызывающему парсеру; то есть, он оценивает истинность, если функция анализа успешна, ложна в противном случае. Если разборка успешна, объект совпадения также может быть запрошен, чтобы сообщить количество совпадающих символов (с использованиемmatch.length()).. Длина неотрицательна, если матч удался, а типичная длина неудачного разбора -1. Нулевая длина вполне верна и по-прежнему представляет собой успешный матч.

У парсеров могут быть атрибутные данные, связанные с ним. Например, парсер real_p имеет связанное с ним числовое значение. Этим атрибутом является парсинговое число. Этот атрибут передается возвращенному объекту матча. Объект матча может быть запрошен, чтобы получить этот атрибут. Данное условие действует только тогда, когда матч проходит успешно.

Semantic Actions

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

Вспомните наш пример выше:

    real_p >> *(',' >> real_p)

При подключении функции (или функтора) к парсерам real_p мы можем извлечь числа из ввода:

    real_p[&f] >> *(',' >> real_p[&f])

гдеf— функция, которая принимает в одном аргументе.[&fзацепляет парсер с функцией так, что когдаreal_pраспознает действительное число, функцияfназывается. Затем функция должна делать то, что уместно. Например, он может вставлять числа в вектор. Или, может быть, если немного изменить грамматику, заменив',на'+', то у нас есть примитивный калькулятор, который вычисляет суммы. После этого функцияfможет быть выполнена для добавления всех входящих чисел.

Copyright © 1998-2003 Joel de Guzman

Use, modification and distribution is subject to the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

Статья Basic Concepts раздела может быть полезна для разработчиков на c++ и boost.

:: Главная :: ::