Using a C++ Flex Lexer with a C++ Bison Parser

I recently found myself revisiting lexing and parsing as part of my research. It's one of those cases where I would get away with ad-hoc parsing with line-splitting and regular expression matching, but the canonical alternative might ultimately turn out to be worth some extra effort for a number of reasons.

Many years ago, I wrote a SQL DDL parser as part of some object-relational mapping research into a “mutual containment” object model for transparently representing junction tables in relational databases. Even if I do say so myself, it was a neat idea. I don't know if anyone else has since thought of it independently and implemented it.

So, I decided to revisit flex and bison, the most popular versions of the venerable and classic compiler construction tools, lex and yacc. This time around, though, I anticipated a possible need for two parser/lexer subsystems, so I was interested in the C++ capabilities of both tools, since the “vanilla” C code they emit uses global variables.

The GNU Bison Manual has A Complete C++ Example that, unfortunately, rather narrowly interprets what it means to be “complete C++ example” to mean “an example where the bison bits are in C++”, and uses the vanilla flex lexer with global variables.

I found a few examples of using flex and bison with C++, but even the best of them only address one or the other, go off on irrelevant tangents, are short on explanation, contain outright misleading comments, use deprecated constructs, or all of the above.

All I wanted, was the minimal example of how to use a C++ flex lexer with a C++ bison parser. Some kind of “addendum” to the “complete” C++ example from the bison manual would be perfect!

*Crickets*.

So now, ladies and gentlemen, for your enjoyment, I have added to my Bitbucket “miscellany”, such an elucidation of Modifying the Bison “Complete C++ Example” to Use a C++ Flex Lexer as I formerly desired.

It's not as easy as it sounds.

Announcing “ftrace”

If you've ever had to understand someone else's largely undocumented code, you may have wished there was some way of narrowing down your search through the source to a simple case or two until you had learned your way around.

I'm in that situation with the Linux “perf tools”, which I'm trying to use in my research. I'm reasonably familiar with strace and ltrace, which trace system and library calls, respectively, but I don't really care about these: I just want to trace the “local” function calls so that I can get a handle on how perf works. That should be easy, right?

Mmm... no. It turns out that I'm not the first person to have this problem.

One of the suggestions on StackOverflow, from Johannes Schaub, is to use readelf to identify all the functions symbols, set breakpoints for all of them in gdb, and retrieve the last frame of the backtrace at each breakpoint. Nice idea. Horribly slow, but a nice idea.

So, since I've been using OpenGrok to browse the kernel tools source, so it would be nice to be able to integrate with it, like this:

OpenGrok with 'ftrace'

It would be really nice to have a callgraph from a particular program invocation, like this:

Callgraph from 'ftrace' via GraphViz 'dot'

So, I wrote a few hundred lines of Python to do what Johannes suggested, plus a bit more. After the pattern of strace and ltrace, I called it ftrace, and you can get it from github:

• Emmet's ftrace on GitHub 

It's horribly slow, it's hacky, but does what I need for the time being.

Arithmetic Intensity Origins

Arithmetic intensity is a key concept in the Roofline Model [Williams et al., 2009], which is important to my own research, and has definitely gone mainstream, making it into the lexicon of computer and computational science and the latest editions of John Hennessey and Dave Patterson's highly-respected books, “Computer Architecture: A Quantitative Approach” and “Computer Organization and Design”. In both books — the former on p.286 et seq., and the latter on p.668 et seq., — the treatment cites the same “Williams et al. 2009”, which inadvertently kinda sorta gives the impression that the idea of arithmetic intensity is due to them (in this case, the “et al.” is Andrew Waterman and Dave Patterson). This seems odd — I would have thought that the term, “arithmetic intensity”, must have been around long before the Roofline Model — but, having been introduced to the term around that time, I couldn't be sure. Where does this term originate?

As it happens, “arithmetic intensity” is a surprisingly new term. Looking back through the literature with Google Scholar and CiteSeerX, it seems that the first occurrence in computer/computational science might have been as early as 1992 [Walter, 1992], but in that case, it seems most likely that it was a rhetorical flourish — synonymous with “containing lots of arithmetic” — rather than a term intended to be coined with any semblance of a consistent technical meaning. It essentially lay dormant for almost 10 years before resurfacing in a Stanford whitepaper by Bill Dally, Pat Hanrahan, and Ron Fedkiw in 2001, where it is loosely defined:

This in turn enables architectures with a high degree of arithmetic intensity, that is applications with a high ratio of arithmetic to memory bandwidth.

In 2002, it appears about half-a-dozen times [Dally, Kapasi et al., Owens et al., Purcell et al., Schröder, Jayasena et al.]. In all but one case in publications (formal or otherwise) about stream computing and GPGPU computing originating at Stanford. In the immediately following years, the term took off, with over 1,000 occurrences in 2012 (see Figure 1).

Figure 1: Occurrences in Search vs. Year

So, it seems that someone in Stanford, perhaps Bill Dally, has a pretty good claim on coining the term “arithmetic intensity” with its current meaning around 2001.