词法分析器与parsing器

词法分析器和parsing器在理论上真的不一样吗？

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

然而，stream行的基于乐谱的工具： pygments ， geshi或者美化 ，都使用正则expression式。 他们似乎什么都得不到

什么时候足够轻松，什么时候需要EBNF？

有没有人使用这些词法分析器生成的令牌与野牛或antlr语法分析器？

Answer 1

parsing器和词法分析器有什么共同之处：

1. 他们从他们的input中读取一些字母的 符号 。
   提示：字母不一定是字母。 但它必须是parsing器/词法分析器理解的语言的primefaces的符号。
   • 词法分析器的符号：ASCII字符。
   • parsing器的符号：特定的令牌，它们是语法的terminal符号。
2. 他们分析这些符号，并尝试将它们与他们理解的语言的语法进行匹配。
   而这里真正的区别通常在哪里。 请参阅下面的更多。
   • 语法理解的语法：正则语法（乔姆斯基的3级）。
   • 语法理解语法：上下文无关文法（乔姆斯基的2级）。
3. 它们将语义 （含义）附加到他们find的语言片断上。
   • Lexers通过将词位 （来自input的string）分类为特定的标记来附加含义。 例如，所有这些词位： * ， == ， <= ， ^将被C / C ++词法分类器归类为“运算符”标记。
   • parsing器通过将来自input（句子）的令牌串分类为特定的非终止符并构buildparsing树来附加含义。 例如，所有这些标记string： [number][operator][number] ， [id][operator][id] ， [id][operator][number][operator][number]将被归类为非expression式C / C ++parsing器。
4. 他们可以附加一些额外的含义（数据）的认可元素。 例如，当一个词法分析器识别出一个构成正确数字的字符序列时，它可以将其转换为二进制值并用“数字”标记进行存储。 类似地，当parsing器识别一个expression式时，它可以计算它的值并且与语法树的“expression式”节点一起存储。
5. 他们都会在他们的输出中产生一个他们认识的语言的恰当句子 。
   • 词库生成令牌 ，这是他们认可的常规语言的 句子 。 每个标记可以有一个内部语法（虽然级别3，而不是级别2），但是这对输出数据和读取它们的数据无关紧要。
   • parsing器产生语法树 ，它们是它们识别的上下文无关语言的句子的表示。 通常它只是整个文档/源文件的一个大树，因为整个文档/源文件是适合它们的句子 。 但是parsing器不能在其输出中生成一系列语法树的原因是没有的。 例如，它可能是一个识别SGML标签的parsing器。 所以它会将SGML文档标记为一系列标记： [TXT][TAG][TAG][TXT][TAG][TXT]...

正如你所看到的，parsing器和标记器有许多共同之处。 一个parsing器可以是其他parsing器的标记器，其input标记作为自己的字母表中的符号（标记只是一些字母表的符号）以与来自一种语言的句子可以是其他一些更高级别的字母符号相同的方式来读取语言。 例如，如果*和-是字母M的符号（如“莫尔斯码符号”），则可以构build一个parsing器，将这些点和线的string识别为以莫尔斯码编码的字母。 “莫尔斯电码”语言中的句子可能是其他parsing器的标记 ，这些标记是其语言的primefaces符号（例如“英语单词”语言）。 这些“英语单词”可以是一些理解“英语句子”语言的高级parsing器的标记（字母符号）。 而所有这些语言只在语法的复杂性上有所不同 。 而已。

那么，这些“乔姆斯基的语法水平”是什么呢？ 那么，诺姆·乔姆斯基（Noam Chomsky）根据语法的复杂性将语法分为四个层次：

• 等级3：普通文法
  他们使用正则expression式，也就是说，它们可以只由字母（ a ， b ）的符号，它们的连接（ ab ， aba ， bbb etd。）或替代（例如a|b ）组成。
  它们可以实现为有限状态自动机（FSA），如NFA（非确定性有限自动机）或更好的DFA（确定性有限自动机）。
  正则语法不能用嵌套的语法来处理，比如正确的嵌套/匹配圆括号(()()(()())) ，嵌套的HTML / BBcode标记，嵌套的块等等。这是因为状态自动机应该处理它有无限多的州处理无数的嵌套层次。
• 2级：上下文无关语法
  它们可以在其语法树中嵌套，recursion，自相似的分支，所以它们可以很好地处理嵌套结构。
  它们可以用状态自动机来实现。 这个堆栈用来表示语法的嵌套级别。 实际上，它们通常被实现为自顶向下的recursion下降parsing器，它使用机器的过程调用堆栈来跟踪嵌套层次，并且在其语法中对每个非terminal符号recursion地使用被调用的过程/函数。
  但是他们不能用上下文相关的语法来处理。 例如，当你有一个expression式x+3 ，在一个上下文中，这个x可以是一个variables的名称，在其他上下文中，它可以是一个函数的名字等。
• 等级1：语境敏感的语法
• 等级0：无限制的语法
  也称为“阶段结构语法”。

Answer 2

是的，他们在理论上和实施上有很大的不同。

词汇是用来识别构成语言元素的“单词”，因为这些单词的结构通常很简单。 正则expression式在处理这个更简单的结构方面非常优秀，并且有用于实现词法分析器的非常高性能的正则expression式匹配引擎。

parsing器用于识别语言短语的“结构”。 这样的结构通常远远超出“正则expression式”所能识别的范围，所以需要“上下文敏感”的parsing器来提取这样的结构。 上下文敏感的parsing器很难build立，所以工程上的妥协是使用“上下文无关”的语法，并向parsing器（“符号表”等）添加黑客来处理上下文敏感的部分。

无论是parsing还是parsing技术都不会很快消失。

他们可以通过决定使用“parsing”技术来识别“单词”来进行统一，正如当前所谓的无扫描器GLRparsing器所探索的那样。 这有一个运行时间成本，因为你正在应用更多的通用机制来解决通常不需要的问题，而且通常你会为此付出代价。 如果你有很多的空闲周期，那么这个开销可能并不重要。 如果你处理了很多文本，那么开销很重要，经典的正则expression式parsing器将继续被使用。

Answer 3

什么时候足够轻松，什么时候需要EBNF？

EBNF真的不会增加很多语法的力量 。 这只是一个方便/快捷方式/ “标准乔姆斯基范式（CNF）语法规则”的“语法糖” 。 例如，EBNF的select：

 S --> A | B 

您可以通过单独列出每个替代产品来实现CNF：

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

EBNF的可选元素：

 S --> X? 

你可以在CNF中通过使用可空的生产来实现，也就是说，可以用一个空string （在这里只是空的生产表示;其他的使用epsilon或者lambda或者交叉圆）来替代：

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

像上面最后一个B的forms的产品被称为“擦除”，因为它可以擦除其他产品中的任何东西（产品是一个空string，而不是别的东西）。

来自EBNF的零或更多的重复：

 S --> A* 

你可以通过使用recursion生产来阻塞，也就是说，它可以embedded到某个地方。 这可以通过两种方式来完成。 首先是左recursion （通常应该避免，因为自顶向下recursion下降parsing器不能parsing它）：

 S --> SA // `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. 

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

 S --> AS // `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 --> AA* 

你可以在CNF中这样表示（我在这里使用了正确的recursion方法，试着找出另外一个作为练习）：

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

知道这一点，你现在可能认识到一个正则expression式（即正则语法 ）的语法就像一个只能由terminal符号组成的单一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. 

也就是说，只使用空string，terminal符号，用于replace和状态变化的简单非terminal，并且仅使用recursion来实现重复（迭代，这只是线性recursion – 不分枝树状）。 没有比这更高级的，那么你确定这是一个常规的语法，你可以只用lexer。

但是，当你的语法以不平凡的方式使用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. 

那么你可以很容易地看出这不能用正则expression式来完成，因为你无法以任何方式把它parsing成单一的EBNF生产; 你最终将无限期地replaceS ，这将永远增加另一个s和b在双方。 词法分析器（更具体地说：词法分析器所使用的有限状态自动机）不能计为任意数（它们是有限的，记得吗？），所以他们不知道有多lessa分布符合它们。 像这样的语法被称为上下文无关语法 （至less），他们需要一个parsing器。

上下文无关文法是众所周知的parsing，所以它们被广泛用于描述编程语言的语法。 但还有更多。 有时需要一个更一般的语法 – 当你有更多的东西在同一时间独立计数。 例如，当你想要描述一种可以使用圆括号和方括号交错的语言，但是他们必须正确配对（带括号的括号，圆括号）。 这种语法被称为上下文敏感 。 您可以通过它左边有多个符号（在箭头之前）来识别它。 例如：

 ARB --> ASB 

您可以将左侧的这些附加符号视为应用规则的“上下文”。 可能有一些先决条件，后置条件等等。例如，上述规则将用R代替S ，但只有当它在A和B之间时，才使A和B本身保持不变。 这种语法真的很难parsing，因为它需要一个完整的图灵机。 这是一个完整的故事，所以我会在这里结束。

Answer 4

要回答这个问题（不必过分重复在其他答案中出现的内容）

正如接受的答案所暗示的那样，词法和parsing器并不是很不相同。 两者都基于简单的语言forms：词法分析器的常规语言和几乎总是用于分析器的上下文无关（CF）语言。 它们都与相当简单的计算模型，有限状态自动机和下推堆栈自动机相关联。 常规语言是上下文无关语言的特例，因此词法分析器可以用更复杂的CF技术来生成。 但至less有两个原因， 这不是一个好主意 。

编程的一个基本点是系统组件应该用最合适的技术来构build，这样就很容易产生，理解和维护。 这种技术不应该是过度的（使用技术比需要复杂和昂贵的技术），也不应该在权力的极限，因此需要技术上的扭曲才能达到预期的目标。

这就是为什么“讨厌正则expression式似乎很时髦”。 虽然他们可以做很多事情，但是他们有时候需要非常不可读的编码才能实现它，更不用说在实现中实现各种扩展和限制的事实在一定程度上减less了它们的理论简单性。 词库通常不会这样做，而且通常是一种简单，高效，适当的parsing令牌技术。 使用CFparsing器代替令牌可能是矫枉过正的，尽pipe这是可能的。

另一个不使用CFforms主义的词法分析器就是使用完整的CFfunction。 但是，这可能会提高节目的阅读方面的结构性问题。

从根本上讲，程序文本的大部分结构都是以树结构的forms提取出来的。 它expression了语法规则如何生成分析语句（程序）。 语义是通过组合技术（针对math导向的同态）从构造语法规则的语法规则的方式派生的。 因此树结构是必不可less的。 事实上，令牌是用普通的词法分析器识别的，并不会改变这种情况，因为用常规组成的CF仍然给出CF（我对于普通的换能器非常松散，将字符stream转化为令牌stream）。

然而，由CF组成的CF（通过CF换能器…对math感到抱歉），不一定给CF，并且可能使得事情更加普遍，但在实践中更不易处理。 所以CF对于词法分析器来说并不是合适的工具，尽pipe它可以被使用。

常规和CF之间的主要区别之一是常规语言（和传感器）以各种方式与几乎任何forms主义组成非常好，而CF语言（和传感器）不甚至与他们自己（除less数例外）之外。

（请注意，常规传感器可能有其他用途，例如某些语法error handling技术的forms化。）

BNF只是一个展示CF语法的特定语法。

EBNF是BNF的一种语法糖 ，它使用定期记号的function来给BNF语法提供更精确的版本。 它总是可以转换成一个等效的纯BNF。

然而，在EBNF中常常使用正则表示法来强调这些与词法元素结构相对应的语法部分，应该用词法分析器来识别，而其余部分则用直接的BNF表示。 但这不是一个绝对的规则。

总之， 用较简单的正则语言技术可以更好地分析令牌的简单结构，而CF语法更好地处理程序语言的树型结构。

我build议也看AHR的答案 。

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

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

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

• 如上所述，在math上很好理解的技术（通过同态的组合性）的基础上，将语义与文本联系起来非常方便。 定义mathforms主义的语义学是一个基本的代数工具。

因此，这是一个很好的中间表示，如抽象语法树（AST）的成功所示。 请注意，AST常常与parsing树不同，因为许多专业人员使用的parsing技术（如LL或LR）仅适用于CF语法的一个子集，因此会强制语法上的错误，这些语法错误将在AST中进行后续更正。 这可以通过接受任何CF语法的更一般的parsing技术（基于dynamic编程）来避免。

关于编程语言是上下文敏感（CS）而不是CF的说法是任意的和有争议的。

问题是语法和语义的分离是任意的。 检查声明或types协议可以被看作是语法的一部分，或者是语义的一部分。 自然语言中的性别和号码协议也是如此。 但是有些自然语言中的复数依赖于单词的实际语义，所以不符合语法。

在指称语义中许多编程语言的定义在语义中放置了声明和types检查。 所以，如Ira Baxter所说，CFparsing器被黑客攻击以获得语法所需的上下文敏感性至多是对情况的任意看法。 它可能在某些编译器中被组织为黑客，但不一定是。

另外它不仅仅是CSparsing器（在这里用于其他答案）难以构build，效率也不高。 他们也不足以明确地expression可能需要的情境敏感的情感。 而且它们自然不会产生一个方便派生程序语义的语法结构（比如分析树），即生成编译后的代码。

Answer 5

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

1. devise的简单性是最重要的考虑因素。 词法分析和句法分析经常使我们能够简化至less其中一个任务。 例如，一个parsing器不得不把注释和空白作为句法单位来处理。 比可以假设评论和词法分析器已经去除了空白的情况要复杂得多。 如果我们正在devise一种新的语言，分离词汇和句法问题可以导致更清晰的整体语言devise。
2. 编译器效率得到改善。 一个单独的词法分析器允许我们应用专门的技术，只服务于词汇任务，而不是parsing工作。 另外，读取input字符的专门缓冲技术可以显着加快编译器的速度。
3. 编译器可移植性得到增强。 input设备特有的特性可以限制在词法分析器中。

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