词法分析者与解析者

5 回答

• 30

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

  他们从输入中读取某些字母的符号 .

  • 提示：字母表不一定是字母 . 但它必须是解析器/词法分析器理解的语言的符号 .

  • 词法分析器的符号：ASCII字符 .

  • 解析器的符号：特定的标记，它们是语法的终结符号 .

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

  • 这里通常存在真正的差异 . 见下文了解更多 .

  • 词法学者理解语法：常规语法（乔姆斯基3级） .

  • 解析器理解语法：无上下文语法（乔姆斯基的2级） .

  他们将语义（含义）附加到他们找到的语言片段 .

  • Lexers通过将lexemes（来自输入的符号串）分类为特定标记来附加含义 . 例如 . 所有这些词汇： * ， == ， <= ， ^ 将被C / C词法分类器归类为"operator"令牌 .

  • 解析器通过将输入（句子）中的标记字符串分类为特定的非终结符并构建解析树来附加含义 . 例如 . 所有这些令牌字符串： [number][operator][number] ，1573320， [id][operator][number][operator][number] 将被C / C解析器归类为"expression"非终结符号 .

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

  • 当词法分析器识别出构成正确数字的字符序列时，它可以将其转换为二进制值并与"number"标记一起存储 .

  • 类似地，当解析器识别表达式时，它可以计算其值并与语法树的"expression"节点一起存储 .

  他们都在他们的输出上产生他们认可的语言的正确句子 .

  • Lexer生成令牌，这些令牌是他们认可的常用语言的句子 . 每个令牌都可以具有内部语法（虽然级别3，而不是级别2），但这对输出数据和读取它们的数据无关紧要 .

  • 解析器生成语法树，它们是他们识别的无上下文语言的句子的表示 . 通常它只是整个文档/源文件的一个大树，因为整个文档/源文件对于它们来说是恰当的句子 . 但是还没有在其输出上产生一系列语法树 . 例如 . 它可以是一个解析器，它可以识别粘贴在纯文本中的SGML标签 . 因此，它会将SGML文档标记为一系列标记： [TXT][TAG][TAG][TXT][TAG][TXT]... .

  如您所见，解析器和标记器有许多共同点 . 一个解析器可以是其他解析器的标记化器，它将其输入标记作为符号从其自己的字母表中读取（标记只是某些字母表的符号），其方式与来自一种语言的句子可以是其他一些语言的字母符号相同 . 语言 . 例如，如果 * 和 - 是字母 M （作为"Morse code symbols"）的符号，那么您可以构建一个解析器，将这些点和线的字符串识别为摩尔斯电码中编码的字母 . 语言"Morse Code"中的句子可以是某些其他解析器的标记，这些标记的语言是其语言的原子符号（例如"English Words"语言） . 对于理解"English Sentences"语言的某些更高级别的解析器，这些"English Words"可能是令牌（字母表的符号） . 和 all these languages differ only in the complexity of the grammar . 而已 .

  那么这些“乔姆斯基的语法水平”究竟是什么呢？好吧，Noam Chomsky将语法分为四个级别，具体取决于它们的复杂程度：

  3级：常规语法

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

  第2级：无上下文语法

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

  1级：上下文相关语法

  0级：不受限制的语法也称为“相位结构语法” .

  回复于 2024-05-03T19:27:20+08:00
• 11

  是的，它们在理论和实施方面都有很大的不同 .

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

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

  lexing和解析技术都不会很快消失 .

  它们可以通过决定使用"parsing"技术识别"words"来统一，正如目前所谓的无扫描GLR解析器所探索的那样 . 这有一个运行时成本，因为您将更多通用机器应用于通常不需要它的问题，通常您需要在开销中支付 . 如果你有很多自由周期，那么开销可能无关紧要 . 如果您处理大量文本，那么开销就很重要，并且将继续使用经典的正则表达式解析器 .

  回复于 2024-05-03T19:27:20+08:00
• 96

  什么时候足够，你什么时候需要EBNF？

  EBNF确实不会增加语法的力量 . 这只是标准乔姆斯基普通形式（CNF）语法规则的便利/快捷符号/ "syntactic sugar" . 例如，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 这样的形式的制作被称为"erasure"，因为它可以删除其他制作中的任何形式（产品是空字符串而不是其他字符串） .

  来自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.
  

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

  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.
  

  也就是说，仅使用空字符串，终端符号，简单的非终端进行替换和状态更改，并且仅使用递归来实现重复（迭代，这只是线性递归 - 没有确定它是常规语法的那个，你可以用lexer来实现 .

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

  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 ，这将始终在双方增加另一个 a 和 b . 词汇表（更具体地说：词法分析器使用的有限状态自动机）不能计算到任意数字（它们是有限的，还记得吗？），因此他们不知道有多少 a 可以将它们与这么多 b 匹配 . 像这样的语法被称为无上下文语法（至少），它们需要一个解析器 .

  无上下文语法是众所周知的解析，因此它们被广泛用于描述编程语言' syntax. But there' . 有时候需要一个更通用的语法 - 当你有更多的东西可以同时计算，独立时 . 例如，当您想要描述一种语言，其中可以使用圆括号和方括号交错，但它们必须彼此正确配对（带括号的圆括号，带圆的圆形） . 这种语法称为上下文敏感 . 您可以通过左侧（箭头前）有多个符号来识别它 . 例如：

  A R B --> A S B
  

  您可以将左侧的这些附加符号视为应用规则的"context" . 可能存在一些先决条件，后置条件等 . 例如，上述规则将 R 替换为 S ，但仅当它位于 A 和 B 之间时，保留 A 和 B 本身不变 . 这种语法很难解析，因为它需要一台成熟的图灵机 . 它's a whole another story, so I'将在此结束 .

  回复于 2024-05-03T19:27:20+08:00
• 5

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

  根据公认的答案，Lexers和解析器并没有太大差异 . 两者都基于简单的语言形式：词法分析器的常规语言，以及几乎总是用于解析器的无上下文（CF）语言 . 它们都与相当简单的计算模型相关联，即有限状态自动机和下推堆栈自动机 . 常规语言是无上下文语言的特例，因此至少有两个原因 .

  编程的一个基本点是系统组件应该使用最合适的技术进行编写，以便易于生成，理解和维护 . 该技术不应过度使用（使用比所需技术复杂且成本更高的技术），也不应超出其功率极限，因此需要技术扭曲才能达到预期目标 .

  这就是为什么“讨厌正则表达式似乎很时髦” . 虽然它们可以做很多事情，但它们有时需要非常难以理解的编码来实现它，更不用说实现中的各种扩展和限制在某种程度上降低了它们的理论简单性 . Lexers通常不这样做，并且通常是一种简单，有效且适当的解析令牌的技术 . 虽然有可能，但使用CF解析器进行令牌可能会过度 .

  不使用CF形式主义用于词法分析器的另一个原因是它可能很容易使用完整的CF能力 . 但这可能会引发有关阅读节目的问题 .

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

  然而，由CF组成的CF（通过CF传感器...对于数学抱歉），不一定给CF，并且可能使事情更通用，但在实践中不易处理 . 所以CF不是词法分析器的合适工具，即使它可以使用 .

  One of the major differences between regular and CF is that regular languages (and transducers) compose very well with almost any formalism in various ways, while CF languages (and transducers) do not, not even with themselves (with a few exceptions).

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

  BNF只是呈现CF语法的特定语法 .

  EBNF is a syntactic sugar for BNF ，使用常规符号的设施来提供更为简洁的BNF语法版本 . 它总是可以转换为等效的纯BNF .

  然而，常规符号通常在EBNF中用于强调语法的这些部分，这些部分对应于词法元素的结构，并且应该用词法分析器识别，而其余部分则用直接BNF表示 . 但这不是一个绝对的规则 .

  总结一下， the simpler structure of token is better analyzed with the simpler technology of regular languages, while the tree oriented structure of the language (of program syntax) is better handled by CF grammars.

  我建议也看AHR's answer .

  但这留下了一个问题： Why trees?

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

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

  如上所述，基于该结构将语义与文本相关联是非常方便的，具有数学上易于理解的技术（通过同态的组合性） . 它是定义数学形式主义语义的基本代数工具 .

  因此，它是一个很好的中间表示，如抽象语法树（AST）的成功所示 . 请注意，AST通常与解析树不同，因为许多专业人员（例如LL或LR）使用的解析技术仅适用于CF语法的子集，因此强制语法扭曲，后来在AST中进行了纠正 . 使用接受任何CF语法的更通用的解析技术（基于动态编程）可以避免这种情况 .

  关于编程语言是上下文敏感（CS）而不是CF的事实的陈述是任意的和有争议的 .

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

  指称语义中的许多编程语言定义在语义中放置声明和类型检查 . 正如Ira Baxter所做的那样，CF解析器被黑客攻击以获得语法所需的上下文敏感性充其量只是对情况的任意看法 . 它可能被组织为一些编译器中的hack，但它不一定是 .

  此外，CS解析器（在此处的其他答案中使用的意义上）难以构建，效率较低 . 它们也不足以明显地表达可能需要的背景敏感性 . 并且它们不会自然地产生句法结构（例如解析树），其便于导出程序的语义，即生成编译的代码 .

  回复于 2024-05-03T19:27:20+08:00
• 439

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

  • 设计的简单性是最重要的考虑因素 . 词法和句法分析的分离通常允许我们简化这些任务中的至少一个 . 例如，一个必须处理注释和空格作为语法单元的解析器 . 词法分析器已经删除了可以假设注释和空格的复杂程度 . 如果我们正在设计一种新语言，将词汇和句法问题分开可以使整体语言设计更加清晰 .

  • 编译器效率得到改善 . 一个单独的词法分析器允许我们应用专门的技术，只用于词法任务，而不是解析工作 . 此外，用于读取输入字符的专用缓冲技术可以显着加速编译器 .

  • 编译器可移植性得到增强 . 输入设备特定的特性可以限制在词法分析器中 .

  resource___ Compilers （第2版） - Alfred V. Abo哥伦比亚大学Monica S. Lam斯坦福大学Ravi Sethi Avaya Jeffrey D. Ullman斯坦福大学

  回复于 2024-05-03T19:27:20+08:00