优化单词解析器

Question

语境:

我有一个代码/文本编辑器,而不是我想要优化.目前,该程序的瓶颈是语言解析器,而不是扫描所有关键字(有不止一个,但它们的编写方式基本相同).

在我的计算机上,编辑器会在1,000,000代码行周围延迟文件.在像Raspberry Pi这样的低端计算机上,延迟开始得更快(我不记得确切,但我想的10,000是代码行).虽然我从来没有看到比1,000,000代码行更大的文档,但我确信它们在那里,我希望我的程序能够编辑它们.

题:

这引出了一个问题:在大型动态字符串中扫描单词列表的最快方法是什么？

以下是可能影响算法设计的一些信息:

1. 关键字
2. 限定字符允许成为关键字的一部分(我称之为限定符)
3. 大字符串

瓶颈的解决方案:

这(大致)是我目前用于解析字符串的方法:

// this is just an example, not an excerpt
// I haven't compiled this, I'm just writing it to
// illustrate how I'm currently parsing strings

struct tokens * scantokens (char * string, char ** tokens, int tcount){

    int result = 0;
    struct tokens * tks = tokens_init ();

    for (int i = 0; string[i]; i++){

        // qualifiers for C are: a-z, A-Z, 0-9, and underscore
        // if it isn't a qualifier, skip it

        while (isnotqualifier (string[i])) i++;

        for (int j = 0; j < tcount; j++){

            // returns 0 for no match
            // returns the length of the keyword if they match
            result = string_compare (&string[i], tokens[j]);

            if (result > 0){ // if the string matches
                token_push (tks, i, i + result); // add the token
                // token_push (data_struct, where_it_begins, where_it_ends)
                break;
            }
        }

        if (result > 0){
            i += result;
        } else {
            // skip to the next non-qualifier
            // then skip to the beginning of the next qualifier

            /* ie, go from:
                'some_id + sizeof (int)'
                 ^

            to here:
                'some_id + sizeof (int)'
                           ^
            */
        }
    }

    if (!tks->len){
        free (tks);
        return 0;
    } else return tks;
}

---

可能的解决方案:

---

上下文解决方案:

我正在考虑以下事项:

• 扫描一次大字符串,并在每次有用户输入时添加一个功能来评估/调整标记标记(而不是一遍又一遍地重新扫描整个文档).我希望这将解决瓶颈,因为涉及的解析要少得多.但是,它并没有完全修复程序,因为初始扫描可能还需要很长时间.

• 优化令牌扫描算法(见下文)

我也考虑过,但拒绝了这些优化:

• 扫描仅在屏幕上的代码.虽然这可以解决瓶颈问题,但它会限制查找比屏幕启动时更早出现的用户定义标记(即变量名称,函数名称,宏)的能力.
• 将文本切换为链接列表(每行一个节点),而不是单片阵列.这并没有真正帮助瓶颈.虽然插入/删除会更快,但索引访问的丢失会降低解析器的速度.我认为,单个阵列也比缓存列表更容易被缓存.
• 为每种语言硬编码扫描令牌功能.虽然这可能是性能的最佳优化,但从软件开发的角度来看,它似乎并不实用.

建筑解决方案

使用汇编语言,解析这些字符串的更快方法是将字符加载到寄存器中,并一次比较它们4或8字节.还有一些必须考虑的额外措施和预防措施,例如:

• 架构是否支持未对齐的内存访问？
• 所有字符串必须是规模s,其中s % word-size == 0,以防止侵犯阅读
• 其他？

但这些问题似乎很容易修复.唯一的问题(除了通常用汇编语言编写的问题)是它不是一个算法解决方案,而是一个硬件解决方案.

算法解决方案:

到目前为止,我已经考虑让程序重新排列关键字列表,以使二进制搜索算法更加可能.

我考虑重新安排它们的一种方法是切换关键字列表的尺寸.这是一个例子C:

// some keywords for the C language

auto  // keywords[0]
break // keywords[1]
case char const continue // keywords[2], keywords[3], keywords[4]
default do double
else enum extern
float for
goto
if int
long
register return
short signed sizeof static struct switch
typedef
union unsigned
void volatile
while

/* keywords[i] refers to the i-th keyword in the list
 *
 */

切换二维数组的尺寸会使它看起来像这样:

    0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
    1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
  -----------------------------------------------------------------
1 | a b c c c c d d d e e e f f g i i l r r s s s s s s t u u v v w
2 | u r a h o o e o o l n x l o o f n o e e h i i t t w y n n o o h
3 | t e s a n n f   u s u t o r t   t n g t o g z a r i p i s i l i
4 | o a e r s t a   b e m e a   o     g i u r n e t u t e o i d a l
5 |   k       i u   l     r t           s r t e o i c c d n g   t e
6 |           n l   e     n             t n   d f c t h e   n   i
7 |           u t                       e               f   e   l
8 |           e                         r                   d   e

// note that, now, keywords[0] refers to the string "abccccdddeeefffiilrr"

这使得使用二进制搜索算法(甚至是普通的强力算法)更有效.但它只是每个关键字中第一个字符的单词,之后什么都不能被视为"排序".这可能对像编程语言这样的小词组有帮助,但对于更大的单词集(例如整个英语语言)来说,这是不够的.

是否有更多可以改进此算法？

是否有其他方法可以提高性能？

笔记:

来自SO的这个问题对我没有帮助.Boyer-Moore-Horspool算法(据我所知)是一种在字符串中查找子字符串的算法.由于我正在解析多个字符串,我认为还有更多的优化空间.

Answer 1

Aho-Corasick 是一个非常酷的算法，但对于关键字匹配来说它并不理想，因为关键字匹配是对齐的；你不能有重叠的匹配，因为你只匹配一个完整的标识符。

对于基本标识符查找，您只需根据关键字构建一个字典树（请参阅下面的注释）。

您的基本算法很好：找到标识符的开头，然后查看它是否是关键字。改进这两个部分很重要。除非您需要处理多字节字符，否则查找关键字开头的最快方法是使用包含 256 个条目的表，每个可能的字符对应一个条目。有以下三种可能：

1. 该字符不能出现在标识符中。（继续扫描）

2. 该字符可以出现在标识符中，但没有关键字以该字符开头。（跳过标识符）

3. 角色可以启动关键字。（开始遍历 trie；如果无法继续遍历，则跳过标识符。如果遍历找到关键字并且下一个字符不能在标识符中，则跳过标识符的其余部分；如果可以在标识符中，请尝试继续如果可能的话步行。）

实际上，步骤 2 和步骤 3 非常接近，因此您实际上并不需要特殊的逻辑。

上述算法存在一些不精确性，因为在很多情况下，您会发现一些看起来像标识符但在语法上不可能的东西。最常见的情况是注释和引用的字符串，但大多数语言还有其他可能性。例如，在 C 中，您可以使用十六进制浮点数；虽然不能仅从 构造 C 关键字[a-f]，但用户提供的单词可能是：

0x1.deadbeef

另一方面，C++ 允许用户定义的数字后缀，如果用户将它们添加到列表中，您可能很想将其识别为关键字：

274_myType

除此之外，每次用户在编辑器中键入字符时解析一百万行代码确实不切实际。您需要开发某种缓存标记化的方法，最简单且最常见的方法是按输入行进行缓存。将输入行保留在链接列表中，并且每个输入行还在该行的开头记录分词器状态（即，无论您是在多行引用字符串中、多行注释还是其他一些特殊的情况）词汇状态）。除了一些非常奇怪的语言之外，编辑不会影响编辑之前的行的标记结构，因此对于任何编辑，您只需要重新标记已编辑的行以及标记器状态已更改的任何后续行。（注意在多行字符串的情况下不要过于努力：它可能会产生大量视觉噪音来翻转整个显示，因为用户输入了未终止的引号。）

注意：对于少量（数百）个关键字，完整的 trie 并不会真正占用那么多空间，但在某些时候您需要处理臃肿的分支。一种非常合理的数据结构是三元搜索树（尽管我将其称为三元搜索树），如果您仔细对待数据布局，它可以表现得很好。