{"id":977,"date":"2010-02-17T07:45:25","date_gmt":"2010-02-17T15:45:25","guid":{"rendered":"http:\/\/boost-spirit.com\/home\/?p=977"},"modified":"2010-02-17T13:30:16","modified_gmt":"2010-02-17T21:30:16","slug":"parsing-arbitrary-things-in-any-sequence","status":"publish","type":"post","link":"http:\/\/boost-spirit.com\/home\/2010\/02\/17\/parsing-arbitrary-things-in-any-sequence\/","title":{"rendered":"Parsing Arbitrary Things in Any Sequence"},"content":{"rendered":"

Recently, there have been a couple of questions on the Spirit mailing list<\/a><\/em> asking how to parse as set of things known in advance in any sequence and any combination. A simple example would be a list of key\/value pairs with known keys but the keys may be ordered in any sequence. This use case seems to be quite common. Fortunately Spirit provides you with a predefined parser component designed for exactly that purpose: the permutation parser.<\/p>\n

<\/p>\n

Spirit’s<\/em> permutation parser a ^ b<\/span> matches either a<\/span>, b<\/span>, a >> b<\/span>, or b >> a<\/span>, where a<\/span> and b<\/span> can be arbitrary parser expressions. Just like normal sequences this operator can be utilized to combine more than two operands. For instance, the expression a ^ b ^ c<\/span> will match a<\/span> or b<\/span> or c<\/span> (or an combination thereof) in any sequence. The attribute propagation rule for the permutation parser is<\/p>\n

\r\na: A, b: B --> (a ^ b): tuple<optional<A>, optional<B> >\r\n<\/pre>\n
As usual, if one or more operand of the expression do not expose any attribute (expose unused_type<\/span> as their attribute, which is equivalent), this operand disappears from attribute handling:<\/p>\n
\r\na: A, b: Unused --> (a ^ b): optional<A>;\r\n<\/pre>\n
The permutation parser works out of the box whenever you do not require to match all of the elements in the input. But what if you want strict permutation (operands get matched exactly once)? You have two possibilities, as often, one simple and less versatile and one more complex but universally applicable solution. The simple solution is to parse the input and to check afterward whether all optionals in the resulting attribute have been filled.\u00a0I will leave that solution\u00a0as an exercise for the reader.<\/p>\n
If we assume the attribute to be a (Fusion<\/em>) tuple of optionals, containing one optional for each of the parser components in the permutation parser we can write the following code (thanks to Carl Barron for the initial idea).<\/p>\n
This code defines a Phoenix<\/em> function (a lazy function encapsulating some custom functionality) checking whether one or more of the optionals in a given Fusion<\/em> sequence are empty. The Fusion<\/em> algorithm find_if<\/span> iterates over the given sequence of optionals, invoking the option_empty::operator()<\/span> for each of the elements. fusion::find_if<\/span> stops iterating on the first invocation returning true<\/span> and returns the iterator to the element it stopped on. This is very similar to the well known std::find_if<\/span> algorithm.<\/p>\n
\r\nnamespace phoenix = boost::phoenix;\r\nnamespace fusion = boost::fusion;\r\nnamespace qi = boost::spirit::qi;\r\n\r\nclass no_empties_impl\r\n{\r\n    \/\/ helper function object to be invoked by fusion::find_if\r\n    struct optional_empty\r\n    {\r\n        template <typename T>\r\n        bool operator ()(T const& val) const\r\n        {\r\n            return !val;  \/\/ return true if 'val' is empty.\r\n        }\r\n    };\r\n\r\npublic:\r\n    template <typename T>\r\n    struct result { typedef bool type; };\r\n\r\n    \/\/ This operator will get called from the semantic action attached\r\n    \/\/ to the permutation parser. The parameter refers to its overall\r\n    \/\/ attribute: the fusion tuple of optionals.\r\n    template <typename T>\r\n    bool operator ()(T const& t) const\r\n    {\r\n        \/\/ look for an empty optional, if any return false.\r\n        return fusion::find_if<optional_empty>(t) ==\r\n               fusion::end(t);\r\n    }\r\n};\r\n\r\n\/\/ define the Phoenix function\r\nphoenix::function<no_empties_impl> const no_empties = no_empties_impl();\r\n<\/pre>\n
The overall Phoenix function no_empties<\/span> will return false<\/span> if we found at least one non-initialized optional in the passed sequence. The following code snippet illustrates how everything fits together:<\/p>\n
\r\nstd::string input ("BCA");\r\nstd::string::const_iterator begin = input.begin();\r\nstd::string::const_iterator end = input.end();\r\nqi::parse(begin, end,\r\n    (qi::char_('A') ^ 'B' ^ 'C')[qi::_pass = no_empties(qi::_0)]);\r\n<\/pre>\n
We assign the result of the invocation of no_empties<\/span> to Qi’s predefined placeholder _pass<\/span>. If we assign false<\/span>, then the parser the semantic action is attached to will be forced to fail in retrospective (even if it matched the input successfully before). As a result the overall parser expression will succeed as long as a) the permutation parser matches its input and b) the Phoenix<\/em> function inside the semantic action returns true<\/span>.<\/p>\n
For more information about the permutation parser please consult its documentation here<\/a>. Overall, this example is a bit more complex than the average parser you might usually write. It utilizes three libraries: Spirit<\/em>, Phoenix<\/em>, and Fusion<\/em> in a seamless manner. But for sure, once you understand the idea, it will be easier for you to come up with similar solutions. Spirit<\/em> has been designed with Phoenix<\/em> and Fusion<\/em> in mind, and in fact it relies on Fusion<\/em> heavily itself. As a result, the integration of those libraries is almost perfect.<\/p>\n
Share this:<\/h3>