在该术语的形式语言定义中,说词汇产生“对消耗输入元素的句法语法上下文敏感”并不意味着语法对上下文敏感。事实上,在几乎所有重要的语法中都存在“对句法语法上下文敏感”的产生式。这是解析的本质:语法上下文有效地提供了一组潜在的可扩展非终结符,并且这些非终结符在不同的语法上下文中会有所不同,这意味着,例如,在大多数语言中,无法在需要表达式的地方输入语句(尽管通常情况下,表达式是语句的表现形式之一)。
然而,差异并不涉及不同的扩展相同的非终结符。 “上下文无关”语言所要求的是,非终结符的可能派生集合是相同的集合,无论该非终结符出现在何处。因此上下文可以提供不同的非终结符选择,但是每个非终结符都可以在不考虑其上下文的情况下进行扩展。这就是语法脱离上下文的意义。
正如您所注意到的,上下文敏感性通常是通过左侧带有模式而不是单个非终结符的语法在语法中抽象出来的。在最初的定义中,上下文——除了要扩展的非终结符之外的所有内容——需要不受影响地通过产生式;只能扩展一个非终结符,但可能的扩展取决于上下文,如产生式所示。上面隐含的是,有些语法可以用 BNF 编写,但它们甚至不符合上下文敏感规则(或其他等效规则)。所以它不是一个二元除法,无论是上下文无关的还是上下文相关的。语法有可能两者都不是(并且,由于空上下文仍然是上下文,因此任何上下文无关语法也是上下文相关的)。最重要的是,当数学家说话时,他们使用语言的方式有时是意想不到的。但它总是有一个明确的基本定义。
在形式语言理论中,不存在词汇和句法产生式;只是作品。如果词汇产生式和句法产生式都不受上下文影响,那么整个语法就不受上下文影响。然而,从实际的角度来看,由于多种原因,组合语法更难解析,我不打算在这里讨论。事实证明,通过词法解析器和句法解析器的划分,编写语言的语法并解析它们要容易一些。
在经典模型中,词法分析是完成的first,这样解析器就不会看到单个字符。相反,句法分析是通过“词汇标记”的“字母表”(在非常扩展的意义上)完成的。这非常方便——例如,这意味着词法分析可以简单地删除空格和注释,这极大地简化了句法语法的编写。但它也降低了通用性,正是因为语法解析器无法“指导”词法分析器做任何事情。在语法分析器意识到它的需求之前,词法分析器已经完成了它要做的事情。
如果解析器能够指导词法分析器,它会以与指导自身相同的方式进行操作。在某些产品中,令牌非终结符将包括InputElementDiv
在其他作品中InputElementRegExp
将是可接受的非终结符。正如我所指出的,这不是上下文敏感——这只是上下文无关语法的正常功能——但它确实需要修改程序的组织,以允许词法分析器考虑解析器的目标。这通常被(实践者,而不是理论家)称为“词汇反馈”,有时也被称为价值中立程度较低的术语;有时它被认为是语言设计中的一个弱点,因为违反了整齐隔离的词法分析器/解析器架构。 C++ 是一个相当激烈的例子,确实有些 C++ 程序也很难被人类解析,这是某种迹象。但 ECMAScript 并没有真正遇到这个问题;人类通常无需付出任何明显的智力努力就能区分除法运算符和正则表达式分隔符。而且,虽然实现 ECMAScript 解析器所需的词汇反馈确实使架构变得不太整洁,但这实际上也不是一项困难的任务。
无论如何,词法语法中的“目标符号”只是 ECMAScript 参考文献的作者决定使用的一个短语。这些“目标符号”只是普通的词法非终结符,就像任何其他产生式一样,因此说存在“多个目标符号”和说“解析器指示词法分析器使用不同的产生式”之间没有区别,我希望能解决您提出的问题。
Notes
-
两种语境中的词汇差异不仅仅如此/
有不同的意义。如果仅此而已,就根本不需要词汇反馈了。问题在于标记化本身发生了变化。如果运算符是可能的,那么/=
in
a /=4/gi;
是单个标记(复合赋值运算符),并且gi
是单个标识符标记。但是,如果此时正则表达式文字是可能的(但事实并非如此,因为正则表达式文字不能跟随标识符),那么/
和=
将是单独的令牌,因此g
and i
.
-
一些程序员更喜欢从一组产生式构建的解析器(但不是编写此内容的人:-));它们通常被称为“无扫描器解析器”。在 ECMAScript 的无扫描器解析器中,不会有词法反馈,因为没有单独的词法分析。
-
形式语言理论的理论纯粹性与编写现实编程语言的工作解析器的实际细节之间确实存在差距。理论模型确实很有用,如果不了解它们,就很难编写解析器。但很少有解析器严格遵守该模型,这没关系。同样,那些通俗地称为“regular从正式语言意义上来说,“表达式”根本不是正则表达式;一些“正则表达式”运算符甚至不是上下文无关的(反向引用)。因此,假设某些理论结果(“正则表达式”)是一个巨大的错误表达式可以在线性时间和常数空间中识别”)实际上对于“正则表达式”库来说也是如此。我不认为解析理论是计算机科学中表现出这种二分法的唯一分支。