Виртуальные функции: От статического к динамическому C++
Правила пересекают границу между статичным и динамическим C++. По сути, правило трансформирует полиморфизм времени компиляции (используя шаблоны) в полиморфизм времени выполнения (используя виртуальные функции). Это необходимо из-за неспособности C++ автоматически объявить переменную типа, выведенную из произвольно сложного выражения в правой стороне (rhs) задания. В принципе, мы хотим сделать что-то вроде:
T rule = an_arbitrarily_complex_expression;
без необходимости знать или заботиться о результирующем типе правой стороны выражения назначения. Кроме того, нам также нужен объект для декларирования неизвестного типа:
T rule;
...
rule = a | b;
Эти ограничения ведут нас к реализации правил. Это происходит за счет накладных расходов на вызов виртуальной функции, один раз за счет каждого вызова правила.
Многократная декларация
Некоторые варианты BNF допускают несколько деклараций правила. Заявления принимаются в качестве альтернативы. Пример:
r = a;
r = b;
эквивалентны:
r = a | b;
Дух 1.3 допускает такое поведение. Однако нынешняя версия Духабольше не допускает этого, потому что опыт показывает, что такое поведение приводит к нежелательным готчам (например, оно не позволяет держать правила в контейнерах). При нынешнем освобождении Духа второе назначение правилу просто переопределит его. Старое определение разрушается. Это следует за семантикой C++ и больше соответствует тому, что пользователь ожидает от правила.
Синтаксис секвенирования
Оператор запятой как в a, b кажется лучшим кандидатом, синтаксисом. Но проблема заключается в его приоритете. Он имеет самый низкий приоритет в C/C++, что делает его практически бесполезным.
Бьярн Страуструп в своей статье"Обобщение перегрузки для C++2000"говорит о перегрузке белого пространства. Такая функция позволила бы сопоставлять парсерные объекты точно так же, как мы делаем в (E)BNF (например, a b | c вместо a >>b | c). К сожалению, статья датирована 1 апреля 1998 года. Хорошо.
Передовые итераторы
В целом, сканер ожидает, по крайней мере, стандартный соответствующий передний итератор. Форвардные итераторы необходимы для обратного отсчета, где итератор должен быть сохранен и восстановлен позже. Вообще говоря, Spirit является парсером обратного пути. Смысл этого заключается в том, что в какой-то момент положение итератора должно быть сохранено, чтобы позволить парсеру вернуться к предыдущей точке. Таким образом, для возврата к работе фреймворк требует, по крайней мере, переднего итератора.
Некоторым парсерам могут потребоваться более специализированные итераторы (двунаправленный или даже случайный доступ). Возможно, в будущем детерминированные парсеры при добавлении в фреймворк не будут выполнять обратную связь и потребуют только один токен, следовательно, потребуют только итераторы ввода.
Почему субстандарты важны?
Подправила также открывают возможность агрессивного метапрограммирования, поскольку они не зависят от виртуальных функций. Виртуальная функция — это ад метапрограммиста. Он не только замедляет работу программы из-за непрямого вызова виртуальной функции, но и является непрозрачной стеной, через которую не может пройти ни одна метапрограмма. Он убивает всю метаинформацию за пределами вызова виртуальной функции. Хуже того, виртуальная функция не может быть создана. Это означает, что его аргументы должны быть привязаны к реальным типам. Многие проблемы связаны с этим ограничением.
В то время как Spirit в настоящее время классифицируется как недетерминированный парсер рекурсивного спуска, Дуг Грегор впервые отметил, что могут применяться другие методы анализа, кроме рекурсивного спуска сверху вниз. Например, помимо недетерминированного рекурсивного спуска, детерминированные LL(1) и LR(1) теоретически могут быть реализованы с использованием одного и того же шаблона выражения передней части. Правила Spirit используют виртуальные функции для кодирования RHS-парсера в непрозрачном абстрактном парсере. Хотя он хорошо служит своей цели, виртуальные функции правила являются камнем преткновения для более продвинутого метапрограммирования. Подправила свободны от виртуальных функций.
Исчерпывающее отступление и жадность РД
Дух не делает исчерпывающее отступление, как ожидают регулярные выражения. Например:
*chlit_p('a') >> chlit_p('a');
Звезда Духа Клин не отступает, когда остальные правила не совпадают.
На самом деле, есть решение этой жадной проблемы РД. Такая схема обсуждается в разделе 6.6.2Методы парсинга: практическое руководство. Хитрость заключается в передаче парсерахвоста(в дополнение к сканеру) каждому парсеру. Тогда начальный парсер будет просто:start >>end_p;(end_p - это хвост старта).
Дух жадный, используя прямо вперед, наивный РД. Конечно, можно реализовать полностью схему обратного отслеживания, представленную выше, но также будет хит производительности. Схема всегда будет пытаться сопоставить все возможные пути парсера (полный обход иерархии парсера) до тех пор, пока не достигнет точки уверенности, что все совпадает или не совпадает.
Отслеживание и Жадный РД
Дух вполне постоянен и интуитивно понятен в том, когда он отступает и куда, хотя это может быть неочевидно для тех, кто приходит из разных слоев общества. Как правило, любой (под)парсер, учитывая один и тот же вход, всегда соответствует одной и той же части входа (или вообще не соответствует входу). Это означает, что Дух по своей природе жадный. Дух будет отступать только тогда, когда (под)парсер не соответствует входу, и он всегда будет отступать к следующей точке выбора вверх (а не назад) в структуре парсера. Другими словами, abb |ab будет соответствовать "ab ", как будет a (bb | b), но (ab | a)b не будет, потому что (ab | a) подпарсер всегда будет соответствовать b после a, если он доступен.
Райнер Дейк
Есть сильное предпочтение на "простота со всеми ручками, когда вам нужно их " подход, прямо сейчас. С другой стороны, гибкость Духа позволяет иметь различные факультативные схемы. Возможно, в будущем можно будет реализовать исчерпывающую схему обратного отслеживания РД в качестве дополнительной функции.
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)
Статья Rationale раздела может быть полезна для разработчиков на c++ и boost.
Виртуальные функции: От статического к динамическому C++
Отслеживание и Жадный РД