{"id":400,"date":"2009-11-18T00:00:07","date_gmt":"2009-11-18T08:00:07","guid":{"rendered":"http:\/\/boost-spirit.com\/home\/?page_id=400"},"modified":"2009-11-19T18:51:54","modified_gmt":"2009-11-20T02:51:54","slug":"output-generation-from-a-list-of-key-value-pairs-using-spirit-karma","status":"publish","type":"page","link":"http:\/\/boost-spirit.com\/home\/articles\/karma-examples\/output-generation-from-a-list-of-key-value-pairs-using-spirit-karma\/","title":{"rendered":"Output Generation from a List of Key-Value Pairs Using Spirit.Karma"},"content":{"rendered":"<p>Even if it feels a bit like cheating I decided to get back to the example highlighting lists of key\/value pairs I initially wrote about <a href=\"http:\/\/boost-spirit.com\/home\/?page_id=371\">here<\/a>. On the other hand looking at this very same problem from the standpoint of generating output allows me to highlight a couple a interesting facilities <em>Spirit<\/em> provides you with.<\/p>\n<h4>A Few Words up Front<\/h4>\n<p>Starting with V2.1 (released with <a href=\"http:\/\/www.boost.org\/users\/news\/version_1_41_0\" target=\"_blank\">Boost V1.41<\/a>) <em>Spirit<\/em> is more than a parser generator library. It now contains two separate, but nevertheless tightly connected sub-libraries: <em>Spirit.Qi<\/em> \u2013 for parsing and <em>Spirit.Karma<\/em> \u2013 for output generation. Understanding <em>Spirit.Karma<\/em> is not hard at all if you already know <em>Spirit.Qi<\/em>. The two sub-libraries are like <a href=\"http:\/\/en.wikipedia.org\/wiki\/Yin_and_yang\" target=\"_blank\">Yin and Yang<\/a>. Everything you have learnt so far about <em>Qi\u2019s<\/em> parsers is equally true for <em>Karma\u2019s<\/em> generators, with the exception that this knowledge has to be applied \u2018inside out\u2019.<\/p>\n<ul>\n<li><em>Qi<\/em> is all about parsing byte sequences into internal data structures, <em>Karma<\/em> is about generating byte sequences from those.<\/li>\n<li>If <em>Qi<\/em> gets its input from input iterators, then <em>Karma<\/em> outputs the generated data using an output iterator.<\/li>\n<li>If <em>Qi<\/em> uses overloaded versions of the <span style=\"font-family: courier new\">\u2018&gt;&gt;\u2019<\/span> do denote sequences of things, <em>Karma<\/em> uses the <span style=\"font-family: courier new\">\u2018&lt;&lt;\u2019<\/span>.<\/li>\n<li><em>Qi\u2019s<\/em> semantic actions receive a value from the parser they are attached to; but <em>Karma\u2019s<\/em> semantic actions are providing values to their generators.<\/li>\n<li>If <em>Qi\u2019s<\/em> parser attributes are passed up the parser hierarchy to fill the data structures supplied by the user, then <em>Karma\u2019s<\/em> attributes are passed down the generator hierarchy, extracting the values the user wants to generate output from.<\/li>\n<\/ul>\n<p>This duality allowed us to develop <em>Qi<\/em> and <em>Karma<\/em> using a common library infrastructure and common implementation techniques, and it makes it easier for the user to work with either of the libraries. Most importantly, <em>Qi<\/em> and <em>Karma<\/em> share a common syntax, exposing a common Domain Specific Embedded Language (based on <a href=\"http:\/\/en.wikipedia.org\/wiki\/Parsing_expression_grammar\" target=\"_blank\">Parsing Expression Grammars<\/a> &#8211; PEG) formed by using C++ operator overloading.<\/p>\n<h4>The Actual Output Generation<\/h4>\n<p>Let\u2019s get back to the problem at hand: generating output from a list of key\/value pairs. Again, we start with writing the grammar, which in this case describes the output format for the URL query string: <span style=\"font-family: courier new\">key1=value1&amp;key2=value2&amp;\u2026&amp;keyN=valueN<\/span>.<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\nquery \u2192 pair ('&amp;' pair)*\r\npair  \u2192 key ('=' value)?\r\nkey   \u2192 [a-zA-Z_][a-zA-Z_0-9]*\r\nvalue \u2192 [a-zA-Z_0-9]+\r\n<\/pre>\n<p>This is almost identical to the grammar we used to derive the <a href=\"http:\/\/boost-spirit.com\/home\/?page_id=371\">parser solution<\/a>. We slightly modified the usual PEG syntax by changing the\u00a0\u2190 to the\u00a0\u2192 to denote the top down nature of output generation, but otherwise the notation is unchanged. A <strong>query<\/strong> should be printed as a list of at least one <strong>pair<\/strong>, where these have to be separated by <span style=\"font-family: courier new\">\u2018&amp;\u2019<\/span><span style=\"font-family: trebuchet ms\">. Each pair should be formatted as a mandatory <strong>key<\/strong>, optionally followed by a <span style=\"font-family: courier new\">\u2018=\u2019<\/span> and the <strong>value<\/strong>, where both, <strong>key<\/strong> and <strong>value<\/strong> have defined some constraints on what characters are allowed. <\/span><\/p>\n<p>After you have seen how any PEG can be converted into a <em>Qi<\/em> parser <a href=\"http:\/\/boost-spirit.com\/home\/?page_id=371\" target=\"_blank\">here<\/a>, you probably will not be surprised to see a similar conversion to be possible for output formats.<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\nquery =  pair &lt;&lt; *('&amp;' &lt;&lt; pair);\r\npair  =  karma::string &lt;&lt; -('=' &lt;&lt; karma::string);\r\n<\/pre>\n<p>In addition to the usual conversion rules, for now we applied some simplifications, namely removing the constraints on the <strong>key<\/strong> and <strong>value<\/strong> formats (we will re-introduce this later). This enables us to use the predefined generator component <span style=\"font-family: courier new\">karma::string<\/span>, a placeholder expression to output any (non-empty) sequence of characters.<\/p>\n<p>Now, as we have the grammar, let\u2019s talk about attributes! Attributes in <em>Qi<\/em> are the types and values we get as the result of converting the input. Attributes in <em>Karma<\/em> are the types and values we want to generate output from. We assume the list of key\/value pairs to be stored in a <span style=\"font-family: courier new\">std::vector<\/span>, while the pairs themselves are stored in a <span style=\"font-family: courier new\">std::pair<\/span>. The only slight difficulty comes from the optional nature of the stored values. As the value may be given or not we store it in a <span style=\"font-family: courier new\">boost::optional&lt;std::string&gt;<\/span>, leaving it uninitialized if no value is present:<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\ntypedef std::pair&lt;std::string, boost::optional&lt;std::string&gt; &gt; pair_type;\r\n\r\nkarma::rule&lt;OutputIterator, std::vector&lt;pair_type&gt;()&gt; query;\r\nkarma::rule&lt;OutputIterator, pair_type()&gt; pair;\r\n<\/pre>\n<p>Generator non-terminals encapsulate a format description for a particular data type, and, whenever we need to emit output for this data type, the corresponding non-terminal is invoked in a similar way as the predefined <em>Karma<\/em> generator primitives. The <em>Karma<\/em> non-terminals are very similar to the <em>Qi<\/em> non-terminals. The main difference is that they do not expose a <em>synthesized<\/em> attribute (as parsers do), but they require a special <em>consumed<\/em> attribute. Even if the consumed attribute is not &#8216;returned&#8217; from the generator (as the synthesized parser attributes in <em>Qi<\/em>) we chose to utilize the same function style declaration syntax as used in <em>Qi<\/em>. For the rule definitions above we need to provide at least the output iterator type of the output data sink <span style=\"font-family: courier new\">(OutputIterator)<\/span> and the consumed attribute type, which is the type of the data the rule is supposed to generate output from.<\/p>\n<p>The encapsulation of the whole grammar is straightforward when using <span style=\"font-family: courier new\">karma::grammar&lt;&gt;<\/span>:<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\nnamespace karma = boost::spirit::karma;\r\n\r\ntemplate &lt;typename OutputIterator&gt;\r\nstruct keys_and_values\r\n  : karma::grammar&lt;OutputIterator, std::vector&lt;pair_type&gt;()&gt;\r\n{\r\n    keys_and_values()\r\n      : keys_and_values::base_type(query)\r\n    {\r\n        query =  pair &lt;&lt; *('&amp;' &lt;&lt; pair);\r\n        pair  =  karma::string &lt;&lt; -('=' &lt;&lt; karma::string);\r\n    }\r\n    karma::rule&lt;OutputIterator, std::vector&lt;pair_type&gt;()&gt; query;\r\n    karma::rule&lt;OutputIterator, pair_type()&gt; pair;\r\n};\r\n<\/pre>\n<p>Deriving your type from <span style=\"font-family: courier new\">karma::grammar&lt;&gt;<\/span><span style=\"font-family: trebuchet ms\"> creates a new <em>Karma<\/em> generator representing the enclosed format description. The base class is initialized with the start rule (<strong>query<\/strong>), which is the top most rule of the grammar to be executed when the grammar is invoked. The template parameter <span style=\"font-family: courier new\">OutputIterator<\/span> makes the grammar usable with any underlying output stream chosen.<\/span><\/p>\n<p>The following code snippet concludes the example by demonstrating how to invoke our grammar:<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\ntypedef std::back_insert_iterator&lt;std::string&gt; sink_type;\r\ntypedef boost::optional&lt;std::string&gt; value_type;\r\n\r\nstd::vector&lt;pair_type&gt; v;                    \/\/ vector containing data\r\nv.push_back(pair_type(&quot;key1&quot;, value_type(&quot;value1&quot;)));\r\nv.push_back(pair_type(&quot;key2&quot;, value_type()));\r\nv.push_back(pair_type(&quot;key3&quot;, value_type(&quot;&quot;)));\r\n\r\nstd::string generated;\r\nsink_type sink(generated);\r\nkeys_and_values&lt;sink_type&gt; g;                \/\/ create instance of\r\n                                             \/\/ generator\r\n\r\nbool result = karma::generate(sink, g, v);   \/\/ returns true if\r\n                                             \/\/ successful\r\n\r\n\/\/ \u2018generated\u2019 will hold: &quot;key1=value1&amp;key2&amp;key3=&quot;\r\n<\/pre>\n<p>The function <span style=\"font-family: courier new\">karma::generate()<\/span> is another of Spirit\u2019s main API functions. In the simplest case it takes an output iterator representing the output target to send the output to <span style=\"font-family: courier new\">(sink)<\/span>, an instance of the generator to invoke <span style=\"font-family: courier new\">(g)<\/span>, and the attribute instance holding the data <span style=\"font-family: courier new\">(v)<\/span>. This function executes the actual generator operation and returns <span style=\"font-family: courier new\">true<\/span> if it was successful.<\/p>\n<p><em>Karma<\/em> has well defined attribute propagation and splitting rules along the same lines as <em>Qi<\/em> does. These rules allow for the code above to actually work as expected. The Kleene Star splits the supplied (STL compatible) container and passes its elements to the embedded generator, one at a time. That\u2019s the reason why we use the <span style=\"font-family: courier new\">value_type<\/span> of the vector as the attribute type of the rule <strong>pair<\/strong>. The sequence on the right hand side of <strong>pair<\/strong> matches the member elements of its attribute to the corresponding sequence parts, which naturally splits off the <span style=\"font-family: courier new\">std::pair<\/span>. It is interesting to note that the optional part of this rule, <span style=\"font-family: courier new\">-(&#8216;=&#8217; &lt;&lt; karma::string)<\/span>, includes the <span style=\"font-family: courier new\">\u2018=\u2019<\/span>, which allows us to skip generating the <span style=\"font-family: courier new\">\u2018=\u2019<\/span> if the value is not initialized (empty).<\/p>\n<p>In the beginning I promised to come back to the issue of adding constraints to the keys and values generated. Assuming we want to apply the constraints as listed in the initial PEG grammar we could write:<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\nkarma::rule&lt;OutputIterator, std::string()&gt; key, value;\r\nkey   =  karma::char_(&quot;a-zA-Z_&quot;) &lt;&lt; *karma::char_(&quot;a-zA-Z_0-9&quot;);\r\nvalue = +karma::char_(&quot;a-zA-Z_0-9&quot;);\r\n<\/pre>\n<p>Additionally we would have to change the format description for <strong>pair<\/strong>:<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\npair  =  key &lt;&lt; -('=' &lt;&lt; value);\r\n<\/pre>\n<p>These changes alone will force the generator to fail if either the key or the value contained \u2018illegal\u2019 characters. This works because Karma generators check their attribute against the immediate value they are initialized from, while failing if those do not match.<\/p>\n<h4>Concluding Remarks<\/h4>\n<p>A last, more general note. Comparing parsing of lists of key\/value pairs with how these can be generated reveals something perhaps unexpected. The grammars used are almost identical! But if you think about this it probably will get obvious. This similarity has been maintained based on the idea that a grammar usable to describe the expected structure of some input may as well be used to formalize the structure of a correspondingly generated output. Parsing, most of the time, is implemented by comparing the input with the patterns defined by the grammar. If we use the same patterns to format a matching output, the generated sequence will follow the rules of the grammar as well.<\/p>\n<p>If you want to try out this example for yourself, the complete source code is available from the <a href=\"http:\/\/www.boost.org\/\" target=\"_blank\">Boost<\/a> SVN <a href=\"http:\/\/svn.boost.org\/svn\/boost\/trunk\/libs\/spirit\/example\/karma\/key_value_sequence.cpp\" target=\"_blank\">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<div class=\"sharedaddy sd-sharing-enabled\"><div class=\"robots-nocontent sd-block sd-social sd-social-icon-text sd-sharing\"><h3 class=\"sd-title\">Share this:<\/h3><div class=\"sd-content\"><ul><li><a href=\"#\" class=\"sharing-anchor sd-button share-more\"><span>Share<\/span><\/a><\/li><li class=\"share-end\"><\/li><\/ul><div class=\"sharing-hidden\"><div class=\"inner\" style=\"display: none;\"><ul><li class=\"share-facebook\"><a rel=\"nofollow noopener noreferrer\" data-shared=\"sharing-facebook-400\" class=\"share-facebook sd-button share-icon\" href=\"http:\/\/boost-spirit.com\/home\/articles\/karma-examples\/output-generation-from-a-list-of-key-value-pairs-using-spirit-karma\/?share=facebook\" target=\"_blank\" title=\"Click to share on Facebook\" ><span>Facebook<\/span><\/a><\/li><li class=\"share-twitter\"><a rel=\"nofollow noopener noreferrer\" data-shared=\"sharing-twitter-400\" class=\"share-twitter sd-button share-icon\" href=\"http:\/\/boost-spirit.com\/home\/articles\/karma-examples\/output-generation-from-a-list-of-key-value-pairs-using-spirit-karma\/?share=twitter\" target=\"_blank\" title=\"Click to share on Twitter\" ><span>Twitter<\/span><\/a><\/li><li class=\"share-end\"><\/li><li class=\"share-pinterest\"><a rel=\"nofollow noopener noreferrer\" data-shared=\"sharing-pinterest-400\" class=\"share-pinterest sd-button share-icon\" href=\"http:\/\/boost-spirit.com\/home\/articles\/karma-examples\/output-generation-from-a-list-of-key-value-pairs-using-spirit-karma\/?share=pinterest\" target=\"_blank\" title=\"Click to share on Pinterest\" ><span>Pinterest<\/span><\/a><\/li><li class=\"share-linkedin\"><a rel=\"nofollow noopener noreferrer\" data-shared=\"sharing-linkedin-400\" class=\"share-linkedin sd-button share-icon\" href=\"http:\/\/boost-spirit.com\/home\/articles\/karma-examples\/output-generation-from-a-list-of-key-value-pairs-using-spirit-karma\/?share=linkedin\" target=\"_blank\" title=\"Click to share on LinkedIn\" ><span>LinkedIn<\/span><\/a><\/li><li class=\"share-end\"><\/li><li class=\"share-reddit\"><a rel=\"nofollow noopener noreferrer\" data-shared=\"\" class=\"share-reddit sd-button share-icon\" href=\"http:\/\/boost-spirit.com\/home\/articles\/karma-examples\/output-generation-from-a-list-of-key-value-pairs-using-spirit-karma\/?share=reddit\" target=\"_blank\" title=\"Click to share on Reddit\" ><span>Reddit<\/span><\/a><\/li><li class=\"share-tumblr\"><a rel=\"nofollow noopener noreferrer\" data-shared=\"\" class=\"share-tumblr sd-button share-icon\" href=\"http:\/\/boost-spirit.com\/home\/articles\/karma-examples\/output-generation-from-a-list-of-key-value-pairs-using-spirit-karma\/?share=tumblr\" target=\"_blank\" title=\"Click to share on Tumblr\" ><span>Tumblr<\/span><\/a><\/li><li class=\"share-end\"><\/li><li class=\"share-end\"><\/li><\/ul><\/div><\/div><\/div><\/div><\/div>","protected":false},"excerpt":{"rendered":"<p>Even if it feels a bit like cheating I decided to get back to the example highlighting lists of key\/value pairs I initially wrote about here. On the other hand looking at this very same problem from the standpoint of generating output allows me to highlight a couple a interesting facilities Spirit provides you with. [&hellip;]<\/p>\n<div class=\"sharedaddy sd-sharing-enabled\"><div class=\"robots-nocontent sd-block sd-social sd-social-icon-text sd-sharing\"><h3 class=\"sd-title\">Share this:<\/h3><div class=\"sd-content\"><ul><li><a href=\"#\" class=\"sharing-anchor sd-button share-more\"><span>Share<\/span><\/a><\/li><li class=\"share-end\"><\/li><\/ul><div class=\"sharing-hidden\"><div class=\"inner\" style=\"display: none;\"><ul><li class=\"share-facebook\"><a rel=\"nofollow noopener noreferrer\" data-shared=\"sharing-facebook-400\" class=\"share-facebook sd-button share-icon\" href=\"http:\/\/boost-spirit.com\/home\/articles\/karma-examples\/output-generation-from-a-list-of-key-value-pairs-using-spirit-karma\/?share=facebook\" target=\"_blank\" title=\"Click to share on Facebook\" ><span>Facebook<\/span><\/a><\/li><li class=\"share-twitter\"><a rel=\"nofollow noopener noreferrer\" data-shared=\"sharing-twitter-400\" class=\"share-twitter sd-button share-icon\" href=\"http:\/\/boost-spirit.com\/home\/articles\/karma-examples\/output-generation-from-a-list-of-key-value-pairs-using-spirit-karma\/?share=twitter\" target=\"_blank\" title=\"Click to share on Twitter\" ><span>Twitter<\/span><\/a><\/li><li class=\"share-end\"><\/li><li class=\"share-pinterest\"><a rel=\"nofollow noopener noreferrer\" data-shared=\"sharing-pinterest-400\" class=\"share-pinterest sd-button share-icon\" href=\"http:\/\/boost-spirit.com\/home\/articles\/karma-examples\/output-generation-from-a-list-of-key-value-pairs-using-spirit-karma\/?share=pinterest\" target=\"_blank\" title=\"Click to share on Pinterest\" ><span>Pinterest<\/span><\/a><\/li><li class=\"share-linkedin\"><a rel=\"nofollow noopener noreferrer\" data-shared=\"sharing-linkedin-400\" class=\"share-linkedin sd-button share-icon\" href=\"http:\/\/boost-spirit.com\/home\/articles\/karma-examples\/output-generation-from-a-list-of-key-value-pairs-using-spirit-karma\/?share=linkedin\" target=\"_blank\" title=\"Click to share on LinkedIn\" ><span>LinkedIn<\/span><\/a><\/li><li class=\"share-end\"><\/li><li class=\"share-reddit\"><a rel=\"nofollow noopener noreferrer\" data-shared=\"\" class=\"share-reddit sd-button share-icon\" href=\"http:\/\/boost-spirit.com\/home\/articles\/karma-examples\/output-generation-from-a-list-of-key-value-pairs-using-spirit-karma\/?share=reddit\" target=\"_blank\" title=\"Click to share on Reddit\" ><span>Reddit<\/span><\/a><\/li><li class=\"share-tumblr\"><a rel=\"nofollow noopener noreferrer\" data-shared=\"\" class=\"share-tumblr sd-button share-icon\" href=\"http:\/\/boost-spirit.com\/home\/articles\/karma-examples\/output-generation-from-a-list-of-key-value-pairs-using-spirit-karma\/?share=tumblr\" target=\"_blank\" title=\"Click to share on Tumblr\" ><span>Tumblr<\/span><\/a><\/li><li class=\"share-end\"><\/li><li class=\"share-end\"><\/li><\/ul><\/div><\/div><\/div><\/div><\/div>","protected":false},"author":3,"featured_media":0,"parent":397,"menu_order":1,"comment_status":"open","ping_status":"open","template":"article-page.php","meta":{"_s2mail":"","spay_email":""},"jetpack_shortlink":"https:\/\/wp.me\/PIHdZ-6s","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"http:\/\/boost-spirit.com\/home\/wp-json\/wp\/v2\/pages\/400"}],"collection":[{"href":"http:\/\/boost-spirit.com\/home\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/boost-spirit.com\/home\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/boost-spirit.com\/home\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"http:\/\/boost-spirit.com\/home\/wp-json\/wp\/v2\/comments?post=400"}],"version-history":[{"count":12,"href":"http:\/\/boost-spirit.com\/home\/wp-json\/wp\/v2\/pages\/400\/revisions"}],"predecessor-version":[{"id":458,"href":"http:\/\/boost-spirit.com\/home\/wp-json\/wp\/v2\/pages\/400\/revisions\/458"}],"up":[{"embeddable":true,"href":"http:\/\/boost-spirit.com\/home\/wp-json\/wp\/v2\/pages\/397"}],"wp:attachment":[{"href":"http:\/\/boost-spirit.com\/home\/wp-json\/wp\/v2\/media?parent=400"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}