QRS：匹配“.”以 UTF-8 格式

Posted on 2024-12-21

Feed.png

早在 12 月 13 日，我就在 Mastodon 上发布了一个挑战：在一个简单的 UTF-8 字节驱动的有限自动机中，需要多少个状态才能匹配正则表达式构造“ . ”，即“任何字符”？评论者安东尼·威廉姆斯回应道，我认为几乎是正确的，但我发现他的描述有点难以理解。在这篇文章中，我将深入探讨什么.实际上意味着，然后你需要多少个状态来匹配它。

答案让我很惊讶。显然，这只对那些对自动机争论、有问题的字符和 UTF-8 的细节感兴趣的人感兴趣。希望大家17人密切关注！

答案是……

四。或者五个，视情况而定。

什么是“Unicode 字符”？

它们由“代码点”表示，即 0 … 17×2 16范围内的数字，也就是说 1,114,112 个可能的值。事实证明，您实际上并不想匹配所有这些；稍后会详细介绍。

有多少个州？

Quamina 是一个“字节级自动机”，这意味着它处于某种状态，它读取一个字节，在映射中查找该字节的值，产生下一个状态，或者nil ，这意味着不匹配。重复直到匹配或失败。

我们在这里谈论什么字节？我们谈论的是 UTF-8 字节。如果您不理解 UTF-8，其余部分将会很困难。二十一年前，我写了一篇简短的解释文章，名为“字符与字节” 。我现在假设您了解 UTF-8 并且知道代码点被编码为 1 到 4 个字节的序列。

我们来数数吧！

  1. 当您成功匹配一个代码点时，您将移动到自动机尝试匹配下一个代码点的部分；我们将此条件称为MATCHED 。

    （从这里开始，所有数字都是十六进制，我将跳过前导 0x。并且所有范围都包含在内。）

  2. 在多字节字符中，除了第一个字节之外的所有 UTF-8 字节都具有类似10XX XXXX的位掩码，因此有 6 个有效位，因此有 2 6或 64 个不同的可能值，范围从 80-BF 不等。

  3. 有一个开始状态。它将字节值 00-7F（如 ASCII）映射到MATCHED 。这是我们的第一个状态，我们已经处理了所有的单字节代码点。

  4. 在开始状态中，32字节值C0-DF（所有这些值都开始110用信号通知两字节代码点）被映射到最后状态。在Last状态下，64 个值 80-BF 被映射到MATCHED 。这会处理所有两字节代码点，并且我们最多有两种状态。

  5. 在开始状态中，16字节值E0-EF（所有这些值开始1110用信号通知三字节代码点）被映射到LastInter状态。在该状态下，64 个值 80-BF 被映射到最后一个状态。现在我们达到了三种状态，并且我们已经处理了三字节代码点。

  6. 在开始状态中，8 个字节值 F0-F7（所有这些值都以 11110 开始，表示一个四字节代码点）被映射到FirstInter状态。在该状态下，64 个值 80-BF 被映射到LastInter状态。现在我们已经处理了四种状态的所有代码点。

但是等等！

我上面提到过不想匹配所有代码点。 “等等，”你说，“为什么你不想最大限度地包容呢？！”我将再次链接到Unicode 字符库子集，这是我与他人共同编写的一份文档，该文档正在 IETF 中通过，并且可能在某一年成为 RFC。我不会试图将一份草稿总结得简短而清晰。我只想说，有充分的理由省略几种不同风格的代码点。

最有害的代码点可能是“代理”，U+D800-U+DFFF。如果你想了解它们是什么以及为什么它们不好，请阅读《曲目子集》草稿，或者相信我的话。如果您要按照 UTF-8 规则对它们进行编码（UTF-8 规范规定您不允许这样做），则下限和上限将为 ED、A0、80 和 ED、BF、BF。

Go 的 UTF-8 实现同意“代理是坏的”和“UTF-8 规范是好的”，并且断然拒绝将这些 UTF-8 序列转换为代码点，反之亦然。生成的代码点子集甚至有一个朗朗上口的名称：Unicode 标量。案子已经结案了吧？

错误的。因为 JSON 是在我们考虑这些问题之前设计的，所以明确表示可以包含任何代码点，包括代理项。 Quamina 用于匹配 JSON 数据。所以，标准之争！

我在这里有点不公平。我确信，如果 Doug Crockford 现在而不是 2001 年发明 JSON，他会排除代理项，并可能排除该子集文档中讨论的其他一些有问题的代码点。

不管怎样，Quamina 会选择 Go 并排除代理人。任何 RFC8259 纯粹主义者都可以随意指责我背离标准，我会同意你的观点，但不会改变 Quamina。事实上，事实并非如此；在某些时候，我可能会添加一个更具限制性的选项，并且排除的不仅仅是代理。

这意味着现在我们必须回到本文的开头并弄清楚需要多少个状态来匹配“ ” . “ 让我们来看看…

  1. 开始状态发生了一些变化。请参阅上面列表中的#5。它不是将所有 E0-EF 映射到LastInter状态，而是将该范围内的一个字节 ED 映射到我们将调用的新状态，让我们看看ED怎么样。

  2. 在ED中，就像在LastInter中一样，80-9F 映射到Last 。但 A0-BF 没有映射到任何东西，因为代理就在这条路径上。

因此，采用 Unicode 标量美德之路意味着我需要五个状态，而不是四个。

原文： https://www.tbray.org/ongoing/When/202x/2024/12/18/Matching-Dot-in-UTF8