Parsing NMEA with C++11/14 and variadic templates

The NMEA organisation defines its format as, “The NMEA 0183 Interface Standard defines electrical signal requirements, data transmission protocol and time, and specific sentence formats for a 4800-baud serial data bus. Each bus may have only one talker but many listeners.”.

It is commonly used by GNSS receivers to describe parameter data as latitude/longitude and other positioning data.

For our purposes we’ll describe it as a CSV format with variable length lines and fields that we want to parse. An example of a sentence is,

$GPGSA,A,3,15,13,21,18,,,,,,,,,5.4,4.0,3.5*3D
$GPGSV,2,1,07,13,81,101,29,15,56,291,27,18,17,318,32,21,10,291,18*70

As we can see we have either chars, ints, or floats delimited by commas and some fields are not present.

The goal is to parse these lines in a somewhat declarative way with static typechecking and in a generic way. For example, both sentences above should use the same code even though the lines have a different number of fields. In pseudocode,

char a;
int num;
float dop;
parse(a, num,...,dop)

for the first sentence above and

int a;
int b;
parse(a,b...)

for the second sentence.

The parse function should dispatch statically to the parser of either char, int, float with empty fields being skipped. This is exactly what variadic templates allows us to achieve,

template <class T, class... Ts>
constexpr void nmea_scanner(const std::string &format,
                            const std::string &sentence, T &t,
                            Ts &... ts) noexcept {
  auto beg = sentence.c_str() + format.size();
  auto end = sentence.c_str() + sentence.size() + 1;
  nmea_scanner_helper(beg, end, t, ts...);
}

The nmea_scanner_helper function can then traverse each of the fields on the line, eventually skipping them, and call the extractor function which then statically dispatches to the field parser function,

template <class FwdIt, class T, class... Ts>
constexpr void nmea_scanner_helper(FwdIt &beg, FwdIt end, T &t,
                                   Ts &... ts) noexcept {
  if (beg != end) {
    if (*beg == ',') {
      ++beg;
      if (*beg == ',') {
        return nmea_scanner_helper(beg, end, ts...);
      }
    }
    if (beg >= end || *beg == '*') {
      return;
    }
    extract(beg, end, t);
    return nmea_scanner_helper(beg, end, ts...);
  }
  __builtin_unreachable();
}

The helper function “recurses” if a field is empty (and therefore skipped), or when a field was extracted. The parsing work for each of our types is done in the extract function.

The extract function independently implements parsing for chars, ints, floats and other types. As an example,

template <class FwdIt, class T>
constexpr std::enable_if_t<std::is_same<T, short>::value>
extract(FwdIt &it, FwdIt, T &t) noexcept {
  std::size_t pos{0};
  t = static_cast<T>(std::stoi(it, &pos));
  it += pos;
}

There is a complete decoupling between the field parsing code and the structure of the file. You can find complete POC code demonstrating the above on Github.