Coverage of rules files generated by bison

I have a really huge bison rules file and was wondering if there is an easy way to get a coverage of those rules from the program behind.

I generate a parser with bison. Run the parser against different files and want to see which lines have been touched in the .yy file.

There's no official way to generate such a report, as far as I know. But it's possible to do, if you're willing to break into bison's internals a bit.

Note that you can only produce a coverage report for parser semantic actions. There's no other direct translation for "parser rules"; the rules are compiled into a state machine, and the correspondence from state to rule is many-to-many. But that will tell you how many times each rule was completed, which is probably what you want to know.

Also note that the parser does not distinguish between rule final semantic actions and mid-rule actions, since mid-rule actions are actually compiled into reduction actions for generated non-terminals.

The rest of this post is unofficial, and should not be relied on to work with all future versions of Bison. Nor will it work with other Bison skeletons (although it could presumably be adapted); I wrote based on the current release, version 3.8.2.

The easiest way to hook into the parser is to hijack the macro YY_REDUCE_PRINT, which is used by the trace facility to trace reduction actions. So it is executed every time a reduction takes place. That happens even if tracing is not compiled into the parser; in that case, the macro is defined as a no-op. YY_REDUCE_PRINT is not an official part of the interface, though, so its name and functionality might change without notice. Also, it's not officially available for customization, and the generated source makes no attempt to check if it was previously defined. So you have to wait until it has been defined in the parser template, and then redefine it. Of course, redefining it will make it unavailable for trace logs, so this is not compatible with debugging traces. It turns out that the ½initial-action code block is injected after the definition of YY_REDUCE_PRINT, so that's where I put the redefinition. That's not guaranteed either.

I tested the following code, very lightly, with a couple of recent bison versions (3.7.1 and 3.8.2), using the lalr1.cc skeleton. It seems to work, but your mileage may vary.

The code is very simple. First, the redefinition of YY_REDUCE_PRINT, which goes into your .yy file. You might want to make it conditional on some configuration macro, in order to retain the possibility of generating debug traces. All that the redefined YY_REDUCE_PRINT macro does is add one to a coverage histogram. (Here, drv is an instance of the parser driver, as per the Calc++ example):

%initial-action {
#undef YY_REDUCE_PRINT
#define YY_REDUCE_PRINT(Rule) drv.register_rule(Rule)
}

The histogram itself needs to be implemented; it can go into driver.hh and driver.cc:

Header:

  // Register execution of a semantic action.
  void register_rule(int rule);
  // Count of executions of each rule.
  std::vector<unsigned> rule_count;

Implementation:

void
driver::register_rule(int ruleno) {
  if (ruleno > 0) {
    if (ruleno > rule_count.size()) rule_count.resize(ruleno);
    ++rule_count[ruleno - 1];
  } 
}

The rule numbers correspond to the numbers in the generated report files. Rule 0 (the accepting rule) will not be counted.