C语言分词器 - 它是如何工作的？

Question

这是如何工作的？

我知道要使用它，您需要传入以下参数：

• start: 字符串（例如 "项目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

这是魔法吗？

- Bob Fincheimer

---

我知道那两行代码用于查找分隔符，但是它是不是没有通过循环遍历分隔符字符串来实现的？ - Bob Fincheimer

Answer 1

由于定界符的每个字符都是8位（sizeof(char) == 1字节），因此它仅限于256个可能的值。

字典被分成8个部分（int dictionary[8]），每个部分有32个可能性（sizeof(int)大于或等于4字节）且32 * 8 = 256。

这形成了一个256位值矩阵。然后打开定界符中每个字符的标志（dictionary[*delim / 32] |= 1 << *delim % 32;）。数组的索引是*delim / 32，即字符的ASCII值除以32。由于ASCII值范围从0到255，因此该除法产生的值为0到7，有余数。余数是决定要打开哪个位的模运算结果。

所有这些只是将256位矩阵的某些位标记为true，如果相应的ASCII字符存在于定界符中。

然后确定一个字符是否在定界符中只是在256位矩阵中查找（dictionary[*start / 32] & 1 << *start % 32）。

- Brandon Horsley

Answer 2

它们通过在字典中存储一个8 x 32 = 256位的表来存储已出现的字符。

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

设置与*delim对应的位

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

检查位

- deinst

Answer 3

好的，如果我们将字符串","作为delimiter发送，则dictionary[*delim / 32] |= 1 << *delim % 32将是dictionary[1] = 4096。表达式dictionary[*start / 32] & 1 << *start % 32仅检查匹配字符。

让我感到困惑的是，为什么他们不使用直接的char比较。

- ChaosPandion