lexer vs .解析器

是的，它们在理论上和执行上都有很大的不同。

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

词法分析和解析技术都不太可能很快消失。

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

解析器和词法分析器的共同之处:

1. 它们从输入中读取一些字母的符号。
   提示:字母表不一定是字母。但它 必须是原子符号的语言 .解析器/lexer可以理解
   • 词法分析器的符号:ASCII字符。
   • 解析器的符号:特定的标记，它们是语法的终端符号。
   李< / ul > < / >
   • 他们分析这些符号，并试图将它们与他们所理解的语言的语法相匹配
     • 这就是真正的区别所在。详见下文。
     • lexers所理解的语法:规则语法(Chomsky的第3级)。
     • 解析器理解的语法:上下文无关语法(乔姆斯基的第2级)。
     李< / ul > < / >
     • 他们将语义(含义)附加到他们找到的语言片段。
       • lexer通过将词位(来自输入的符号字符串)分类为特定的令牌来附加含义。例:所有这些词素:*， ==， <=， ^将被C/ c++ lexer归类为“操作符”令牌。
       • 解析器通过将输入(句子)中的标记字符串分类为特定的非终结符并构建解析树来附加含义。例如，所有这些令牌字符串:[number][operator][number]， [id][operator][id]， [id][operator][number][operator][number]将被C/ c++解析器归类为“表达式”非终结符。
       李< / ul > < / >
       • 它们可以为已识别的元素附加一些额外的含义(数据)。
         • 当词法分析器识别出一个构成适当数字的字符序列时，它可以将其转换为二进制值并与“number”令牌一起存储。
         • 类似地，当解析器识别表达式时，它可以计算其值并将其存储在语法树的“expression”节点中。
         李< / ul > < / >
         • 它们都在输出中产生它们所识别的语言的正确句子。
           • lexer生成令牌，这是他们识别的正规语言的句子。每个令牌都可以有一个内部语法(虽然是第3级，而不是第2级)，但这对于输出数据和读取它们的人来说无关紧要。
           • 解析器生成语法树，这是它们所识别的上下文无关语言的句子的表示。通常整个文档/源文件只有一个大树，因为整个文档/源文件对它们来说是一个合适的句子。但是没有任何理由解释为什么解析器不能在其输出中产生一系列语法树。例如，它可以是一个解析器，可以识别插入纯文本的SGML标记。因此，它将SGML文档标记转换为一系列令牌:[TXT][TAG][TAG][TXT][TAG][TXT]...。
           李< / ul > < / >

如您所见，解析器和标记器有很多共同之处。一个解析器可以是另一个解析器的标记器，后者将其输入标记读取为来自其自身字母表的符号(标记只是一些字母表的符号)，就像来自一种语言的句子可以是其他高级语言的字母符号一样。例如，如果*和-是字母M的符号(作为“莫尔斯电码符号”)，那么您可以构建一个解析器，它可以将这些点和线组成的字符串识别为莫尔斯电码编码的字母。“莫尔斯电码”语言中的句子可以是其他解析器的令牌，这些令牌是其语言的原子符号(例如:“英语词汇”语言)。这些“英语单词”可以是一些高级解析器的标记(字母表的符号)，这些解析器可以理解“英语句子”语言。和所有这些语言的区别仅仅在于语法的复杂程度。仅此而已。

那么，这些“乔姆斯基的语法水平”到底是怎么回事呢?诺姆·乔姆斯基根据语法的复杂程度将其分为四个等级:

• 第三级:常规语法

  它们使用正则表达式，也就是说，它们只能由字母符号(a，b)、它们的连接符号(ab，aba，bbb etd.)或替代符号(例如a|b)组成。它们可以实现为有限状态自动机(FSA)，如NFA(非确定性有限自动机)或更好的DFA(确定性有限自动机)。
  常规语法无法处理嵌套的语法，例如正确嵌套/匹配的括号(()()(()()))，嵌套的HTML/BBcode标签，嵌套的块等。这是因为要处理它的状态自动机必须有无限多的状态才能处理无限多的嵌套层

• 第2级:上下文无关语法

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

• 第1级:上下文敏感语法

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

什么时候lexing是足够的，什么时候你需要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中通过使用可以为空结果来实现，也就是说，它可以被空字符串(这里仅用空结果表示;其他人使用或或或交叉圆):

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

像上面最后一个B这样形式的结果被称为“擦除”，因为它可以擦除它在其他结果中所代表的任何内容(product为空字符串而不是其他内容)。

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.

知道它只生成一个空字符串(最终)，后面跟着0个或多个__abc0，相同的字符串(但不是同一种语言!)可以使用right-recursion表示:

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，它总是会在两边添加另一个__abc1和__abc2。lexer(更具体地说:lexer使用的有限状态自动机)不能计数到任意数字(它们是有限的，记得吗?)，所以它们不知道有多少__abc1与这么多__abc2均匀匹配。这样的语法被称为上下文无关文法(至少)，它们需要解析器。

上下文无关语法以解析而闻名，因此它们被广泛用于描述编程语言的语法。但还有更多。有时需要一个更通用的语法——当你同时有更多的东西要独立计算时。例如，当你想要描述一种可以使用圆括号和方括号交错使用的语言时，但它们必须彼此正确配对(大括号加大括号，圆括号加圆括号)。这种语法被称为上下文相关的。你可以通过它左边(箭头之前)有多个符号来识别它。例如:

A R B --> A S B

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

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

资源___编译器(第二版) 写的, 阿尔弗雷德·v·Abo 哥伦比亚大学 林忆莲 斯坦福大学 拉维塞提 亚美亚 杰弗里·d·厄尔曼 斯坦福大学< / p >

回答被问到的问题(不要过分重复中出现的内容) 其他答案)< / p > 类所建议的lexer和解析器并没有很大的不同 接受的答案。两者都基于简单的语言形式:规则 用于词法分析器的语言和几乎总是上下文无关(CF)语言 解析器。它们都与相当简单的计算有关 模型，有限状态自动机和下推堆栈自动机。 常规语言是上下文无关语言的一种特殊情况，所以 lexer可以用更复杂的CF生成 技术。但这不是一个好主意，至少有两个原因 编程的一个基本要点是系统组件应该 采用最合适的技术，使之易于实现 生产，理解和维护。技术不应该如此 过度杀戮(使用比实际需要复杂和昂贵得多的技术)， 它也不应该在其权力的极限，因此需要技术