Faster token table lookups

[Hans Aberg]

Token table lookups in the parser that Bison generates (cf. the manual, the
%token_table option & sec 4.2.1) can be speeded up if Bison writes a token
table with the names sorted alphabetically: A search in yytname takes now
average linear time; by contrast, a sorted table can be searched in at most
log_2 time.

The suggest that Bison writes another table with pairs
struct name_index_type {
  char* name;
  long index;
};
in an array
name_index_type yytname_index[] = { ... };
name_index_type yytname_index_size[] = ...;

where the "name" fields are sorted alphabetically, "index" is the index
number that Bison uses.

A search algorithm (in C) for such a sorted table by halving intervals is:

long find_sorted(name_index_type a[], unsigned long size, const char* s) {
  unsigned long low = 0, high = size;
  while (low != high) {
    int i = low + (high - low)/2;
    int c = std::strcmp(s, a[i].text);
    switch ((c > 0) - (c < 0)) {
      case -1: high = i; break;
      case 1: low = i + 1; break;
      default: return a[i].index;
    }
  }
  return -1;
}

which returns -1 if the lookup s was not found; otherwise the return is the
index of the found name in the table. -- I.e., one should call
   find_sorted(yytname_index, yytname_index_size, my_search_string);
to find which number Bison is using.

  Hans Aberg