[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Faster token table lookups
From: |
Hans Aberg |
Subject: |
Faster token table lookups |
Date: |
Fri, 15 Dec 2000 18:51:00 +0100 |
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
- Faster token table lookups,
Hans Aberg <=
- Re: Faster token table lookups, Akim Demaille, 2000/12/19
- Re: Faster token table lookups, Hans Aberg, 2000/12/19
- Re: Faster token table lookups, Akim Demaille, 2000/12/20
- Re: Faster token table lookups, Hans Aberg, 2000/12/20
- Re: Faster token table lookups, Hans Aberg, 2000/12/22
- Re: Faster token table lookups, Akim Demaille, 2000/12/22
- Re: Faster token table lookups, Hans Aberg, 2000/12/22
- Re: Faster token table lookups, Hans Aberg, 2000/12/22