Разбор с помощью Spirit Qi
Я работал над инструментом для анализа / обработки файлов проекта Apple Xcode. Поскольку этот формат может изменяться в каждой новой версии Xcode, синтаксический анализатор должен быть очень чистым и удобным в обслуживании. Кроме того, я планировал использовать этот инструмент для обработки файлов в качестве внутренней службы, и скорость была решающей частью реализации.
Прежде чем приступить к реализации, я проверил множество реализаций C ++, доступных в Интернете. Некоторые из них не были завершены, а некоторые из них трудно было поддерживать.
Вместо этого я использовал Boost.Spirit Qi, чтобы написать парсер с нуля, и в этой статье я покажу, как его можно использовать для решения всех вышеперечисленных проблем.
Введение:
Boost Spirit - это набор библиотек парсера, лексера и генерации вывода. Он интенсивно развивается с 2001 года (да, более 15 лет!)
Qi - это библиотека Spirit для синтаксического анализа, которая использует грамматику Extended Backus-Naur Form (EBNF) непосредственно в C ++. Это очень полезно, если вы работаете с программой чтения файлов, сетевым протоколом высокого уровня или даже языком для конкретной предметной области. Это очень быстро (самый быстрый http://boost-spirit.com/home/2014/09/03/fastest-numeric-parsers-in-the-world/)
Что такое EBNF:
EBNF - это простая для понимания грамматика для определения структурированного текста.
EBNF чисел:
zero = "0"; none_zero = "1".."9"; digit = zero | none_zero
«0» и «9» называются терминалами. ноль и none_zero называются без терминалов или производственными правилами. Каждое правило можно определить как смесь терминалов и ни одного терминала. Вы можете дополнительно контролировать эти правила с помощью богатого набора операторов (как в регулярных выражениях). Например, мы можем использовать «..» как оператор диапазона и «|» как оператор OR.
Так что же такое число? Число может быть просто нулем:
number = zero;
Или нулевую цифру:
number = zero | none_zero;
Или последовательность цифр, начинающаяся с нуля:
number = zero | none_zero | ( none_zero ( zero | none_zero )* )
Здесь круглые скобки используются для группировки правил и звездочки Клини «*» для обозначения повторения.
Обратите внимание на пробел между none_zero и (zero | none_zero) *. В терминах EBNF это означает none_zero , за которым следует (zero | none_zero) *. если мы хотим, мы можем альтернативно использовать запятую:
number = zero | none_zero | ( none_zero, ( zero | none_zero )* )
Теперь эта грамматика должна принимать все числа, но у нас есть проблема. Если мы попробуем ввести 0 или 6, это будет работать для однозначных чисел (поскольку у нас есть ноль | none_zero). Но если мы попробуем ввести многозначное число, такое как 983, это правило будет читать только первую цифру 9 и не сможет проанализировать остальную часть. Это из-за свойства приоритета грамматик EBNF. Если мы переформатируем наше правило и сначала воспользуемся наиболее жадным вариантом, оно будет работать должным образом:
number = ( none_zero, ( zero | none_zero )* ) | zero | none_zero
Сначала он попытается сопоставить многозначное число, начинающееся с none_zero, если не удастся, то нуля, а если и это не удастся, оно попытается сопоставить none_zero однозначное число.
Обратите внимание: (none_zero, (zero | none_zero) *) принимает none_zero, за которым следует ноль или более цифр. Это означает, что эту часть можно использовать для одиночных цифр none_zero или для многозначных цифр, начинающихся с none_zero. Затем мы можем упростить наше правило следующим образом:
number = ( none_zero ( zero | none_zero )* ) | zero;
Наконец, мы добавляем опцию знака:
number = ( [ "-" ] none_zero ( zero | none_zero )* ) | zero;
Это правило принимает значения 0, -8, 2147483647 и 1000000. Если вы попробуете ввести такой параметр, как 000001 или 000, он будет правильно соответствовать только первому нулю.
EBNF действительных чисел:
real_number = number [ "." digit { digit }];
Выше будет читаться так: действительное число - это число, за которым следует необязательная последовательность, начинающаяся с «.», А затем любая последовательность цифр s . Теперь он поддерживает действительные числа, такие как -666, 2.0, 3.14 и 1.00009. (Это также приведет к неправильному синтаксическому анализу 1.00000 или 1.100000, которые нам нужно будет адресовать в реальной реализации синтаксического анализатора. Но синтаксический анализ с плавающей запятой содержит массу других деталей (например, экспоненты и точность), которые мы пропустим в этой статье.)
Парсер Spirit Qi EBNF:
Грамматику EBNF очень легко перевести в Spirit Qi. Единственное, что нам нужно знать, это то, что некоторые операторы, такие как фигурные скобки, запятая, пробел или звездочка Клини, нельзя напрямую использовать в C ++. (Да, вы можете найти шутку Бьярна Страуструпа, посвященную Дню дураков, в 1998 ссылке. для космических операторов)
Сначала мы включаем заголовок и определяем сокращение для пространства имен qi:
#include <boost/spirit/include/qi.hpp> namespace qi = boost::spirit::qi;
Число в ци:
const auto zero = qi::char_( ‘0’ );
const auto none_zero = qi::char_( ‘1’ ) |
qi::char_( ‘2’ ) |
qi::char_( ‘3’ ) |
qi::char_( ‘4’ ) |
qi::char_( ‘5’ ) |
qi::char_( ‘6’ ) |
qi::char_( ‘7’ ) |
qi::char_( ‘8’ ) |
qi::char_( ‘9’ );
const auto digit = zero | none_zero;
const auto number = ( -( qi::char_( "-" ) ) >> none_zero >> *digit ) | zero;
Мы используем некоторые из предопределенных синтаксических анализаторов Qi: qi :: char_ соответствует любому символу или его можно использовать для определенного символа, используя форму qi :: char_ ('B') или для диапазона символов qi :: char_ («A», «Z»). qi :: lit («text») определяет текст, который используется как есть и пропускается во время вывода. qi :: eol - это конец строки, а qi :: space - это пробел (то есть табуляции, пробелы). Снова круглые скобки используются для группировки операторов, а оператор «-» используется для указания необязательности. «››» - оператор конкатенации, эквивалентный тому, что делает пробел или запятая в EBNF.
Совет: мы можем реализовать none_zero как:
const auto none_zero = qi::char_( ‘1’, ‘9’ );
Реальные числа в ци:
const auto real_number = number >> -( qi::char_( ‘.’ ) >> digit >> *digit );
Давайте проанализируем:
std::string input = "3.14159265359"; std::string output; qi::parse( input.begin(), input.end(), real_number, output ); assert( input == output );
Живой код: number, real_number
Давайте проанализируем файл PBXProj:
// !$*UTF8*$!
{
archiveVersion = 1;
classes = {};
objectVersion = 46;
objects = {
41EC29201BFE456C00AEA710 /* Project object */ = {
};
};
rootObject = 41EC29201BFE456C00AEA710 /*Project object*/;
}
PBXProj - это формат файла проекта Xcode. С точки зрения Apple, это список собственности. Он может иметь двоичную, XML или JSON-форму, и вы можете использовать plutil для преобразования между ними:
plutil -convert xml1 -o - {project_name}.xcodeproj/project.pbxproj
В этой статье мы сосредоточимся только на разборе формата «JSON».
Давайте рассмотрим формат данных. Хотя он называется JSON, есть ряд отличий от стандарта:
- В стандартном формате нет поддержки комментариев (однострочных и многострочных).
- В стандартном формате строковое значение необходимо заключить в двойные кавычки. В этом случае он переносится только в том случае, если есть данные, содержащие пробелы или некоторые специальные символы.
Для хранения проанализированного вывода нам нужны структуры данных. Мы будем рассматривать все числа, логические и нули как строки. Кроме того, массивы обрабатываются как std :: vector значений и объекты как std :: maps (введите строковое значение для имени атрибута).
Мы реализуем его как абстрактное синтаксическое дерево (AST):
class ASTValue;
class ASTObject;
class ASTArray;
using ASTVariant = boost::variant<
boost::recursive_wrapper<ASTObject>,
boost::recursive_wrapper<ASTArray>,
std::string>;
using ASTAttributeMapT = std::map<std::string, ASTValue>;
using ASTValuesT = std::vector<ASTValue>;
struct ASTValue
{
ASTVariant value;
};
struct ASTObject
{
ASTAttributeMapT attributes;
};
struct ASTArray
{
ASTValuesT values;
};
Здесь мы использовали Boost.Variant и Boost.recursive_wrapper, чтобы заставить ASTValue хранить строку, объект или массив.
Чтобы Qi могла использовать эти структуры, нам нужно адаптировать их с помощью Boost.Fusion:
BOOST_FUSION_ADAPT_STRUCT(ASTValue,(ASTVariant,value)) BOOST_FUSION_ADAPT_STRUCT(ASTObject,(ASTAttributeMapT,attributes )) BOOST_FUSION_ADAPT_STRUCT(ASTArray,(ASTValuesT,values))
Для удобства мы определяем сокращения для boost :: spirit, boost :: spirit :: qi и boost :: phoenix:
namespace spirit = boost::spirit; namespace qi = spirit::qi; namespace phoenix = boost::phoenix;
Ци может группировать правила в грамматических объектах. Мы создаем подкласс от грамматики Qi, которая по шаблону соответствует нашему строковому типу итератора. Таким образом, одна грамматика Qi может работать с разными типами ввода. Нам нужно инициализировать наш суперкласс (base_type / Grammar) с последним правилом, которым мы объединяем все наши правила:
template<typename IteratorT>
class SkipperGrammar : public qi::grammar<IteratorT>
{
public:
SkipperGrammar()
:SkipperGrammar::base_type( rule )
{
lineCommentRule = qi::lit( "//" ) >>
*(qi::char_ -qi::eol) >>
qi::eol;
blockCommentRule = qi::lit( "/*" ) >>
*(qi::char_ -qi::lit( "*/" ) ) >>
qi::lit( "*/" );
spaceRule = qi::space;
rule = spaceRule | lineCommentRule | blockCommentRule;
}
qi::rule<IteratorT> lineCommentRule;
qi::rule<IteratorT> blockCommentRule;
qi::rule<IteratorT> spaceRule;
qi::rule<IteratorT> rule;
};
Qi может использовать определенную грамматику шкипера, чтобы обрабатывать желаемую часть нашего ввода как пробелы.
Прежде чем мы обсудим детали, нам нужно проверить интересное свойство грамматик. Допустим, мы хотим иметь грамматику, которая читает все символы и останавливается на «B».
Наш вклад:
AACCCA12312344BASDEGFHFG
Эту грамматику можно записать как:
*qi::char_ >> qi::char_( 'B' )
Но поскольку любой символ (* qi :: char_) также будет соответствовать «B», он никогда не остановится на «B». В этом случае он проанализирует все AACCCA12312344BASDEGFHFG. Нам нужно определить четкую границу для парсера * qi :: char_. Вместо этого мы пишем:
*( qi::char - qi::char( 'B') ) >> qi::char_( 'B' )
Давайте проверим правила:
lineCommentRule: начинается с литерала «//» и считывает все символы до конца строки. Как объяснялось выше, мы вычли qi :: eol из * qi :: char_, чтобы определить границу для любого символьного выражения.
blockCommentRule: начинается с литерала «/ *» и читает все (включая концы строк) до буквального «* /».
spaceRule: мы также хотим включить любые обычные пробелы, предопределенные в Qi.
правило: мы объединяем все правила в это правило. Обратите внимание, что мы сначала предоставляем spaceRule. Ци будет пробовать каждый вариант слева направо, и большая часть нашего ввода будет пропускать пробелы. Мы стараемся, чтобы qi :: space был первым выбором для оптимизации нашего правила.
Мы написали SkipperGrammar, давайте поработаем над следующей важной вещью; наша грамматика строковых значений. Обрисуем, какие формы могут иметь эти строковые значения:
- Его можно заключить в двойные кавычки.
- Он может содержать экранированные символы, такие как «\\ n», которые необходимо преобразовать в «\ n».
- Это может быть обычная строка с некоторой поддержкой символов (./_-) (используется для путей и строк версии).
- Это может быть целое число или число с плавающей запятой.
template<typename IteratorT, typename SkipperT>
class ValueGrammar : public qi::grammar<IteratorT, std::string(), SkipperT>
{
public:
ValueGrammar()
:ValueGrammar::base_type( rule, "String" )
{
escapedStringRule %= qi::lexeme[
qi::lit( '"' ) >>
*( escapeCharSymbols | ( qi::char_ - qi::char_( '"' ) ) ) >
qi:lit( '"') ];
rawStringRule %= qi::lexeme[
+( qi::alnum |
qi::char_( '.' ) |
qi::char_( '/' ) |
qi::char_( '_' ) |
qi::char_( '-' )
) ];
rule %= rawStringRule | escapedStringRule;
escapeCharSymbols.add ( "\\a", '\a' )
( "\\b", '\b' )
( "\\f", '\f' )
( "\\n", '\n' )
( "\\r", '\r' )
( "\\t", '\t' )
( "\\v", '\v' )
( "\\\\", '\\' )
( "\\\'", '\'' )
( "\\\"", '\"' );
escapedStringRule.name( "Escaped String" );
rawStringRule.name( "Escaped String" );
escapeCharSymbols.name( "Escaped Chars" );
}
qi::rule<IteratorT, std::string(), SkipperT> escapedStringRule;
qi::rule<IteratorT, std::string(), SkipperT> rawStringRule;
qi::rule<IteratorT, std::string(), SkipperT> rule;
qi::symbols<const char, const char> escapeCharSymbols;
};
qi :: lexeme […] определит блок, внутри которого грамматика пропуска блока отключена, «% =» скажет Qi создать правило без семантических действий, qi :: alnum - это буквенно-цифровой синтаксический анализатор, а qi :: symbols ‹…› - особый синтаксический анализатор для таблиц символов. Это позволит нам заменить символы с двойным экранированием на одинарные экранированные символы.
Мы также назвали свои правила. Ци может использовать эти имена в отчетах об ошибках, чтобы предоставить более подробную информацию о причине ошибки.
Обратите внимание, что некоторые правила получили форму qi :: rule ‹IteratorT, std :: string (), SkipperT›. Здесь std :: string () сообщает Qi создать правило, которое выводит std :: string и использует SkipperT для внутренних целей. Порядок аргументов этого шаблона не важен, но тип вывода должен быть реализован как std :: string (). При написании грамматики убедитесь, что вы указали все правила с одинаковыми типами итератора и пропуска.
Остальное не требует пояснений:
using ASTNameValuePairT = std::pair<std::string, ASTValue>;
template<typename IteratorT, typename SkipperT>
class Grammar : public qi::grammar<IteratorT, ASTObject(), SkipperT>
{
public:
Grammar()
:Grammar::base_type( objectRule, "Object" )
{
objectRule %= qi::lit( '{' ) >> -attributesRule > qi::lit( '}' );
arrayRule %= qi::lit( '(' ) >>
-valuesRule >>
-qi::lit( ',' ) >
qi::lit( ')' );
attributesRule %= attributeRule >>
*( qi::lit( ';' ) >> attributeRule ) >>
-qi::lit( ';' );
attributeRule %= nameRule > qi::lit( '=' ) > valueRule;
nameRule %= qi::lexeme[ +( qi::alnum | qi::char( '_' ) ) ];
valuesRule %= ( objectRule % qi::lit( ',' ) ) |
( arrayRule % qi::lit( ',' ) ) |
( stringRule % qi::lit( ',' ) );
valueRule %= objectRule | arrayRule | stringRule;
objectRule.name( “Object” );
arrayRule.name( “Array” );
attributesRule.name( “Attributes” );
attributeRule.name( “Attribute” );
nameRule.name( “Name” );
valuesRule.name( “Values” );
valueRule.name( “Value” );
stringRule.name( “String” );
}
qi::rule<IteratorT, ASTObject(), SkipperT> objectRule;
qi::rule<IteratorT, ASTArray(), SkipperT> arrayRule;
qi::rule<IteratorT, ASTAttributeMapT(), SkipperT> attributesRule;
qi::rule<IteratorT, ASTNameValuePairT(), SkipperT> attributeRule;
qi::rule<IteratorT, std::string(), SkipperT> nameRule;
qi::rule<IteratorT, ASTValuesT(), SkipperT> valuesRule;
qi::rule<IteratorT, ASTValue(), SkipperT> valueRule;
ValueGrammar<IteratorT, SkipperT> stringRule;
};
И функция парсера:
template<typename IteratorT>
ASTObject parse( const IteratorT & begin,
const IteratorT & end
)
{
using LinePosIteratorT = spirit::line_pos_iterator<IteratorT>;
using SkipperGrammarT = SkipperGrammar<LinePosIteratorT>;
using ParserGrammarT = Grammar<LinePosIteratorT, SkipperGrammarT>;
SkipperGrammarT skipper;
ParserGrammarT grammar;
LinePosIteratorT posIterBegin( begin );
LinePosIteratorT posIterEnd( end );
try
{
ASTObject result;
const bool parseResult = qi::phrase_parse( posIterBegin,
posIterEnd,
grammar,
skipper,
result );
if( parseResult && posIterBegin == posIterEnd )
{
return result;
} else {
throw std::runtime_error{ "Parser Failed" };
}
} catch ( ... ) {
throw std::runtime_error{ "Parser Failed" };
}
return ASTObject{};
}
int main()
{
// Read file contents.
std::string input = "......" // our pbxproj file content.
try{
ASTObject result = parse( input.begin(), input.end() );
} catch( ... )
{
// Error reporting
}
}
Примечания :
- Ци очень велика, чтобы ее можно было охватить в одной статье. Он предоставляет гораздо больше: вы можете использовать большой набор встроенных функций; от числовых анализаторов до двоичных анализаторов. Сделав необходимые части вашей грамматики более строгими (вместо оператора ››, использующего только ›), вы можете контролировать то, что следует рассматривать как ошибку. Вы можете работать с любым типом хранилища (например, с широким символом). Вы можете анализировать наборы символов Юникода. У вас есть полный контроль над тем, что следует игнорировать (или рассматривать как пробелы). Он может синтезировать проанализированные данные, и вы можете предоставить свои собственные типы ... Он даже прекрасно работает с глубоко вложенными структурами! Благодаря поддержке библиотеки Boost.Phoenix он предоставляет семантические действия (встроенные функции) для полного контроля над процессом синтаксического анализа.
- Иногда бывает трудно развиваться с Духом. Ошибки компилятора могут становиться очень длинными и трудными для понимания из-за шаблонов выражений или Boost.Fusion. Я надеюсь, что в V3 это станет лучше. А пока я предлагаю сохранять как можно меньше изменений и компилировать каждый маленький шаг, чтобы убедиться, что они работают. Это очень хорошая идея, чтобы грамматики были хорошо разбиты на разделы и были простыми, чтобы их можно было поддерживать и оптимизировать в дальнейшем.
- Во встраиваемых кодах Medium нет поддержки подсветки синтаксиса, управления размером, шрифтом и т. Д. Я заметил, что их трудно читать. Если Medium решит исправить это, я переформатирую их, чтобы сделать их более удобочитаемыми.
Использованная литература :
