JavaScript是一种上下文无关语言吗？ [英] Is JavaScript a Context Free Language?
问题描述
这篇关于浏览器如何工作的文章解释了CSS如何无上下文，而HTML是不。但是，JavaScript的上下文是免费的吗？
This article on how browsers work explains how CSS is context free, while HTML is not. But what about JavaScript, is JavaScript context free?
我正在学习CFG和正式证明，但距离理解如何解决这个问题还有很长的路要走。有没有人知道JavaScript是否没有上下文？
I am learning about CFG and formal proofs, but am a long way away from understanding how to figure this out. Does anyone know if JavaScript is context free or not?
推荐答案
不，JavaScript不是一种无上下文的语言。
No, JavaScript is not a context-free language.
非常接近1，ECMAScript 5规范确实使用上下文 - 免费语法 1 来描述语言的语法（你可以在附件A中找到所有作品）。
It is very close to one, and the ECMAScript 5 specification does indeed use a context-free grammar1 to describe the language's syntax (you can find all productions in Annex A).
当然，它确实对纯无上下文语法产生做了一些扩展，并描述了解析器的额外行为。一个特别的事情是 lookahead 的使用仍然是一种无上下文的语言，但如果语法很复杂，那将会很复杂。它不能用于某些规则。不允许某些事物出现在严格模式代码中是相似的 - 它可以通过调整语法（具有更多的产品）来完成，但是通过离开BNF可以更容易地表达规则。
Of course, it does make some extensions to pure context-free grammatical productions, and describes extra behaviour of the parser. One particular thing is the usage of lookahead which still makes a context-free languages, but would complicate the grammar a lot if it couldn't be used for some rules. Not allowing certain things to appear in strict mode code is similar - it could be done by adjusting the grammar (with far more productions), but the rule is much easier expressed by leaving the BNF.
但是，也有一些 2 规则确实使语言不具有上下文。您可以在 早期错误 的说明中找到概述，这会导致程序代码无效。该对象文字必须不包含重复的属性名称，并且函数参数列表不能包含重复的标识符是两个不能使用（有限的）无上下文语法表达的规则。
我的直觉告诉我自动分号插入落在同一个框中，但我认为它的规则太复杂了，甚至不能在这里尝试证明。
However, there are also some2 rules that do make the language not context-free. You'll find an overview in the description of early errors, which can make a program code invalid. That object literals must not contain duplicate property names and that function parameter lists must not contain duplicate identifiers are two rules that cannot be expressed using (finite) context-free grammars.
My gut tells me that the automatic semicolon insertion falls in the same box, but I think its rules are too complicated to even attempt a proof here.
1：实际上它使用两种语法，一种是 lexical 和一个语法，其中第一个消除除法表达式和正则表达式之间的歧义，并确实产生作为输入的标记到第二个语法。
2：与其他编程语言相比实际上相当少
1: Actually it uses two grammars, a lexical and a syntactical one, where the first disambiguates between division expressions and regular expressions, and does produce the tokens that are the input to the second grammar.
2: Rather few actually, compared to other programming languages
这篇关于JavaScript是一种上下文无关语言吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
