词法分析者与解析者

Question

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

讨厌正则表达式似乎很时髦:编码恐怖,另一篇博客文章.

然而,流行的基于乐兴的工具:pygments,geshi或者美化,都使用正则表达式.他们好像有什么东西......

什么时候足够兴奋,什么时候需要EBNF？

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

Answer 1

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

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(作为"莫尔斯代码符号"),那么您可以构建一个解析器,将这些点和线的字符串识别为摩尔斯电码中编码的字母.在语言的"莫尔斯电码"的句子可能是令牌其他一些解析器,对于这些令牌是其语言的原子符号(例如"英语单词"语言).对于理解"英语句子"语言的某些更高级别的解析器,这些"英语单词"可以是令牌(字母表的符号).而所有这些语言的语法的复杂性唯一有所不同.而已.

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

• 3级:常规语法

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

• 第2级:无上下文语法

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

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

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

Answer 2

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

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

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

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

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

Answer 3

什么时候足够兴奋,什么时候需要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通过使用实现为空的生产,也就是说,它可以通过一个被替换的一个空字符串(由这里只是空洞的生产表示;其他人使用小量或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.

也就是说,仅使用空字符串,终端符号,简单的非终端进行替换和状态更改,并且仅使用递归来实现重复(迭代,这只是线性递归 - 不是树状分支的那种).没有比这更高级的东西了,那么你肯定它是一个常规语法,你可以用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将无限期地替换,这将始终在双方都添加另一个as和bs.词汇表(更具体地说:词法分析器使用的有限状态自动机)不能计算到任意数字(它们是有限的,还记得吗？),因此他们不知道a有多少s可以将它们与这么多bs 均匀匹配.像这样的语法被称为无上下文语法(至少),它们需要一个解析器.

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

A R B --> A S B

您可以将左侧的这些附加符号视为应用规则的"上下文".可能有一些前提条件,后置条件等.例如,上述规则将取代R成S,但只有当它的之间的A和B,让那些A和B自己不变.这种语法很难解析,因为它需要一台成熟的图灵机.这是另一个故事,所以我会在这里结束.

Answer 4

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

根据公认的答案,Lexers和解析器并没有太大差异.两者都基于简单的语言形式:词法分析器的常规语言,以及几乎总是用于解析器的无上下文(CF)语言.它们都与相当简单的计算模型相关联,即有限状态自动机和下推堆栈自动机.常规语言是无上下文语言的特例,因此可以使用更复杂的CF技术生成词法分析器.但至少有两个原因并不是一个好主意.

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

这就是为什么"讨厌正则表达式似乎很时髦".虽然它们可以做很多事情,但它们有时需要非常难以理解的编码来实现它,更不用说实现中的各种扩展和限制在某种程度上降低了它们的理论简单性.Lexers通常不这样做,并且通常是一种简单,有效且适当的解析令牌的技术.虽然有可能,但使用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解析器(在此处的其他答案中使用的意义上)难以构建,效率较低.它们也不足以明显地表达可能需要的背景敏感性.并且它们不会自然地产生一种句法结构(例如解析树),它便于导出程序的语义,即生成编译的代码.

Answer 5

解析器通常会组合词法分析器生成的标记并将它们分组。

\n

\n

解析器定义为对输入进行分析， \n根据语法规则组织数据，而词法分析器则\n转换标记序列中的字符序列

\n

\n

让\xe2\x80\x99s 看一下下面的例子，想象我们正在尝试解析一个加法。

\n

437 + 734\n

\n

词法分析器扫描文本并找到4, 3, 7一个空格( )。词法分析器的工作是识别字符构成NUM437类型的一个标记。

\n

\n

然后词法分析器找到一个+符号，它对应于第二个PLUS类型的标记，最后找到另一个NUM类型的标记类型的标记。

\n

查看更多详细信息：
\n解析指南：算法和术语

\n

Answer 6

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

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

资源___编者(第2版) - Alfred V. Abo哥伦比亚大学Monica S. Lam斯坦福大学Ravi Sethi Avaya Jeffrey D. Ullman斯坦福大学