语境敏感的标记化是否需要词汇语法中的多个目标符号？ [英] Does context-sensitive tokenisation require multiple goal symbols in the lexical grammar?

问题描述

根据ECMAScript spec：

在几种情况下，词汇输入的识别 元素对句法语法上下文敏感，即 使用输入元素。这需要多个目标符号 词汇语法。

两个这样的符号是InputElementDiv和InputElementRegExp。

在ECMAScript中，/的含义取决于它出现的上下文。根据上下文的不同，/可以是除法运算符、正则表达式文字的开始或注释分隔符。词法分析器本身无法区分除法运算符和正则表达式文本，因此它必须依赖于来自分析器的上下文信息。

我想了解为什么这需要在词汇语法中使用多个目标符号。我对语言设计不是很了解，所以我不知道这是因为语法的某种正式要求，还是仅仅是惯例。

问题

• 为什么不像这样使用单一目标符号：

InputElement ::
     [...]
     DivPunctuator
     RegularExpressionLiteral
     [...]

并让解析器告诉词法分析器使用哪个结果(DivPunctuatorvsRegExLiteral)，而不是使用哪个球门符号(InputElementDivvsInputElementRegExp)？

• 还有哪些语言在其词汇语法中使用多目标符号？

• 我们如何对ECMAScript词汇语法进行分类？它在CSG的正式定义意义上不是上下文敏感的(即，其产品的LHS不被终端和非终端符号的上下文包围)。

推荐答案

说词汇产生对使用输入元素的句法语法上下文敏感，在该术语的形式语言定义中，不会使语法上下文敏感。事实上，在几乎每一个重要的语法中，都有对句法语法语境敏感的作品。这是语法分析的本质：语法上下文有效地提供了一组潜在可扩展的非终结符，这些非终结符在不同的语法上下文中会有所不同，这意味着，例如，在大多数语言中，语句不能在需要表达式的地方输入(尽管通常情况下，表达式是语句的表现之一)。

但是，差异不涉及相同非终结符的不同扩展。上下文无关语言所要求的是，无论非终结符出现在哪里，非终结符的可能派生集合都是相同的集合。因此，上下文可以提供不同的非终端选择，但是每个非终端都可以在不考虑其上下文的情况下被扩展。这就是语法脱离语境的意义。

正如您注意到的，上下文敏感通常在语法中抽象为左侧有模式的语法，而不是单个非终结符。在最初的定义中，上下文--除了要扩展的非终端之外的所有东西--需要原封不动地通过产品；只能扩展一个非终端，但可能的扩展取决于产品所指示的上下文。上面隐含的意思是，可以用BNF编写的语法甚至不符合上下文敏感规则(或其他等价规则)。所以它不是一个二进制除法，无论是上下文无关还是上下文敏感。语法可能两者都不是(而且，因为空的上下文仍然是上下文，所以任何上下文无关的语法也是上下文敏感的)。底线是，当数学家讲话时，他们使用词语的方式有时是出乎意料的。但它总是有一个明确的基本定义。

在形式语言理论中，没有词汇和句法的产生，只有产生。如果词汇产出和句法产出都是脱离语境的，那么整个语法就是脱离语境的。但是，从实际的角度来看，组合语法更难解析，原因有很多，我不会在这里详细介绍。事实证明，为一种语言编写语法并对它们进行语法分析要容易一些，词法分析器和句法分析器是分开的。

在经典模型中，首先进行词法分析，因此解析器看不到单个字符。相反，句法分析是用字母表(在非常广泛的意义上)的词性标记&来完成的。这非常方便--例如，这意味着词法分析可以简单地删除空格和注释，这极大地简化了语法编写。但它也降低了通用性，这恰恰是因为句法分析器不能指导词法分析器做任何事情。在语法分析器意识到它的需要之前，词法分析器已经完成了它要做的事情。

如果解析器能够指导词法分析器，它将以与指导自身相同的方式这样做。在一些产品中，令牌非终止符将包括InputElementDiv，而在其他产品中，InputElementRegExp将是可接受的非终止符。正如我所提到的，这不是上下文敏感的--这只是上下文无关语法的正常功能--但它确实需要修改程序的组织，以允许词法分析器考虑解析器的目标。这通常(由实践者而不是理论家)称为词法反馈，有时被称为值不那么中立的术语；有时它被认为是语言设计中的一个弱点，因为整齐分离的词法分析器/解析器架构被违反了。C++是一个相当激烈的例子，事实上，也有一些C++程序很难被人类解析，这是某种迹象。但是ECMASRIPT并没有真正受到这个问题的困扰；人们通常在没有进行任何明显的智力努力的情况下区分除法运算符和正则表达式分隔符。而且，虽然实现ECMAScript解析器所需的词汇反馈确实会使体系结构变得不那么整洁，但这也不是一项困难的任务。

无论如何，词汇语法中的目标符号只是ECMAScript参考的作者决定使用的短语。与任何其他结果一样，这些目标符号只是普通的词法非终止符，因此，说有多个目标符号和说语法分析器指示词法分析器使用不同的结果&没有什么不同，我希望这能解决您提出的问题。

备注

1. 这两个上下文中的词汇差异不仅仅是/有不同的含义。如果这就是全部，就根本不需要词汇反馈了。问题是，标记化本身发生了变化。如果运算符是可能的，则

   中的/=

   a /=4/gi;
   

   是单个令牌(复合赋值操作符)，gi是单个标识符令牌。但是，如果在这一点上可以使用regexp文本(实际上不可能，因为regexp文本不能跟在标识符之后)，那么/和=将是单独的标记，g和i也是如此。

2. 从一组产品构建的解析器是某些程序员的首选(但不是编写这篇文章的人：-)；它们通常被称为无扫描解析器。在ECMAScript的无扫描解析器中，不会有词法反馈，因为没有单独的词法分析。

3. 在形式语言理论的理论纯洁性和编写实际编程语言的工作解析器的实际细节之间确实存在着突破。理论模型非常有用，在不了解它们的情况下很难编写解析器。但很少有解析器严格遵守该模型，这也没什么。类似地，通常称为正则正则表达式的东西在形式语言意义上根本不是正则的；一些正则表达式运算符甚至不是上下文无关的(反向引用)。因此，假设某些理论结果(正则表达式可以在线性时间和常量空间中标识)实际上适用于正则表达式&库，将是一个巨大的错误。我不认为解析理论是计算机科学中唯一表现出这种二分法的分支。

这篇关于语境敏感的标记化是否需要词汇语法中的多个目标符号？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！