{"id":371,"date":"2009-11-15T20:12:48","date_gmt":"2009-11-16T04:12:48","guid":{"rendered":"http:\/\/boost-spirit.com\/home\/?page_id=371"},"modified":"2009-11-19T10:02:08","modified_gmt":"2009-11-19T18:02:08","slug":"parsing-a-list-of-key-value-pairs-using-spirit-qi","status":"publish","type":"page","link":"http:\/\/boost-spirit.com\/home\/articles\/qi-example\/parsing-a-list-of-key-value-pairs-using-spirit-qi\/","title":{"rendered":"Parsing a List of Key-Value Pairs Using Spirit.Qi"},"content":{"rendered":"

One of the goals of this blog is to provide shrink wrapped solutions for small everyday parsing and output generation problems. We hope to show how Spirit<\/em> may be used to simplify the life for you as a C++ programmer related to data conversion problems from some external representation to your internal data structures and vice versa.<\/p>\n

One of the tasks often to be solved is to parse arbitrary key\/value pairs delimited by some separator into a std::map<\/span>. Parsing the URL query format is one example: key1=value1;key2=value2;\u2026;keyN=valueN<\/span>, and that\u2019s what I would like to provide a reusable solution for.<\/p>\n

Let\u2019s start with the corresponding grammar (written using the notation of Parsing Expression Grammars<\/a>):<\/p>\n

\r\nquery \u2190 pair ((';' \/ '&') pair)*\r\npair  \u2190 key ('=' value)?\r\nkey   \u2190 [a-zA-Z_][a-zA-Z_0-9]*\r\nvalue \u2190 [a-zA-Z_0-9]+\r\n<\/pre>\n
We assume that a key<\/strong> has to start with any letter or an underscore, but otherwise might consist of letters, digits or underscores. A value<\/strong> can not be empty and may consist of letters, digits or underscores only as well. Further, we assume a query<\/strong> to be a sequence of at least one pair<\/strong> delimited by semicolons (‘;’<\/span>) or ampersands (‘&’<\/span>), and a pair<\/strong> to be a sequence of a mandatory key<\/strong> optionally followed by a ‘=’<\/span> and a value<\/strong>.<\/p>\n
Converting any Parsing Expression Grammar (PEG) into an equivalent grammar for Spirit.Qi<\/em> is a purely mechanical step. Let me provide the result first and explain some of the details later on:<\/p>\n
\r\nquery =  pair >> *((qi::lit(';') | '&') >> pair);\r\npair  =  key >> -('=' >> value);\r\nkey   =  qi::char_("a-zA-Z_") >> *qi::char_("a-zA-Z_0-9");\r\nvalue = +qi::char_("a-zA-Z_0-9");\r\n<\/pre>\n
All differences we see are caused by limitations of the C++ language Spirit<\/em> has to live with. Direct juxtaposition is expressed using the right shift operator (‘>>’)<\/span>, postfix operators as the Kleene Star (‘*’<\/span>) and the Plus (‘+’<\/span>) are moved to the front of the corresponding expression and written as prefix operators, and the optional operator (question mark) is rewritten using the unary minus (‘-‘<\/span>). Otherwise the two grammars look fairly similar.<\/span> The char_<\/span> is a predefined Qi parser primitive matching exactly one character based on the description provided as its argument. The lit<\/span> is very similar to char_<\/span> except that it does not expose the matched value as its attribute.<\/p>\n
The next required step is to understand what attribute type each of our defined grammar rules should expose. These attribute types will allow us to map the external representation onto the internal C++ types we will use to store the parsing results. Let us store the keys and the values as std::string<\/span>\u2019s (assuming we have to deal with narrow character representations). The result of a parsed key\/value pair can be conveniently stored into a std::pair<std::string, std::string><\/span>. Finally, the overall result of parsing the query string should be stored into a std::map<std::string, std::string><\/span>. This knowledge allows to write the declaration of our rule variables as used above:<\/p>\n
\r\nqi::rule<Iterator, std::map<std::string, std::string>()> query;\r\nqi::rule<Iterator, std::pair<std::string, std::string>()> pair;\r\nqi::rule<Iterator, std::string()> key, value;\r\n<\/pre>\n
The type qi::rule<><\/span> is a predefined non-terminal parser provided by Spirit<\/em> usable for storing the grammar definitions above. We need to provide the iterator type of the underlying input data (Iterator)<\/span> and the attribute type, which is the type of the data the rule is supposed to store its parsed data in.<\/p>\n
A word about the unusual function declaration syntax used to specify the attribute type of the rule. Non-terminals in recursive descent parsers can be seen as being very similar to functions. They return a value, their (synthesized) attribute, while they optionally may take arguments, their (inherited) attributes. Spirit<\/em> uses the function declaration syntax in order to emphasize this similarity.<\/p>\n
In the beginning I promised to provide a shrink wrapped solution, so what\u2019s still left is to encapsulate the whole functionality. Again Spirit has some recommended way of doing that: grammar<><\/span>\u2019s. Spirit grammar<\/span>\u2019s are special non-terminals acting as containers for one or more rules allowing to encapsulate more complex parsers:<\/p>\n
\r\nnamespace qi = boost::spirit::qi;\r\n\r\ntemplate <typename Iterator>\r\nstruct keys_and_values\r\n  : qi::grammar<Iterator, std::map<std::string, std::string>()>\r\n{\r\n    keys_and_values()\r\n      : keys_and_values::base_type(query)\r\n    {\r\n        query =  pair >> *((qi::lit(';') | '&') >> pair);\r\n        pair  =  key >> -('=' >> value);\r\n        key   =  qi::char_("a-zA-Z_") >> *qi::char_("a-zA-Z_0-9");\r\n        value = +qi::char_("a-zA-Z_0-9");\r\n    }\r\n    qi::rule<Iterator, std::map<std::string, std::string>()> query;\r\n    qi::rule<Iterator, std::pair<std::string, std::string>()> pair;\r\n    qi::rule<Iterator, std::string()> key, value;\r\n};\r\n<\/pre>\n
The derivation from Qi\u2019s grammar type converts the keys_and_values<\/span> type into a parser. Its member rules define a grammar which makes it usable for recognizing URL query strings. The base class constructor gets passed the start<\/strong> rule, which is the top most rule of the grammar to be executed when the grammar is invoked. The type keys_and_values<\/span> has a template parameter allowing to utilize this grammar with arbitrary iterator types.<\/p>\n
The last missing code piece shows how to invoke the newly created parser.<\/p>\n
\r\nstd::string input("key1=value1;key2;key3=value3");  \/\/ input to parse\r\nstd::string::iterator begin = input.begin();\r\nstd::string::iterator end = input.end();\r\n\r\nkeys_and_values<std::string::iterator> p;    \/\/ create instance of parser\r\nstd::map<std::string, std::string> m;        \/\/ map to receive results\r\nbool result = qi::parse(begin, end, p, m);   \/\/ returns true if successful\r\n<\/pre>\n
The function qi::parse()<\/span> is one of Spirit\u2019s main API functions. In the simplest case it takes a pair of iterators pointing to the input sequence to parse (begin, end)<\/span>, an instance of the parser to invoke (p)<\/span>, and the attribute instance to be filled with the converted data (m)<\/span>. This function executes the actual parsing operation and returns true<\/span> if it was successful.<\/p>\n
The fact that attributes of certain types are getting filled on the fly might look like magic to you, or you might think I left out some essential code snippets. But neither it is magic nor did I leave out anything. In Spirit.Qi<\/em> all parser components (such as char_<\/span> or lit<\/span>) expose specific attribute types and all compound parsers (such as sequences and alternatives) implement well defined rules for attribute propagation and merging. Our example uses the knowledge about these rules, and if you want to understand how this works in more detail, please refer to Spirit\u2019s<\/em> documentation.<\/p>\n
Here is an example: as you might expect char_<\/span> exposes the matched character as its attribute. The Kleene Star (‘*’<\/span>) and the Plus (‘+’<\/span>) are compound parsers collecting the attributes of their embedded parser in a (STL<\/a> compatible) container (in our case a std::string<\/span>, which is a container of char<\/span>). The non-terminal rule<\/span> normally inherits the attribute of the parser expression on the right hand side of its assignment. Last but not least, sequences match the attributes of their elements to the corresponding parts of their attribute data structure. Since literals (such as ‘=’<\/span> or lit(‘;’)<\/span>) do not expose any attribute, the expression<\/span><\/p>\n
\r\npair  =  key >> -('=' >> value);\r\n<\/pre>\n
naturally combines the two string attributes of key<\/strong> and value<\/strong> into the pair of strings as expected by the non-terminal pair<\/strong>, initializing the attribute of value<\/strong> with an empty string if it is not matched.<\/p>\n
If you want to try it out for yourself, the complete source code for this example is available from the Boost<\/a> SVN here<\/a>. In the future this example will be distributed as part of the Spirit distribution, but for now it lives in the SVN only.<\/p>\n
Share this:<\/h3>