JavaScript Grammar is Not Context-Free!

By Xah Lee. Date: . Last updated: .
js spec 2015 5.3 static semantic rules
js spec 2015 5.3 static semantic rules ECMAScript 2015 §Notational Conventions#sec-static-semantic-rules

it's say

Context-free grammars are not sufficiently powerful to express all the rules that define whether a stream of input elements form a valid ECMAScript Script or Module that may be evaluated

example would be:

js spec 2015 13.2.1 block static semantics early errors
ECMAScript 2015 §ECMAScript Language: Statements and Declarations#sec-block-static-semantics-early-errors
js spec 2015 14.1.2 static semantics early errors
ECMAScript 2015 §ECMAScript Language: Functions and Classes#sec-function-definitions-static-semantics-early-errors

It is a Syntax Error if any element of the BoundNames of FormalParameters also occurs in the LexicallyDeclaredNames of FunctionBody.

there's some interesting complexities going on in JavaScript grammar.

here's the spec

js spec 2015 5.1.1 context free grammars
ECMAScript 2015 §Notational Conventions#sec-notational-conventions

here's some interesting things.

• they divided the grammar into

and

• Instead of the typical VERTICAL LINE | for rhs alternatives, it uses multiple lines. That is, each line is a alternative.

js es2015 grammar 14393
ECMAScript 2015 §Notational Conventions#sec-grammar-notation

• it uses subscript opt to indicate optional nonterminal, instead of the more traditional square bracket [].

js es2015 grammar 88906

• it uses a subscript [xyz] to represent alternatives of nonterminal on lhs. This is getting complex.

js es2015 grammar 60226

• the subscript [xyz] notation can be on the rhs, and combined with the opt

js es2015 grammar 47266

• now the sub-scripted nonterminal on the rhs, can be prefixed with a question mark, depends on which of the subscribed nonterminal on lhs is used.

js es2015 grammar 17089

• the rhs may start with square bracketed notation like this [+xyz]. It means, this alternative is valid only if the lhs has the same parameter [xyz]. It may start with [~xyz], means, this alternative is valid only if the lhs does not have the same parameter.

js es2015 grammar 49792

• now, comes “not apparently context-free” things. A lookhead notation.

js es2015 grammar 15517

• another non-standard notation, is “[no LineTerminator here]”.

js es2015 grammar 66268

• and now adding plain English word “but not” into the BNF.

js es2015 grammar 02354

Grand Finale: Context-free grammars are not sufficiently powerful to express JavaScript syntax!

js es2015 grammar 00922
ECMAScript 2015 §Notational Conventions#sec-static-semantic-rules

JavaScript Spec Reading