{"id":1416,"date":"2011-04-16T10:27:14","date_gmt":"2011-04-16T17:27:14","guid":{"rendered":"http:\/\/boost-spirit.com\/home\/?p=1416"},"modified":"2011-04-16T14:27:03","modified_gmt":"2011-04-16T21:27:03","slug":"the-keyword-parser","status":"publish","type":"post","link":"http:\/\/boost-spirit.com\/home\/2011\/04\/16\/the-keyword-parser\/","title":{"rendered":"The Keyword parser"},"content":{"rendered":"

The keyword parser construct has recently been added to spirit’s repository<\/a> (available in 1.47 or from svn) . Here’s a small introduction to help you get started using the keyword parsers.<\/p>\n

Those of you familiar with the Nabialek trick <\/a>will recognize it’s working under the hood. What you can achieve with the keywords parser can also be achieved with the Nabialek trick but not always as elegantly or as efficiently.<\/p>\n

<\/p>\n

The two examples presented below are included in the spirit repository and can be found in the folder :<\/p>\n

libs\/spirit\/repository\/example\/qi<\/pre>\n
Data members marked by keywords (options.cpp<\/a>)<\/h4>\n
For this small introduction we’ll consider parsing a program command line.<\/p>\n
Options are commonly passed to applications delimited by option keywords :<\/p>\n
\r\n\r\nmySuperCompiler --include includePath --define newSymbol=10 --output output.txt --define newSymbol2=20 --source mySourceFile\r\n\r\n<\/pre>\n
The order in which the options are specified doesn’t matter at all. The task of the parser we are going to write is to extract the individual options into some internal data structure we will use to control the program.<\/p>\n
Here are the structures we could use to hold the options passed to our command line :<\/p>\n
\r\n\/\/ A basic preprocessor symbol<\/pre>\r\ntypedef std::pair<std::string, int32_t> preprocessor_symbol;\r\n\r\nstruct program_options {\r\n   \/\/ symbol container type definition\r\n   typedef std::vector< preprocessor_symbol > preprocessor_symbols_container;<\/pre>\r\n   \/\/ include paths\r\n   std::vector<std::string> includes;\r\n   \/\/ preprocessor symbols\r\n   preprocessor_symbols_container preprocessor_symbols;\r\n   \/\/ output file name\r\n   boost::optional<std::string> output_filename;\r\n   \/\/ input file name\r\n   std::string source_filename;\r\n};\r\n\r\n<\/pre>\n
Of course \u00a0the structures are adapted to be compatible with fusion in order to get the data pulled into the structures easily.<\/p>\n
Now lets define our options rule:<\/p>\n
\r\n\r\nrule<const char *, program_options(), space_type> kwd_rule;\r\n\r\nkwd_rule %= kwd("--include")[\r\n                parse_string\r\n            ]\r\n          \/ kwd("--define") [\r\n                parse_string\r\n                >> (\r\n                    (lit('=') > int_) | attr(1)\r\n                   )\r\n            ]\r\n          \/ kwd("--output",0,1)[\r\n                parse_string\r\n            ]\r\n          \/ kwd("--source",1)[\r\n                parse_string\r\n            ]\r\n          ;\r\n<\/pre>\n
The first thing to notice here is that we used the %= operator. This means that the parsing construct we just wrote has an attribute type compatible with the attribute type of our adapted structure!<\/p>\n
This is one spot were the keyword parsing construct surpasses the Nabialek trick. The Nabialek trick just can’t do that.<\/p>\n
On the next lines we define our keyword parsing constructs.  Writing<\/p>\n
kwd("--include")[ parse_string ] <\/pre>\n
is equivalent to writing:<\/p>\n
lit("--inlude") > parse_string<\/pre>\n
The word “–include” must be followed by a string.<\/p>\n
The kwd directive<\/a> has the ability to be combined by using the \/ operator<\/a>. The kwd directive and the operator \/ work tightly together to achive the goal of attribute compatibility while using the Nabialek trick.<\/p>\n
One last thing to notice is the occurrence constraints which can be associated with a kwd directive. It works like the repeat directive and enables to add additional validation checks inside the keyword parsing loop.<\/p>\n
Writing<\/p>\n
kwd("--output",0,1)[ parse_string ] <\/pre>\n
means that the keyword “–output” may occur 0 or 1 times at most. If it occurs more than once the parser will fail.<\/p>\n
Writing<\/p>\n
kwd("--source",1)[ parse_string ] <\/pre>\n
means that the keyword “–source” must occur once and only once. This works just like the repeat directive.<\/p>\n
Using occurrence constraints doesn’t cost much on the runtime performance and gives the ability to easily enforce constraints which would be otherwise way much more difficult to formulate.<\/p>\n
The kwd directive also exists in a case insentive variant : ikwd. You can combine the kwd and ikwd freely inside the same keyword block at the cost of a small runtime overhead.<\/p>\n
Derived structures (derived.cpp<\/a>)<\/h4>\n
A recent post in the mailing list gave me the idea to provide an example of how the keyword parser can be used to produce different derived structures depending on keywords placed in the input.<\/p>\n
Here’s the problem as described by MM:<\/p>\n
“I have a case where I have a prefix string that will distinguish what will follow it.<\/p>\n
prefix string - struct members<\/pre>\n
this is what is read from the input stream.\u00a0I have a base struct and 5 derived D1..D5, each derived has a different prefix as a static const std::string member.\u00a0Parsing the prefix string tells me which struct D1..D5 I should parse after.\u00a0All these derived structs are fusion adapted. There is a rule for each of the derived.”<\/p>\n
To keep the example simple here are the classes we could consider:<\/p>\n
\r\n\r\nstruct base_type {\r\n    base_type(const std::string &name) : name(name)  {}\r\n\r\n    std::string name;\r\n    virtual std::ostream &output(std::ostream &os) const {\r\n        os<<"Base : "<<name;        return os;\r\n    }\r\n};\r\n\r\nstruct derived1 : public base_type {\r\n    derived1(const std::string &name, unsigned int data1) :\r\n        base_type(name)\r\n      , data1(data1)  {}\r\n\r\n    unsigned int data1;\r\n    virtual std::ostream &output(std::ostream &os) const {\r\n        base_type::output(os);\r\n        os<<", "<<data1;\r\n        return os;\r\n    }\r\n};\r\n\r\nstruct derived2 : public base_type {\r\n    derived2(const std::string &name, unsigned int data2) :\r\n        base_type(name), data2(data2)  {}\r\n\r\n    unsigned int data2;\r\n    virtual std::ostream &output(std::ostream &os) const    {\r\n        base_type::output(os);\r\n        os<<", "<<data2;\r\n        return os;\r\n    }\r\n};\r\n\r\nstruct derived3 : public derived2 {\r\n    derived3(const std::string &name, unsigned int data2, double data3) :\r\n      derived2(name,data2)\r\n    , data3(data3)\r\n    {}\r\n\r\n    double data3;\r\n    virtual std::ostream &output(std::ostream &os) const    {\r\n        derived2::output(os);\r\n        os<<", "<<data3;\r\n        return os;\r\n    }\r\n};\r\n\r\n<\/pre>\n
Our parse result must be a vector of pointers to our base class:<\/p>\n
std::vector<base_type*><\/pre>\n
To get that done, we’ll use semantic actions inside the kwd directive:<\/p>\n
\r\n\r\nkwd_rule = kwd("derived1")[\r\n              ('=' > parse_string > int_ )\r\n              [phx::push_back(_val,phx::new_<derived1>(_1,_2))]\r\n           ]\r\n         \/ kwd("derived2")[\r\n              ('=' > parse_string > int_ )\r\n              [phx::push_back(_val,phx::new_<derived2>(_1,_2))]\r\n           ]\r\n         \/ kwd("derived3")[\r\n              ('=' > parse_string > int_ > double_)\r\n              [phx::push_back(_val,phx::new_<derived3>(_1,_2,_3))]\r\n           ]\r\n           ;\r\n\r\n<\/pre>\n
This rule will construct new derived classes and append them to our result vector during parsing. The input parsed by this construct is of the form:<\/p>\n
 derived2 = "object1" 10 derived3= "object2" 40 20.0 <\/pre>\n
Keywords vs Nabialek trick<\/h4>\n
Here’s a small table to compare the features of the keyword parsing constructs and the Nabialek trick to help you decide which solution better suits your needs.<\/p>\n\n\n\n\t\n\t\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t
<\/th>Nabialek trick<\/th>Keywords parser<\/th>\n\t<\/tr>\n<\/thead>\n
Attribute propagation<\/td>no<\/td>yes<\/td>\n\t<\/tr>\n\t
Runtime modification of the keyword set<\/td>yes<\/td>no<\/td>\n\t<\/tr>\n\t
Occurrence constraints<\/td>not easily implented<\/td>yes<\/td>\n\t<\/tr>\n\t
Number of keyword limit<\/td>available runtime memory<\/td>BOOST_VARIANT_LIMIT_TYPES<\/td>\n\t<\/tr>\n<\/tbody>\n<\/table>\n\n
The keywords parsing construct can save a lot of typing over the Nabialek trick<\/a> and has in many cases even better performance. It also makes retrieving the parsed data into the program usable structures much easier as it supports attribute propagation. The main limitation of the keyword parser is the number of keywords a keyword block may contain ( limited by the maximum size of the variant type BOOST_VARIANT_LIMIT_TYPES).<\/p>\n
Share this:<\/h3>