词法分析器的规格是什么？
What's the specification of a lexer?
有人问我以下问题：
Given two token rules:
A := aaa
B := aaaa
The output for text 'aaaaaaaaa' (nine a's) is
B (aaaa); B (aaaa); unknown (a)
Rather than
A (aaa); A (aaa); A (aaa)
我知道这是最大咀嚼原理的结果。但是我怎样才能恰当地陈述词法分析器的正确行为呢？具体来说，我被问到“为什么输出应该是第一个，而不是第二个似乎更合理？”
我试图寻找很多文献，但他们只描述了最大蒙克算法的工作原理。即便如此，如果有人能提出一些参考，那将是有帮助的。
这是个好问题。
没有词法分析器的正式定义；这是 pattern，不是标准。并且使用 maximal munch 是一种启发式方法，而不是绝对规则。但这是一个很好的启发式方法：最大咀嚼量 几乎总是 正确的做法。
但“几乎总是”不是“总是”，许多语言都有最大咀嚼的例外。
一个非常常见的例子，可以追溯到（至少）Modula-2，是范围运算符 ..，通常与整数操作数一起使用，因此 0..99 表示范围从 0 到99.（语义因语言而异。）在大多数语言中，maximal munch 会将 0..99 解释为两个浮点常量（0. 和 .99），而不是组成的三个标记范围（0、.. 和 99）。所以这必须作为最大咀嚼的例外处理。
C++ 还有一个例外。当二合字母被添加到语言中后，就可以将 [ 写成 <:；与 trigraphs 不同，digraphs 只是标记，因此应适用 maximal munch。但是，::在C++中用作namespace分隔符，而::name表示“top-levelnamespace中的name”（如反对 namespaces active because of a using declaration）。许多已经存在的程序包括使用这种语法的模板扩展——Template<::classname>——如果 <: 突然被解释为 [ 的语法等价物，这些将成为语法错误。所以对序列 <:: 的 maximal munch 做了一个例外，它必须是两个标记 < :: 除非 下一个字符是 > 或 :。所以我们有 <::a ⇒ < :: a 但 <:::a ⇒ <: :: a 和 <::> ⇒ <: :>（即[]）。
还有其他例子。
(F)lex 通过使用稍微更灵活的“匹配”定义来处理这些异常，该定义仍然取决于最大 munch 启发式算法。
一个 (f)lex 模式可以包含一个（未加括号的）/ 运算符。 / 通常称为“尾随上下文”运算符，但这并不准确。 / 不改变匹配的字符；它的作用是从匹配的标记中排除 / 之后的匹配部分。因此，C++ 的 (f)lex 扫描器可能包含以下规则：
< { return T_LT; }
<: { return T_LT_COLON; }
</::[^:>] { return T_LT; }
因此，输入 <::a 将匹配所有三种模式。由于 maximal munch，最后一条规则将获胜，但是从该匹配中得到的标记 return 只是 < 而不是完整的 four-character 匹配。这意味着下一次扫描将从重新扫描 ::a 开始（导致检测到 :: 标记）。另一方面，输入 <:::a 不会匹配最后一个模式，因此扫描器将不得不回溯到实际匹配的最长模式：<:.
可以使用类似的技巧来确保具有范围（例如Swift）的语言中的 2..3 不匹配浮点模式：
[[:digit:]]+"."[[:digit:]] { ... return T_FLOAT; }
[[:digit:]]+/".." { ... return T_INTEGER; }
同样，2..3 的最长匹配是第二个匹配，因此 maximal munch 选择它。但是令牌 returned 只是 2；为下一个标记重新扫描尾随上下文。
然而，还有另一个 class 最大的 munch 异常，只能通过依赖句法上下文的词法分析来处理。例如，EcmaScript（和其他语言，包括 Awk）允许以 / 字符开头的正则表达式文字。但是，/ 也可能是除法运算符或 /= 运算符的第一个字符。 （它也可能开始注释，但由于正则表达式不能以 * 开头，所以这种情况是没有问题的。）语言语法有效地定义了两个互斥的上下文：
- 在“运算符”上下文中，中缀或后缀运算符是可能的，而变量或文字等操作数则不是。
- 在“操作数”上下文中，可以使用操作数或前缀运算符，但不能使用其他运算符。
因此 解析器 始终知道下一个标记是否可能是除法运算符，以及何时可能是正则表达式。但是它没有一个很好的方式来将这个事实传达给词法分析器。 （解析器依赖于先行标记的事实使场景进一步复杂化：为了让解析器调用词法分析器并指示是使用运算符还是正则表达式规则，解析器需要知道 before 它读取先行标记。）
maximal munch 的另一组明显的句法例外是模棱两可的双右括号，其中最臭名昭著的可能是 C++ 模板参数。当模板首次添加到 C++ 时，我们需要小心避免在没有干预 space 的情况下关闭两个打开的模板特化，以避免 >> 被识别为 right-shift 运算符。塔很烦人，也没有什么必要；很少有 >> 可以用两种不同方式解释的表达式，并且在几乎所有此类表达式中，其中一种可能性是非常人为的。因此，为了让大多数 C++ 程序员松一口气（以及 C++ 词法分析器作者的烦恼），标准最终被更改为允许 >> 关闭两个开放的模板特化，而不是强制将其解释为句法（或语义上）无效的右移。 （请注意，这种情况不必由词法分析器处理。词法分析器可以 return 单个 >> 标记，将其留给解析器使用该单个标记来关闭两个开放的特化。那语法有点复杂，但不是难以忍受。）
所以，最大咀嚼量并不是普遍的。此外，有时会提出词法分析器的建议，这些词法分析器可以通过生成多个可能的标记流来处理不明确的词典，这与 GLR/GLL 解析器可以生成多个可能的解析树的方式非常相似。事实上，一种 often-suggested 可能性是“无扫描器”解析器，其中词法分析只是集成到语法中。如果 GLR/GLL 解析器可用，词法分析往往会破坏对 lookahead 的需求这一事实将不再是 show-stopper。 （据称，无扫描器解析也适用于 PEG 语法。）
另一方面，处理并行标记流会显着增加解析时间，甚至达到需要输入长度的二次方的时间（尽管实际语法不应该发生这种情况）。我认为这让我们回到了最初问题中的例子。
上面给出的所有示例都显示了涉及两个连续标记的与 maximal munch 的偏差（在某种程度上它们是与 maximal munch 的偏差），这增加了词法分析的复杂性，但不会对计算产生太大影响复杂。但是在 OP 中建议的语法中，将 aaaaaaaaa 识别为以 aaa 标记而不是 aaaa 开始需要向前看不止一个标记（因为 aaaaaaaa 和 aaaaaaaaaa 应该以 aaaa).
开头
除了可能对解析器提出额外的计算要求外，这种 non-local 消歧会给人类 reader（或作者）带来认知负担，他们通常 best-served一个功能易于预测的解析器，即使它有时无法找到潜在的解析器。
a+++++b 的 C 示例浮现在脑海中；偶尔会出现这样的问题，即为什么不将其解析为 a++ + ++b，这是唯一可能有意义的解析。我认为这里的答案与其说是“因为最大的咀嚼”，不如说是“因为大多数代码 readers 不会看到该解析”。 maximal munch 的一大优点，除了它的计算价值之外，就是它易于解释和预测。
其实很简单。当词法分析器（实现最长 match/maximal munch 原则）处理输入字符时，它会根据其他标记相互依赖 为每个标记做出决定。这意味着，在找到第一个可能的最长匹配项 aaaa 之后，第一个标记就可以由解析器进行处理了。然后词法分析器再次开始搜索另一个标记，并再次找到 aaaa。之后，由于剩余的输入字符串不足以匹配任何token，因此剩余的单个a不被识别为token。
第二个结果是可能的，如果词法分析器搜索 whole 输入的最佳匹配以转换为标记，而不是有问题的最长匹配。
有人问我以下问题：
Given two token rules:
A := aaa
B := aaaa
The output for text 'aaaaaaaaa' (nine a's) is
B (aaaa); B (aaaa); unknown (a)
Rather than
A (aaa); A (aaa); A (aaa)
我知道这是最大咀嚼原理的结果。但是我怎样才能恰当地陈述词法分析器的正确行为呢？具体来说，我被问到“为什么输出应该是第一个，而不是第二个似乎更合理？”
我试图寻找很多文献，但他们只描述了最大蒙克算法的工作原理。即便如此，如果有人能提出一些参考，那将是有帮助的。
这是个好问题。
没有词法分析器的正式定义；这是 pattern，不是标准。并且使用 maximal munch 是一种启发式方法，而不是绝对规则。但这是一个很好的启发式方法：最大咀嚼量 几乎总是 正确的做法。
但“几乎总是”不是“总是”，许多语言都有最大咀嚼的例外。
一个非常常见的例子，可以追溯到（至少）Modula-2，是范围运算符 ..，通常与整数操作数一起使用，因此 0..99 表示范围从 0 到99.（语义因语言而异。）在大多数语言中，maximal munch 会将 0..99 解释为两个浮点常量（0. 和 .99），而不是组成的三个标记范围（0、.. 和 99）。所以这必须作为最大咀嚼的例外处理。
C++ 还有一个例外。当二合字母被添加到语言中后，就可以将 [ 写成 <:；与 trigraphs 不同，digraphs 只是标记，因此应适用 maximal munch。但是，::在C++中用作namespace分隔符，而::name表示“top-levelnamespace中的name”（如反对 namespaces active because of a using declaration）。许多已经存在的程序包括使用这种语法的模板扩展——Template<::classname>——如果 <: 突然被解释为 [ 的语法等价物，这些将成为语法错误。所以对序列 <:: 的 maximal munch 做了一个例外，它必须是两个标记 < :: 除非 下一个字符是 > 或 :。所以我们有 <::a ⇒ < :: a 但 <:::a ⇒ <: :: a 和 <::> ⇒ <: :>（即[]）。
还有其他例子。
(F)lex 通过使用稍微更灵活的“匹配”定义来处理这些异常，该定义仍然取决于最大 munch 启发式算法。
一个 (f)lex 模式可以包含一个（未加括号的）/ 运算符。 / 通常称为“尾随上下文”运算符，但这并不准确。 / 不改变匹配的字符；它的作用是从匹配的标记中排除 / 之后的匹配部分。因此，C++ 的 (f)lex 扫描器可能包含以下规则：
< { return T_LT; }
<: { return T_LT_COLON; }
</::[^:>] { return T_LT; }
因此，输入 <::a 将匹配所有三种模式。由于 maximal munch，最后一条规则将获胜，但是从该匹配中得到的标记 return 只是 < 而不是完整的 four-character 匹配。这意味着下一次扫描将从重新扫描 ::a 开始（导致检测到 :: 标记）。另一方面，输入 <:::a 不会匹配最后一个模式，因此扫描器将不得不回溯到实际匹配的最长模式：<:.
可以使用类似的技巧来确保具有范围（例如Swift）的语言中的 2..3 不匹配浮点模式：
[[:digit:]]+"."[[:digit:]] { ... return T_FLOAT; }
[[:digit:]]+/".." { ... return T_INTEGER; }
同样，2..3 的最长匹配是第二个匹配，因此 maximal munch 选择它。但是令牌 returned 只是 2；为下一个标记重新扫描尾随上下文。
然而，还有另一个 class 最大的 munch 异常，只能通过依赖句法上下文的词法分析来处理。例如，EcmaScript（和其他语言，包括 Awk）允许以 / 字符开头的正则表达式文字。但是，/ 也可能是除法运算符或 /= 运算符的第一个字符。 （它也可能开始注释，但由于正则表达式不能以 * 开头，所以这种情况是没有问题的。）语言语法有效地定义了两个互斥的上下文：
- 在“运算符”上下文中，中缀或后缀运算符是可能的，而变量或文字等操作数则不是。
- 在“操作数”上下文中，可以使用操作数或前缀运算符，但不能使用其他运算符。
因此 解析器 始终知道下一个标记是否可能是除法运算符，以及何时可能是正则表达式。但是它没有一个很好的方式来将这个事实传达给词法分析器。 （解析器依赖于先行标记的事实使场景进一步复杂化：为了让解析器调用词法分析器并指示是使用运算符还是正则表达式规则，解析器需要知道 before 它读取先行标记。）
maximal munch 的另一组明显的句法例外是模棱两可的双右括号，其中最臭名昭著的可能是 C++ 模板参数。当模板首次添加到 C++ 时，我们需要小心避免在没有干预 space 的情况下关闭两个打开的模板特化，以避免 >> 被识别为 right-shift 运算符。塔很烦人，也没有什么必要；很少有 >> 可以用两种不同方式解释的表达式，并且在几乎所有此类表达式中，其中一种可能性是非常人为的。因此，为了让大多数 C++ 程序员松一口气（以及 C++ 词法分析器作者的烦恼），标准最终被更改为允许 >> 关闭两个开放的模板特化，而不是强制将其解释为句法（或语义上）无效的右移。 （请注意，这种情况不必由词法分析器处理。词法分析器可以 return 单个 >> 标记，将其留给解析器使用该单个标记来关闭两个开放的特化。那语法有点复杂，但不是难以忍受。）
所以，最大咀嚼量并不是普遍的。此外，有时会提出词法分析器的建议，这些词法分析器可以通过生成多个可能的标记流来处理不明确的词典，这与 GLR/GLL 解析器可以生成多个可能的解析树的方式非常相似。事实上，一种 often-suggested 可能性是“无扫描器”解析器，其中词法分析只是集成到语法中。如果 GLR/GLL 解析器可用，词法分析往往会破坏对 lookahead 的需求这一事实将不再是 show-stopper。 （据称，无扫描器解析也适用于 PEG 语法。）
另一方面，处理并行标记流会显着增加解析时间，甚至达到需要输入长度的二次方的时间（尽管实际语法不应该发生这种情况）。我认为这让我们回到了最初问题中的例子。
上面给出的所有示例都显示了涉及两个连续标记的与 maximal munch 的偏差（在某种程度上它们是与 maximal munch 的偏差），这增加了词法分析的复杂性，但不会对计算产生太大影响复杂。但是在 OP 中建议的语法中，将 aaaaaaaaa 识别为以 aaa 标记而不是 aaaa 开始需要向前看不止一个标记（因为 aaaaaaaa 和 aaaaaaaaaa 应该以 aaaa).
除了可能对解析器提出额外的计算要求外，这种 non-local 消歧会给人类 reader（或作者）带来认知负担，他们通常 best-served一个功能易于预测的解析器，即使它有时无法找到潜在的解析器。
a+++++b 的 C 示例浮现在脑海中；偶尔会出现这样的问题，即为什么不将其解析为 a++ + ++b，这是唯一可能有意义的解析。我认为这里的答案与其说是“因为最大的咀嚼”，不如说是“因为大多数代码 readers 不会看到该解析”。 maximal munch 的一大优点，除了它的计算价值之外，就是它易于解释和预测。
其实很简单。当词法分析器（实现最长 match/maximal munch 原则）处理输入字符时，它会根据其他标记相互依赖 为每个标记做出决定。这意味着，在找到第一个可能的最长匹配项 aaaa 之后，第一个标记就可以由解析器进行处理了。然后词法分析器再次开始搜索另一个标记，并再次找到 aaaa。之后，由于剩余的输入字符串不足以匹配任何token，因此剩余的单个a不被识别为token。
第二个结果是可能的，如果词法分析器搜索 whole 输入的最佳匹配以转换为标记，而不是有问题的最长匹配。