JavaScript是一种上下文无关语言吗？

Question

这篇关于浏览器如何工作的文章解释了CSS如何无上下文,而HTML则没有.但是JavaScript呢,JavaScript上下文是免费的吗？

我正在学习CFG和正式证明,但距离理解如何解决这个问题还有很长的路要走.有没有人知道JavaScript是否没有上下文？

Answer 1

不,JavaScript不是一种无上下文的语言.

它与一个非常接近,ECMAScript 5规范确实使用无上下文语法¹来描述语言的语法(您可以在附录A中找到所有产品).

当然,它确实对纯无上下文语法产生做了一些扩展,并描述了解析器的额外行为.一个特别的事情是前瞻的使用仍然使得无上下文的语言,但如果它不能用于某些规则会使语法复杂化.不允许某些事物出现在严格模式代码中是相似的 - 它可以通过调整语法(具有更多的产品)来完成,但是通过离开BNF更容易表达规则.

然而,也有一些^2条规则,不要让语言不是上下文无关.您将在早期错误的描述中找到概述,这可能会使程序代码无效.该对象文字不得包含重复的属性名称,并且函数参数列表不得包含重复标识符,这是两个无法使用(有限)无上下文语法表达的规则.
我的直觉告诉我,自动分号插入落在同一个盒子里,但我认为它的规则太复杂了甚至不能在这里尝试证明.

_{1:实际上它使用两个语法,一个词法和一个语法,其中第一个在分词表达式和正则表达式之间消除歧义,并产生作为第二个语法输入的标记.
2:与其他编程语言相比,实际上相当少}

Answer 2

没有编程语言(完全)没有上下文(我想说包括CSS).尽管可以使用无上下文语法(CFG)来定义/生成该语言的编译器/解析器.

简单的事实(例如)需要首先定义变量,在使用之前,或者涉及标识符的声明应该是唯一的,这使得语言" 上下文敏感 ".

(编程)语言的语法应该描述(并生成)只是该语言中有效程序的字符串(语法,但也是语义上的).然而,CFG可以描述和生成不是有效程序的字符串(给定语言语义和规范).描述有效程序的条件(例如:1.class需要在使用前定义new class(),2.ids必须匹配等)需要上下文敏感性.

无CFG(与任何有限数量的制作的)能正确表示只有有效字符串这种语言::,这里应该是相同的,,(它应该匹配).注意,确实可以为这种语言的(超集)定义CFG,但它也会接受无效字符串和有效字符串(然后通过其他方式过滤掉它们),这不是语言的语法规范应该做的.它应该只接受有效的字符串并拒绝无效的字符串.与统计学类比,可以说语言的语法规范应该消除/最小化Type-I(拒绝有效字符串)和Type-II(接受无效字符串)错误,而不仅仅是其中之一.{ anbncnn >= 1 }nabc

让我在JavaScript的上下文中给出一个简单的例子(因为变量似乎对JavaScript没有任何问题).

在JavaScript中(在严格模式下),重复的命名函数声明无效.所以这是无效的:

function duplicateFunc(){}
function duplicateFunc(){} // duplicate named function declaration

所以程序不正确,但CFG无法处理这种情况.

即使打开严格模式本身也是上下文敏感的 严格模式规则的一个子集可以通过在案例中拆分 CFG并根据@ Bergi的答案进行相应解析来处理(严格模式示例已删除)

[UPDATE]

我将尝试给出一些JavaScript非上下文代码的示例,这些代码不需要"严格模式"(对建议/更正开放).

使用的保留字 /关键字是在语法的延伸部(或限制).这是一个无关的功能,因此以下示例应作为非CF行为的示例.

var var; // identifier using reserved name
var function; // identifier using reserved name
obj.var; // reserved name used as (explicit) property
obj["var"]; // this is fine!!
Object++; // built-in type used as numeric variable

[/ UPDATE]

因此,上下文在正确解析程序中起作用.正如所说的" 背景就是一切 "!

然而,这种上下文敏感性可以通过对无上下文语法(例如属性语法,词缀语法,TAG语法等)的轻微扩展来处理(希望),这仍然有效地解析(意味着在多项式时间中).

[UPDATE]

" 我会说包括CSS "

详细说明这个陈述.CSS1将是CF,但作为CSS规范增加了更多的功能inclufing variable支持(例如css-counters)它使得CSS代码上下文敏感的在上述感测(例如,变量需要被前文定义中使用).所以下面的css代码将被浏览器解析(并且因为它无效而被忽略)但是它不能用a来描述CFG

body { }
h3::before {
  counter-increment: section;               /* no counter section has been defined, not valid css code */
  content: "Section" counter(section) ": "; /* Display the counter */
}

[/ UPDATE]