C Tokenizer - Как это работает? - PullRequest
Новая
       4

C Tokenizer - Как это работает?

3 голосов
/ 30 июля 2010

Как это работает?

Я знаю, чтобы использовать его, вы передаете:

  • начало: строка (например, «Элемент 1, Элемент 2, Элемент 3»)
  • delim: строка разделителя (например, ",")
  • tok: ссылка на строку, которая будет содержать маркер
  • nextpos (необязательно): ссылка на позицию в оригиналестрока, в которой начинается следующий токен
  • sdelim (необязательно): указатель на символ, который будет содержать начальный разделитель токена
  • edelim (необязательно): указатель на символ, который будет содержать окончаниеразделитель токена

Код: 

#include <stdlib.h>
#include <string.h>

int token(char* start, char* delim, char** tok, char** nextpos, char* sdelim, char* edelim) {
    // Find beginning:
    int len = 0;
    char *scanner;
    int dictionary[8];
    int ptr;

    for(ptr = 0; ptr < 8; ptr++) {
        dictionary[ptr] = 0;
    }

    for(; *delim; delim++) {
        dictionary[*delim / 32] |= 1 << *delim % 32;
    }

    if(sdelim) {
        *sdelim = 0;
    }

    for(; *start; start++) {
        if(!(dictionary[*start / 32] & 1 << *start % 32)) {
            break;
        }
        if(sdelim) {
            *sdelim = *start;
        }
    }

    if(*start == 0) {
        if(nextpos != NULL) {
            *nextpos = start;
        }
        *tok = NULL;
        return 0;
    }

    for(scanner = start; *scanner; scanner++) {
        if(dictionary[*scanner / 32] & 1 << *scanner % 32) {
            break;
        }
        len++;
    }

    if(edelim) {
        *edelim = *scanner;
    }

    if(nextpos != NULL) {
        *nextpos = scanner;
    }

    *tok = (char*)malloc(sizeof(char) * (len + 1));

    if(*tok == NULL) {
        return 0;
    }

    memcpy(*tok, start, len);
    *(*tok + len) = 0;


    return len + 1;
}

Я получаю большую часть, за исключением:

dictionary[*delim / 32] |= 1 << *delim % 32;

и

dictionary[*start / 32] & 1 << *start % 32

Это волшебство?

Ответы [ 3 ]

4 голосов
/ 30 июля 2010

Поскольку каждый символ разделителя составляет 8 бит (sizeof(char) == 1 байт), он ограничен 256 возможными значениями.

Словарь разбит на 8 частей (int dictionary[8]), 32 варианта на единицу (sizeof(int) is> = 4 байта) и 32 * 8 = 256.

Это формирует 256-битную матрицу значений. Затем он включает флаг для каждого символа в разделителе (dictionary[*delim / 32] |= 1 << *delim % 32;). Индекс массива равен *delim / 32, или значение ASCII символа, разделенное на 32. Поскольку значение ASCII варьируется от 0 до 255, это деление дает значение от 0 до 7 с остатком. Остаток, какой бит включить, определяется операцией модуля.

Все, что это делает, - помечает определенные биты 256-битной матрицы как истинные, если соответствующий символ ASCII существует в разделителе.

Определение того, находится ли символ в разделителе, - это просто поиск в 256-битной матрице (dictionary[*start / 32] & 1 << *start % 32)

1 голос
/ 30 июля 2010

Они запоминают, какие символы произошли, создав таблицу битов размером 8 x 32 = 256, сохраненную в словаре. 

dictionary[*delim / 32] |= 1 << *delim % 32;

устанавливает бит, соответствующий проверкам * delim 

dictionary[*start / 32] & 1 << *start % 32

бит

0 голосов
/ 30 июля 2010

ОК, поэтому, если мы отправим строку "," для delimiter, тогда dictionary[*delim / 32] |= 1 << *delim % 32 будет dictionary[1] = 4096.Выражение dictionary[*start / 32] & 1 << *start % 32 просто проверяет наличие соответствующего символа.

Меня удивляет то, что они не используют прямое char сравнение.

...