{"id":392,"date":"2009-11-17T03:41:59","date_gmt":"2009-11-17T11:41:59","guid":{"rendered":"http:\/\/boost-spirit.com\/home\/?page_id=392"},"modified":"2011-01-09T18:00:18","modified_gmt":"2011-01-10T02:00:18","slug":"nabialek-trick","status":"publish","type":"page","link":"http:\/\/boost-spirit.com\/home\/articles\/qi-example\/nabialek-trick\/","title":{"rendered":"Nabialek trick"},"content":{"rendered":"

This sample is a port of the original “Nabialek trick” from classic Spirit. See the cpp file here<\/a>.<\/p>\n

Update:<\/h4>\n

Thomas Bernard did some performance investigations and concluded that the older version of this article which stores the rules directly in the symbol-table is sub-optimal. This updated article uses rule pointers instead.<\/p>\n

Thomas notes:<\/p>\n

I’ve done some more investigation on the performance issue the proposed Nabialek trick implementation shows. With the help of callgrind I confirmed that the main performance hit comes from copying the parser out of the symbol table when a successful parse occurs into the rule local variable. (If anybody is interested I can provide the callgrind results)<\/p>\n

There is a very simple way to prevent that: use pointers. This time the optimization I propose works \ud83d\ude42<\/p>\n

The modifications to the proposed implementation are simple:<\/p>\n

    \n
  1. Replace the symbol table definition to use rule pointers instead of normal rules<\/li>\n
  2. Replace the rule local variable type to be a pointer to a rule instead of a rule<\/li>\n
  3. Adapt the call to the lazy parser to take into account the modified local variable type<\/li>\n<\/ol>\n

    Using pointers prevents copying the rules around and gives about three times faster parsing speed in the most simple cases. The speed improvement can be much bigger as the complexity of the rules stored in the symbol table increases.<\/p><\/blockquote>\n

    This technique, I’ll call the “Nabialek trick” (from the name of its inventor, Sam Nabialek), can improve the rule dispatch from linear non-deterministic to deterministic. The trick applies to grammars where a keyword (operator, etc), precedes a production. There are lots of grammars similar to this:<\/p>\n

    \r\nr =\r\n        keyword1 >> production1\r\n    |   keyword2 >> production2\r\n    |   keyword3 >> production3\r\n    |   keyword4 >> production4\r\n    |   keyword5 >> production5\r\n    \/*** etc ***\/\r\n    ;\r\n;\r\n<\/pre>\n
    The cascaded alternatives are tried one at a time through trial and error until something matches. The Nabialek trick takes advantage of the symbol table’s search properties to optimize the dispatching of the alternatives. For an example, consider this grammar:<\/p>\n
    \r\none = id;\r\ntwo = id >> ',' >> id;\r\n\r\nstart = *("one" >> one | "two" >> two);\r\n<\/pre>\n
    There are two rules (one and two). When “one” is recognized, rule ‘one’ is invoked. When “two” is recognized, rule ‘two’ is invoked.<\/p>\n
    Here’s the corresponding grammar using the Nabialek trick (see nabialek.cpp<\/a>):<\/p>\n
    \r\none = id;\r\ntwo = id >> ',' >> id;\r\n\r\nkeyword.add\r\n    ("one", &one)\r\n    ("two", &two)\r\n    ;\r\n\r\nstart = *(keyword[_a = _1] >> lazy(*_a));\r\n<\/pre>\n
    The grammar works as follows. keyword is a symbol table with two slots containing rule pointers:<\/p>\n
    \r\nqi::symbols<char, qi::rule<Iterator, ascii::space_type>*> keyword;\r\n<\/pre>\n
    This is initialized to contain the address of rules “one” and “two”.<\/p>\n
    one, two, id, start are rules which are declared as follows:<\/p>\n
    \r\nqi::rule<Iterator, ascii::space_type> id, one, two;\r\nqi::rule<Iterator, ascii::space_type,\r\n    qi::locals<qi::rule<Iterator,\r\n        ascii::space_type>*> > start;\r\n<\/pre>\n
    The start rule has a local variable \u2014a rule pointer. In this example, when we enter the start rule, we create a temporary local variable. When a valid keyword is matched, notice that the semantic action stores a pointer to the rule we initially stored in the symbol table into the local variable with this code:<\/p>\n
    \r\nkeyword[_a = _1]\r\n<\/pre>\n
    _a refers to the local variable and _1 refers to the attribute of keyword \u2014the rule pointer contained in the symbol slots.<\/p>\n
    Now that the local variable (referred to by _a) contains a pointer to the rule we want to continue parsing with, the next thing to do is call it. This is done by the lazy pseudo parser:<\/p>\n
    \r\n>> lazy(*_a)\r\n<\/pre>\n
    The dynamic grammar parses inputs such as:<\/p>\n
    \r\n"one only"\r\n"one again"\r\n"two first, second"\r\n<\/pre>\n
    The cool part is that the rule we want to parse with is dynamically chosen at runtime depending on what the symbol table contains. If it got a “one” then we use the ‘one’ rule. If it got “two”, then we use the ‘two’ rule. Very nifty! This technique should be very fast, especially when there are lots of keywords. It would be nice to add special facilities to make this easy to use. I imagine:<\/p>\n
    \r\nr = keywords >> rest;\r\n<\/pre>\n
    where keywords is a special parser (based on the symbol table) that automatically sets its RHS (rest) depending on the acquired symbol. This, I think, is mighty cool! Someday perhaps…<\/p>\n
    Now, that last line was written in 2003. Will someone come forward and finally do it? \ud83d\ude42<\/p>\n
    Share this:<\/h3>