341

词法分析器和解析器在理论上真的有那么不同吗？

讨厌正则表达式似乎很时髦：编码恐怖，另一篇博文。

然而，流行的基于词法分析的工具：pygments、geshi或prettify都使用正则表达式。他们似乎对任何事情都...

什么时候词法足够，什么时候需要 EBNF？

有没有人将这些词法分析器生成的令牌与 bison 或 antlr 解析器生成器一起使用？

4

5 回答 5

528

解析器和词法分析器的共同点：

  1. 他们从输入中读取一些字母的符号。

    • 提示：字母表不一定是字母。但它必须是解析器/词法分析器理解的语言的原子符号。
    • 词法分析器的符号：ASCII 字符。
    • 解析器的符号：特定的标记，它们是语法的终结符号。

  2. 他们分析这些符号并尝试将它们与他们理解的语言的语法相匹配。

    • 这通常是真正的区别所在。有关更多信息，请参见下文。
    • 词法分析器理解的语法：常规语法（乔姆斯基的第 3 级）。
    • 解析器理解的语法：上下文无关语法（乔姆斯基的第 2 级）。

  3. 他们将语义（意义）附加到他们找到的语言片段上。

    • 词法分析器通过将词位（来自输入的符号字符串）分类为特定标记来附加意义。例如，所有这些词位：*, ==, <=,^将被 C/C++ 词法分析器归类为“运算符”标记。
    • 解析器通过将输入（句子）中的标记字符串分类为特定的非终结符并构建解析树来附加含义。例如，所有这些标记字符串：[number][operator][number], [id][operator][id],[id][operator][number][operator][number]将被 C/C++ 解析器归类为“表达式”非终结符。

  4. 他们可以为识别的元素附加一些额外的含义（数据）。

    • 当词法分析器识别出构成正确数字的字符序列时，它可以将其转换为二进制值并与“数字”标记一起存储。
    • 类似地，当解析器识别出一个表达式时，它可以计算它的值并与语法树的“表达式”节点一起存储。

  5. 他们都在他们的输出中产生了他们所认识的语言的正确句子。

    • 词法分析器产生标记，它们是它们识别的常规语言的句子。每个标记都可以有一个内部语法（尽管是 3 级，而不是 2 级），但这对于输出数据和读取它们的数据并不重要。
    • 解析器产生句法树，它们是它们识别的上下文无关语言的句子的表示。通常整个文档/源文件只有一棵大树，因为整个文档/源文件对他们来说是一个合适的句子。但是解析器无法在其输出中生成一系列语法树是没有任何原因的。例如，它可以是一个解析器，它可以识别粘贴在纯文本中的 SGML 标签。所以它会将SGML 文档标记为一系列标记：.[TXT][TAG][TAG][TXT][TAG][TXT]...

如您所见，解析器和分词器有很多共同点。一个解析器可以是另一个解析器的分词器，它将其输入记号读取为它自己的字母表中的符号（记号只是某些字母表的符号），就像来自一种语言的句子可以是其他一些更高级别的字母符号一样语言。例如，如果*和-是字母表的符号M（作为“摩尔斯电码符号”），那么您可以构建一个解析器，将这些点和线的字符串识别为以摩尔斯电码编码的字母。“摩尔斯电码”语言中的句子可能是其他解析器的标记，这些标记是其语言的原子符号（例如“英语单词”语言）。这些“英语单词”可能是一些理解“英语句子”语言的高级解析器的标记（字母表的符号）。而所有这些语言的不同之处仅在于语法的复杂性。而已。

那么这些“乔姆斯基的语法水平”到底是怎么回事？好吧，诺姆乔姆斯基根据语法的复杂性将语法分为四个级别：

  • 第 3 级：常规语法

    它们使用正则表达式，也就是说，它们只能由字母符号 ( a, b)、它们的串联符号 ( ab, aba, bbbetd.) 或替代符号 (例如a|b) 组成。
    它们可以实现为有限状态自动机 (FSA)，如 NFA（非确定性有限自动机）或更好的 DFA（确定性有限自动机）。
    常规语法无法处理嵌套语法，例如正确嵌套/匹配的括号(()()(()()))、嵌套的 HTML/BBcode 标记、嵌套块等。这是因为处理它的状态自动机应该有无限多的状态来处理无限多的嵌套级别。

  • 第 2 级：上下文无关文法

    它们的语法树中可以有嵌套的、递归的、自相似的分支，因此它们可以很好地处理嵌套结构。
    它们可以实现为带有堆栈的状态自动机。此堆栈用于表示语法的嵌套级别。在实践中，它们通常被实现为自上而下的递归下降解析器，它使用机器的过程调用堆栈来跟踪嵌套级别，并对其语法中的每个非终结符号使用递归调用的过程/函数。
    但是它们无法处理上下文相关的语法。例如，当您有一个表达式时x+3，在一个上下文中，这x可能是一个变量的名称，而在其他上下文中，它可能是一个函数的名称等。

  • 级别 1：上下文相关的语法

  • 0 级：无限制文法
    也称为递归可枚举文法。

于 2010-09-01T03:53:27.470 回答
116

是的，它们在理论上和实现上都非常不同。

词法分析器用于识别构成语言元素的“词”，因为这些词的结构通常很简单。正则表达式非常擅长处理这种更简单的结构，并且有非常高性能的正则表达式匹配引擎用于实现词法分析器。

解析器用于识别语言短语的“结构”。这种结构通常远远超出“正则表达式”可以识别的范围，因此需要“上下文敏感”解析器来提取这种结构。上下文相关的解析器很难构建，因此工程上的折衷方案是使用“无上下文”语法并向解析器（“符号表”等）添加 hack 来处理上下文相关部分。

词法分析和解析技术都不会很快消失。

它们可以通过决定使用“解析”技术来识别“单词”来统一，正如目前所谓的无扫描 GLR 解析器所探索的那样。这会产生运行时成本，因为您将更通用的机器应用于通常不需要它的问题，并且通常您会为此付出开销。如果您有很多空闲周期，那么开销可能并不重要。如果您处理大量文本，那么开销确实很重要，并且将继续使用经典的正则表达式解析器。

于 2010-05-17T20:52:45.447 回答
34

什么时候词法足够，什么时候需要 EBNF？

EBNF 并没有真正增加语法的力量。它只是标准乔姆斯基范式（CNF）语法规则的方便/快捷符号/ “语法糖” 。例如，EBNF 替代方案：

S --> A | B

您可以通过单独列出每个替代生产在 CNF 中实现：

S --> A      // `S` can be `A`,
S --> B      // or it can be `B`.

EBNF 的可选元素：

S --> X?

您可以在 CNF 中通过使用可为空的产生式来实现，即可以用空字符串替换的产生式（此处仅用空产生式表示；其他人使用 epsilon 或 lambda 或交叉圆）：

S --> B       // `S` can be `B`,
B --> X       // and `B` can be just `X`,
B -->         // or it can be empty.

像上面最后一个形式的产生式B称为“擦除”，因为它可以擦除它在其他产生式中代表的任何内容（产生一个空字符串而不是其他东西）。

EBNF 的零次或多次重复：

S --> A*

您可以通过使用递归生产来获得，也就是说，将自己嵌入其中的某个地方。它可以通过两种方式完成。第一个是左递归（通常应该避免，因为自顶向下递归下降解析器无法解析它）：

S --> S A    // `S` is just itself ended with `A` (which can be done many times),
S -->        // or it can begin with empty-string, which stops the recursion.

知道它只生成一个空字符串（最终）后跟零个或多个As，可以使用右递归表示相同的字符串（但不是相同的语言！ ） ：

S --> A S    // `S` can be `A` followed by itself (which can be done many times),
S -->        // or it can be just empty-string end, which stops the recursion.

当涉及到+EBNF 的一次或多次重复时：

S --> A+

它可以通过分解出一个A并*像以前一样使用来完成：

S --> A A*

您可以在 CNF 中这样表达（我在这里使用右递归；尝试自己找出另一个作为练习）：

S --> A S   // `S` can be one `A` followed by `S` (which stands for more `A`s),
S --> A     // or it could be just one single `A`.

知道了这一点，您现在可能可以将正则表达式的文法（即正则文法）识别为可以在仅由终端符号组成的单个 EBNF 产生式中表示的文法。更一般地说，当您看到类似于这些的产生式时，您可以识别常规语法：

A -->        // Empty (nullable) production (AKA erasure).
B --> x      // Single terminal symbol.
C --> y D    // Simple state change from `C` to `D` when seeing input `y`.
E --> F z    // Simple state change from `E` to `F` when seeing input `z`.
G --> G u    // Left recursion.
H --> v H    // Right recursion.

也就是说，仅使用空字符串、终结符号、简单的非终结符进行替换和状态更改，并且仅使用递归来实现重复（迭代，这只是线性递归- 不会像树一样分支的递归）。没有比这些更高级的了，那么你确定它是一种常规语法，你可以只使用词法分析器。

但是，当您的语法以非平凡的方式使用递归时，会产生树状、自相似、嵌套结构，如下所示：

S --> a S b    // `S` can be itself "parenthesized" by `a` and `b` on both sides.
S -->          // or it could be (ultimately) empty, which ends recursion.

那么你可以很容易地看到这不能用正则表达式来完成，因为你不能以任何方式将它解析为一个单一的 EBNF 产生式；你最终会S无限期地替换，这总是会在两边添加另一个as 和s 。b词法分析器（更具体地说：词法分析器使用的有限状态自动机）不能计数到任意数字（它们是有限的，记得吗？），所以他们不知道a有多少 s 可以将它们与这么多bs 均匀匹配。像这样的语法被称为上下文无关语法（至少），它们需要一个解析器。

上下文无关语法是众所周知的解析，因此它们被广泛用于描述编程语言的语法。但还有更多。有时需要更通用的语法——当你有更多的东西要同时独立计算时。例如，当您要描述一种可以使用圆括号和方括号交错的语言时，但它们必须正确配对（大括号与大括号，圆与圆）。这种语法称为context-sensitive。您可以通过它在左侧（箭头之前）有多个符号来识别它。例如：

A R B --> A S B

您可以将左侧的这些附加符号视为应用规则的“上下文”。可能有一些前置条件、后置条件等。例如，上述规则将替换R为S，但仅当它位于A和之间时B，它们A和B它们本身保持不变。这种语法真的很难解析，因为它需要一个成熟的图灵机。这是另一个故事，所以我会在这里结束。

于 2012-08-02T02:36:06.567 回答
13

按要求回答问题（不要过度重复其他答案中出现的内容）

正如接受的答案所建议的那样，词法分析器和解析器并没有太大的不同。两者都基于简单的语言形式：用于词法分析器的常规语言和几乎总是用于解析器的上下文无关 (CF) 语言。它们都与相当简单的计算模型、有限状态自动机和下推堆栈自动机相关联。正则语言是上下文无关语言的一种特殊情况，因此词法分析器可以使用更复杂的 CF 技术生成。但这不是一个好主意，至少有两个原因。

编程的一个基本点是系统组件应该使用最合适的技术来构建，以便于生产、理解和维护。该技术不应过度杀伤（使用比所需更复杂和成本更高的技术），也不应处于其能力的极限，从而需要技术上的扭曲来实现预期的目标。

这就是为什么“讨厌正则表达式似乎很时髦”。尽管它们可以做很多事情，但有时需要非常不可读的编码来实现它，更不用说实现中的各种扩展和限制在一定程度上降低了它们的理论简单性。词法分析器通常不会这样做，并且通常是一种简单、高效且适当的技术来解析令牌。尽管有可能，但使用 CF 解析器获取令牌将是矫枉过正。

不对词法分析器使用 CF 形式主义的另一个原因是，使用完整的 CF 功能可能很诱人。但这可能会引发有关阅读程序的结构性问题。

从根本上说，从中提取意义的程序文本的大部分结构是树形结构。它表达了解析语句（程序）是如何从语法规则生成的。语义是通过组合技术（面向数学的同态）从组合语法规则以构建解析树的方式得出的。因此，树结构是必不可少的。使用基于常规集的词法分析器识别标记的事实并没有改变这种情况，因为由常规组合的 CF 仍然给出 CF（我非常松散地谈论常规转换器，它将字符流转换为令牌流）。

然而，由 CF 组成的 CF（通过 CF 换能器......对不起数学），不一定给出 CF，并且可能使事情更普遍，但在实践中不太容易处理。所以 CF 不是词法分析器的合适工具，即使它可以使用。

常规语言和 CF 之间的主要区别之一是常规语言（和转换器）以各种方式与几乎任何形式主义组合得非常好，而 CF 语言（和转换器）则不能，甚至它们本身也不行（除了少数例外）。

（请注意，常规转换器可能有其他用途，例如某些语法错误处理技术的形式化。）

BNF 只是表示 CF 语法的特定语法。

EBNF 是 BNF 的语法糖，使用正则符号的工具来提供 BNF 语法的简洁版本。它总是可以转化为等价的纯 BNF。

然而，在 EBNF 中经常使用正则符号只是为了强调与词法元素结构相对应的语法部分，并且应该用词法分析器识别，而其余部分则在直接 BNF 中呈现。但这不是一个绝对的规则。

总而言之，使用更简单的常规语言技术可以更好地分析更简单的标记结构，而使用 CF 语法更好地处理语言（程序语法）的面向树的结构。

我建议也看看AHR 的答案。

但这留下了一个问题：为什么是树？

树是指定语法的良好基础，因为

  • 他们给文本一个简单的结构

  • 如上所述，使用数学上很好理解的技术（通过同态的组合性）将语义与文本关联起来非常方便。它是定义数学形式语义的基本代数工具。

因此，它是一个很好的中间表示，正如抽象语法树 (AST) 的成功所示。请注意，AST 通常与解析树不同，因为许多专业人士（例如 LL 或 LR）使用的解析技术仅适用于 CF 语法的子集，因此会导致语法失真，这些失真后来在 AST 中得到纠正。这可以通过接受任何 CF 语法的更通用的解析技术（基于动态编程）来避免。

关于编程语言是上下文敏感 (CS) 而不是 CF 这一事实的陈述是任意且有争议的。

问题是语法和语义的分离是任意的。检查声明或类型协议可以被视为语法的一部分或语义的一部分。自然语言中的性别和数字一致性也是如此。但是有些自然语言的复数一致性取决于单词的实际语义，因此它不能很好地适应语法。

指称语义中的许多编程语言定义将声明和类型检查放在语义中。因此，正如Ira Baxter所做的那样，CF 解析器被黑客入侵以获得语法所需的上下文敏感性充其量只是对这种情况的任意看法。在某些编译器中，它可能被组织为 hack，但并非必须如此。

此外，不仅仅是 CS 解析器（在此处其他答案中使用的意义上）难以构建，而且效率较低。它们也不足以清晰地表达可能需要的上下文敏感性。而且它们自然不会产生便于推导程序语义的句法结构（如分析树），即生成编译代码。

于 2014-06-11T14:19:30.200 回答
7

编译器的分析部分通常分为词法分析和解析（语法分析）阶段的原因有很多。

  1. 设计的简单性是最重要的考虑因素。词法分析和句法分析的分离通常使我们能够简化这些任务中的至少一项。例如，一个必须将注释和空格作为句法单元处理的解析器。比假设注释和空格已经被词法分析器删除的复杂得多。如果我们正在设计一种新语言，分离词汇和句法关注点可以导致更清晰的整体语言设计。
  2. 编译器效率得到提高。一个单独的词法分析器允许我们应用专门的技术，这些技术只服务于词法任务，而不是解析工作。此外，用于读取输入字符的专用缓冲技术可以显着加快编译器的速度。
  3. 编译器的可移植性得到增强。输入设备特定的特性可以限制在词法分析器中。

资源___ 编译器（第 2 版），作者：Alfred V. Abo 哥伦比亚大学 Monica S. Lam 斯坦福大学 Ravi Sethi Avaya Jeffrey D. Ullman 斯坦福大学

于 2014-03-10T17:40:27.250 回答