Gramática

JavaScript tem uma das gramáticas mais difíceis de analisar; este tutorial registra o trabalho e os tropeços ao aprendê-la.

Gramática LL(1)

Segundo a Wikipedia,

an LL grammar is a context-free grammar that can be parsed by an LL parser, which parses the input from Left to right

O primeiro L significa varrer o código da esquerda para a direita; o segundo L refere-se à derivação pela esquerda.

“Livre de contexto” e o (1) em LL(1) indicam que dá para montar a árvore olhando apenas o próximo token.

LL(1) é popular na academia porque permite gerar parsers automaticamente sem escrever à mão — mas a maior parte das linguagens industriais não tem uma gramática LL(1) feliz, e JavaScript entra nessa estatística.

INFO

Há alguns anos a Mozilla começou jsparagus e escreveu um gerador LALR em Python. Poucas atualizações recentes; ao fim de js-quirks.md a mensagem é clara:

What have we learned today?
Do not write a JS parser.
JavaScript has some syntactic horrors in it. But hey, you don't make the world's most widely used programming language by avoiding all mistakes. You do it by shipping a serviceable tool, in the right circumstances, for the right users.

Na prática, escrever descida recursiva manual é quase inevitável por causa da própria gramática. Vamos percorrer os detalhes antes de tomar decisões ruins na implementação.

Lista do simples ao intricado — pegue um café e vá com calma.

Identificadores

Na spec (#sec-identifiers) existem três formas:

IdentifierReference[Yield, Await] :
BindingIdentifier[Yield, Await] :
LabelIdentifier[Yield, Await] :

estree (e algumas ASTs) não distingue esses casos, e a especificação textual não explica de forma didática.

BindingIdentifier declara; IdentifierReference referencia vínculos existentes. Em var foo = bar, foo é BindingIdentifier, bar é IdentifierReference:

VariableDeclaration[In, Yield, Await] :
    BindingIdentifier[?Yield, ?Await] Initializer[?In, ?Yield, ?Await] opt

Initializer[In, Yield, Await] :
    = AssignmentExpression[?In, ?Yield, ?Await]

Seguindo até PrimaryExpression:

PrimaryExpression[Yield, Await] :
    IdentifierReference[?Yield, ?Await]

Modelar isso separado no AST facilita muito análise semântica posterior.

rust

pub struct BindingIdentifier {
    pub node: Node,
    pub name: Atom,
}

pub struct IdentifierReference {
    pub node: Node,
    pub name: Atom,
}

Classe e modo estrito

Classes ECMAScript nasceram depois do modo estrito; todo o corpo de classe é strict. Em #sec-class-definitions aparece a nota explícita (A class definition is always strict mode code).

Associar modo estrito a escopos de função é mecânico; class, porém, não define escopo lexical próprio — o parser ganha estado extra só para esse caso.

rust

// https://github.com/swc-project/swc/blob/f9c4eff94a133fa497778328fa0734aa22d5697c/crates/swc_ecma_parser/src/parser/class_and_fn.rs#L85
fn parse_class_inner(
    &mut self,
    _start: BytePos,
    class_start: BytePos,
    decorators: Vec<Decorator>,
    is_ident_required: bool,
) -> PResult<(Option<Ident>, Class)> {
    self.strict_mode().parse_with(|p| {
        expect!(p, "class");

Octal legado e `use strict`

#sec-string-literals-early-errors proíbe octal escapado em string "\01" em modo estrito:

EscapeSequence ::
    LegacyOctalEscapeSequence
    NonOctalDecimalEscapeSequence

É um erro de sintaxe se o texto-fonte correspondido por esta produção for código em modo estrito.

O léxico costuma detectar junto ao parser perguntando o estado de strict mode.

Mas com diretivas tudo quebra:

javascript

https://github.com/tc39/test262/blob/747bed2e8aaafe8fdf2c65e8a10dd7ae64f66c47/test/language/literals/string/legacy-octal-escape-sequence-prologue-strict.js#L16-L19

use strict vem depois do octal; ainda assim precisa erro de sintaxe. Felizmente código real não costuma misturar — apenas o caso test262 citado acima.

Parâmetros não simples e modo estrito

Duplicando parâmetros é permitido fora do strict: function foo(a, a) { }, mas "use strict" impede (function foo(a, a) { "use strict" }). ES6 trouxe formulários elaborados tipo function foo({ a }, b = c) {}.

E quando "01" (erro estrito) aparece assim?

javascript

function foo(
  value = (function() {
    return "\01";
  }()),
) {
  "use strict";
  return value;
}

Do ponto de vista do parser: o que fazer se o erro estrito aparece dentro da lista de parâmetros?

#sec-function-definitions-static-semantics-early-errors fecha a porta:

FunctionDeclaration :
FunctionExpression :

É um erro de sintaxe se FunctionBodyContainsUseStrict de FunctionBody for verdadeiro e IsSimpleParameterList de FormalParameters for falso.

O Chrome diz algo opaco tipo Illegal 'use strict' directive in function with non-simple parameter list. Artigo recomendável: Nicholas C. Zakas.

INFO

Curiosidade: com target: es5 no TypeScript a regra some e vira código transpilado estilo:

javascript

function foo(a, b) {
  "use strict";
  if (b === void 0) b = "\01";
}

Expressão entre parênteses

À primeira vista só agrupamento? Na gramática oficial ((x)) pode colapsar em um único IdentifierReference.

Porém há efeitos de runtime conforme #194 do estree:

javascript

> fn = function () {};
> fn.name
< "fn"

> (fn) = function () {};
> fn.name
< ''

Acorn/Babel ganharam opção preserveParens por compatibilidade.

Declaração de função dentro de `if`

Em #sec-ecmascript-language-statements-and-declarations, Declaration não entra dentro de Statement “puro”; porém Annex B (#sec-functiondeclarations-in-ifstatement-statement-clauses) permite, fora strict, funções no lugar de comando em cada ramo:

javascript

if (x) {
  function foo() {}
} else function bar() {}

Rótulos são sintaxe válida

Pouca gente usa label, mas é JS moderno e strict não proíbe.

No JSX abaixo o trecho é LabelledStatement, não literal de objeto:

javascript

<Foo
  bar={() => {
    baz: "quaz";
  }}
/>
//   ^^^^^^^^^^^ `LabelledStatement`

`let` não é palavra-chave

let não é keyword reservada globalmente: pode aparecer na maioria dos lugares salvo onde a gramática veta. O parser precisa olhar o token seguinte:

javascript

let a;
let = foo;
let instanceof x;
let + 1;
while (true) let;
a = let[0];

`for-in` / `for-of` e o parâmetro `[In]`

#prod-ForInOfStatement assusta de primeira. Dois nós: [lookahead ≠ let] e [+In].

Depois de for (let, o lookahead não pode ser in (evita for (let in)), mas precisa permitir {, [ ou identificador para padrões for (let {} = foo) etc.

Ao chegar em in ou of, o lado direito passa com [+In] correto para não confundir o operador in de RelationalExpression com o in do for:

RelationalExpression[In, Yield, Await] :
    [+In] RelationalExpression[+In, ?Yield, ?Await] in ShiftExpression[?Yield, ?Await]
    [+In] PrivateIdentifier in ShiftExpression[?Yield, ?Await]

Nota 2: O parâmetro gramatical `[In]` evita confundir o operador `in` em uma expressão relacional com o `in` de uma instrução `for`.

Esse é praticamente o único uso global de [In]. Ainda há [lookahead ∉ { let, async of }] bloqueando for (async of …) — precisa guard explícito.

Declarações de função em bloco (Annex B)

#sec-block-level-function-declarations-web-legacy-compatibility-semantics explica páginas de comportamento; em termos de implementação lembre do que o Acorn documenta em escopo:

javascript

https://github.com/acornjs/acorn/blob/11735729c4ebe590e406f952059813f250a4cbd1/acorn/src/scope.js#L30-L35

Dentro de função, function aninhada em bloco se comporta como var — daí redeclaração ilegal se misturar var e function no mesmo bloco:

javascript

function foo() {
  if (true) {
    var bar;
    function bar() {} // erro de redeclaração
  }
}

No corpo da função sem bloco intermediário funciona:

javascript

function foo() {
  var bar;
  function bar() {}
}

Parâmetros de contexto gramatical

Cinco parâmetros guiam o que é permitido: [In], [Return], [Yield], [Await], [Default]. Exemplo de flags no parser (Biome/Rome legado):

rust

// https://github.com/rome/tools/blob/5a059c0413baf1d54436ac0c149a829f0dfd1f4d/crates/rome_js_parser/src/state.rs#L404-L425

pub(crate) struct ParsingContextFlags: u8 {
    /// Whether the parser is in a generator function like `function* a() {}`
    /// Matches the `Yield` parameter in the ECMA spec
    const IN_GENERATOR = 1 << 0;
    /// Whether the parser is inside a function
    const IN_FUNCTION = 1 << 1;
    /// Whatever the parser is inside a constructor
    const IN_CONSTRUCTOR = 1 << 2;

    /// Is async allowed in this context. Either because it's an async function or top level await is supported.
    /// Equivalent to the `Async` generator in the ECMA spec
    const IN_ASYNC = 1 << 3;

    /// Whether the parser is parsing a top-level statement (not inside a class, function, parameter) or not
    const TOP_LEVEL = 1 << 4;

    /// Whether the parser is in an iteration or switch statement and
    /// `break` is allowed.
    const BREAK_ALLOWED = 1 << 5;

    /// Whether the parser is in an iteration statement and `continue` is allowed.
    const CONTINUE_ALLOWED = 1 << 6;

Alterne os bits conforme a gramática.

`AssignmentPattern` versus `BindingPattern`

No estree, o lado esquerdo de AssignmentExpression é Pattern:

extend interface AssignmentExpression {
    left: Pattern;
}

O mesmo vale para VariableDeclarator:

interface VariableDeclarator <: Node {
    type: "VariableDeclarator";
    id: Pattern;
    init: Expression | null;
}

Mas na especificação o mesmo trecho sintático pode ser referência ou binding:

javascript

// AssignmentExpression:
{ foo } = bar;
  ^^^ IdentifierReference
[ foo ] = bar;
  ^^^ IdentifierReference

// VariableDeclarator
var { foo } = bar;
      ^^^ BindingIdentifier
var [ foo ] = bar;
      ^^^ BindingIdentifier

Se o enum interno for só Pattern::Identifier, não dá para saber sem inspecionar pais na árvore. A própria spec separa AssignmentPattern e BindingPattern — vale modelar dois enums:

13.15 Assignment Operators

AssignmentExpression[In, Yield, Await] :
    LeftHandSideExpression[?Yield, ?Await] = AssignmentExpression[?In, ?Yield, ?Await]

13.15.5 Destructuring Assignment

In certain circumstances when processing an instance of the production
AssignmentExpression : LeftHandSideExpression = AssignmentExpression
the interpretation of LeftHandSideExpression is refined using the following grammar:

AssignmentPattern[Yield, Await] :
    ObjectAssignmentPattern[?Yield, ?Await]
    ArrayAssignmentPattern[?Yield, ?Await]

14.3.2 Variable Statement

VariableDeclaration[In, Yield, Await] :
    BindingIdentifier[?Yield, ?Await] Initializer[?In, ?Yield, ?Await]opt
    BindingPattern[?Yield, ?Await] Initializer[?In, ?Yield, ?Await]

rust

enum BindingPattern {
    BindingIdentifier,
    ObjectBindingPattern,
    ArrayBindingPattern,
}

enum AssignmentPattern {
    IdentifierReference,
    ObjectAssignmentPattern,
    ArrayAssignmentPattern,
}

Eu fiquei uma semana confuso até perceber: precisamos de dois tipos diferentes em vez de um Pattern genérico. A gramática supplemental de AssignmentPattern aparece como subseção 5 de “13.15 Assignment Operators” depois das runtime semantics — fácil de não notar 😉.

TIP

Os trechos a seguir são especialmente densos (“here be dragons”).

Gramática ambígua

Dado um /, divisão ou início de RegExp?

javascript

a / b;
a / / regex /;
a /= / regex /;
/ regex / / b;
/=/ / /=/;

A gramática sintática orienta o léxico (#sec-ecmascript-language-lexical-grammar):

There are several situations where the identification of lexical input elements is sensitive to the syntactic grammar context that is consuming the input elements.

Ou seja, o parser manda qual “meta léxica” usar. Quando um literal RegExp cabe na posição atual, vale InputElementRegExp; caso contrário InputElementDiv:

InputElementDiv ::
    WhiteSpace
    LineTerminator
    Comment
    CommonToken
    DivPunctuator <---------- the `/` and `/=` token
    RightBracePunctuator

InputElementRegExp ::
    WhiteSpace
    LineTerminator
    Comment
    CommonToken
    RightBracePunctuator
    RegularExpressionLiteral <-------- the `RegExp` token

Percorrendo a / / regex /:

a / / regex /
^ ------------ PrimaryExpression:: IdentifierReference
  ^ ---------- MultiplicativeExpression: MultiplicativeExpression MultiplicativeOperator ExponentiationExpression
    ^^^^^^^^ - PrimaryExpression: RegularExpressionLiteral

Fluxo vai para ExpressionStatement até PrimaryExpression. Antes da primeira / ainda não estamos esperando regexp → InputElementDiv. Para o lado direito esperamos ExponentiationExpression; segunda / inicia regexp porque a gramática naquele ponto admite RegularExpressionLiteral.

RegularExpressionLiteral ::
    / RegularExpressionBody / RegularExpressionFlags

INFO

Exercício: faça o mesmo para /=/ / /=/.

Cover grammar

Leia antes o post do V8. Há três cover grammars principais na spec:

`CoverParenthesizedExpressionAndArrowParameterList`

PrimaryExpression[Yield, Await] :
    CoverParenthesizedExpressionAndArrowParameterList[?Yield, ?Await]

Ao processar uma instância da produção
PrimaryExpression[Yield, Await] : CoverParenthesizedExpressionAndArrowParameterList[?Yield, ?Await]
    a interpretação de CoverParenthesizedExpressionAndArrowParameterList é refinada com a gramática seguinte:

ParenthesizedExpression[Yield, Await] :
    ( Expression[+In, ?Yield, ?Await] )

ArrowFunction[In, Yield, Await] :
    ArrowParameters[?Yield, ?Await] [no LineTerminator here] => ConciseBody[?In]

ArrowParameters[Yield, Await] :
    BindingIdentifier[?Yield, ?Await]
    CoverParenthesizedExpressionAndArrowParameterList[?Yield, ?Await]

javascript

let foo = (a, b, c); // SequenceExpression
let bar = (a, b, c) => {}; // ArrowExpression
          ^^^^^^^^^ CoverParenthesizedExpressionAndArrowParameterList

Se os escopos são construídos durante o parse, fica ambíguo — esbuild descreve escopos temporários e ajustes posteriores.

`CoverCallExpressionAndAsyncArrowHead`

CallExpression :
    CoverCallExpressionAndAsyncArrowHead

Ao processar uma instância da produção
CallExpression : CoverCallExpressionAndAsyncArrowHead
a interpretação de CoverCallExpressionAndAsyncArrowHead é refinada com a gramática seguinte:

CallMemberExpression[Yield, Await] :
    MemberExpression[?Yield, ?Await] Arguments[?Yield, ?Await]

AsyncArrowFunction[In, Yield, Await] :
    CoverCallExpressionAndAsyncArrowHead[?Yield, ?Await] [no LineTerminator here] => AsyncConciseBody[?In]

CoverCallExpressionAndAsyncArrowHead[Yield, Await] :
    MemberExpression[?Yield, ?Await] Arguments[?Yield, ?Await]

Ao processar uma instância da produção
AsyncArrowFunction : CoverCallExpressionAndAsyncArrowHead => AsyncConciseBody
a interpretação de CoverCallExpressionAndAsyncArrowHead é refinada com a gramática seguinte:

AsyncArrowHead :
    async [no LineTerminator here] ArrowFormalParameters[~Yield, +Await]

javascript

async (a, b, c); // chamada qualquer primeiro async
async (a, b, c) => {} // função arrow assíncrona
^^^^^^^^^^^^^^^ CoverCallExpressionAndAsyncArrowHead

`CoverInitializedName`

13.2.5 Object Initializer

ObjectLiteral[Yield, Await] :
    ...

PropertyDefinition[Yield, Await] :
    CoverInitializedName[?Yield, ?Await]

Nota 3: Em determinados contextos, ObjectLiteral é usado como cover grammar para uma gramática secundária mais restrita.
A produção CoverInitializedName é necessária para cobrir plenamente essas gramáticas secundárias. Contudo, o uso dessa produção resulta em erro de sintaxe antecipado em contextos normais onde se espera um ObjectLiteral propriamente dito.

13.2.5.1 Static Semantics: Early Errors
...
PropertyDefinition : CoverInitializedName
    É um erro de sintaxe se qualquer texto-fonte for correspondido por esta produção.

13.15.1 Static Semantics: Early Errors

AssignmentExpression : LeftHandSideExpression = AssignmentExpression
Se LeftHandSideExpression for um ObjectLiteral ou um ArrayLiteral, aplicam-se as seguintes regras de erro antecipado:
    * LeftHandSideExpression deve cobrir (*cover*) um AssignmentPattern.

javascript

({ prop = value } = {}); // ObjectAssignmentPattern
({ prop: value }); // ObjectLiteral que dispara SyntaxError fora do contexto de pattern

Exercício: qual = abaixo é inválido?

javascript

let { x = 1 } = ({ x = 1 } = { x: 1 });

Gramática ​

Gramática LL(1) ​

Identificadores ​

Classe e modo estrito ​

Octal legado e use strict ​

Parâmetros não simples e modo estrito ​

Expressão entre parênteses ​

Declaração de função dentro de if ​

Rótulos são sintaxe válida ​

let não é palavra-chave ​

for-in / for-of e o parâmetro [In] ​

Declarações de função em bloco (Annex B) ​

Parâmetros de contexto gramatical ​

AssignmentPattern versus BindingPattern ​

Gramática ambígua ​

Cover grammar ​

CoverParenthesizedExpressionAndArrowParameterList ​

CoverCallExpressionAndAsyncArrowHead ​

CoverInitializedName ​

Gramática

Gramática LL(1)

Identificadores

Classe e modo estrito

Octal legado e `use strict`

Parâmetros não simples e modo estrito

Expressão entre parênteses

Declaração de função dentro de `if`

Rótulos são sintaxe válida

`let` não é palavra-chave

`for-in` / `for-of` e o parâmetro `[In]`

Declarações de função em bloco (Annex B)

Parâmetros de contexto gramatical

`AssignmentPattern` versus `BindingPattern`

Gramática ambígua

Cover grammar

`CoverParenthesizedExpressionAndArrowParameterList`

`CoverCallExpressionAndAsyncArrowHead`

`CoverInitializedName`