EBNF Grammar to AST Parser

Common errors

• Cannot find module 'ebnf' or its corresponding type declarations.

  cause The `ebnf` package is not installed, or the TypeScript compiler cannot locate its type definitions.
  fix Run `npm install ebnf` (or `yarn add ebnf`) to install the package. If using TypeScript, ensure `tsconfig.json` correctly includes `node_modules/@types` or that the package's bundled types are being picked up.

• TypeError: Cannot read properties of undefined (reading 'Parser')

  cause This usually occurs when trying to access `Grammars.BNF.Parser` or `Grammars.W3C.Parser` but `Grammars` itself is undefined or incorrectly imported.
  fix Verify that `import { Grammars } from 'ebnf';` is used correctly and that the package is installed. If using CommonJS, ensure `const { Grammars } = require('ebnf');` is being used, though ESM imports are preferred.

• Error: Invalid grammar, production 'SomeRule' is not defined.

  cause A non-terminal rule referenced in the grammar (e.g., `<SomeRule>`) does not have a corresponding definition in the provided grammar string.
  fix Review your EBNF/BNF grammar string and ensure all referenced non-terminal rules are explicitly defined. Check for typos in rule names.

• Error: Line X, column Y: Unexpected token 'Z'.

  cause The parser encountered a token (character or sequence) in the input string that does not match any expected rule at that position according to the grammar.
  fix Inspect the input string at the specified line and column. Compare it against your grammar definition to identify which rule is failing to match. This often points to incorrect grammar syntax, missing terminals, or an input string that doesn't conform to the defined language. Consider simplifying the grammar or the input to isolate the issue.

Warnings

• gotcha Version 1.9.1 included a fix to 'remove eval' from the internal implementation. While not explicitly marked as a breaking change for external API, prior versions might have used `eval` internally, which can carry security risks if not properly sandboxed, especially if user-supplied grammar definitions were possible.
  Fix: Upgrade to version 1.9.1 or later to mitigate potential security implications related to `eval` usage. Ensure all grammar definitions, especially those originating from untrusted sources, are thoroughly validated before being passed to the parser.
• gotcha The library differentiates between two EBNF styles: standard BNF and W3C EBNF (compatible with Railroad Diagram Generator). Grammars must adhere strictly to one of these two forms for correct parsing. Mixing notations or using unsupported EBNF extensions will lead to parsing errors.
  Fix: Explicitly choose either `Grammars.BNF.Parser` or `Grammars.W3C.Parser` and ensure your grammar strictly follows the conventions of the chosen format. Consult the respective specifications (BNF, W3C EBNF) for syntax details.
• gotcha By default, rules defined with `ALL_UPPER_AND_SNAKE_CASE` in the grammar are not emitted in the resulting AST, simplifying the tree for common use cases like whitespace or comments. This behavior can be surprising if you expect all defined rules to appear in the AST.
  Fix: If you need `ALL_UPPER_AND_SNAKE_CASE` rules to be present in the AST, you can deactivate this default behavior by setting the `keepUpperRules: true` flag in the parser's options (if supported, verify against latest documentation/source). Otherwise, design your grammar to use different naming conventions for rules intended to be part of the AST.

Install

• npm install ebnf npm
• yarn add ebnf yarn
• pnpm add ebnf pnpm

Imports

• Grammars
  wrong:

  const Grammars = require('ebnf');

  correct:

  import { Grammars } from 'ebnf';

  While CommonJS `require` might work in some environments (e.g., Webpack), ESM `import` is the idiomatic and recommended way to access `Grammars`.
• Grammars.BNF.Parser
  wrong:

  import { BNF } from 'ebnf'; // Incorrect path, BNF is nested

  correct:

  import { Grammars } from 'ebnf';
  const bnfParser = new Grammars.BNF.Parser(bnfGrammar);

  The Parser classes are nested under `Grammars.BNF` and `Grammars.W3C` respectively.
• Grammars.W3C.Parser
  wrong:

  import { W3CParser } from 'ebnf';

  correct:

  import { Grammars } from 'ebnf';
  const w3cParser = new Grammars.W3C.Parser(w3cGrammar);

  Ensure correct capitalization and nesting when accessing the W3C Parser class.

Quickstart

This quickstart demonstrates how to define a simple arithmetic grammar using BNF, create a parser instance, and then use it to generate an Abstract Syntax Tree (AST) for a given expression.

import { Grammars } from 'ebnf';

const mathGrammar = `
<Equation>         ::= <BinaryOperation> | <Term>
<Term>             ::= "(" <RULE_WHITESPACE> <Equation> <RULE_WHITESPACE> ")" | "(" <RULE_WHITESPACE> <Number> <RULE_WHITESPACE> ")" | <RULE_WHITESPACE> <Number> <RULE_WHITESPACE>
<BinaryOperation>  ::= <Term> <RULE_WHITESPACE> <Operator> <RULE_WHITESPACE> <Term>

<Number>           ::= <RULE_NEGATIVE> <RULE_NON_ZERO> <RULE_NUMBER_LIST> | <RULE_NON_ZERO> <RULE_NUMBER_LIST> | <RULE_DIGIT>
<Operator>         ::= "+" | "-" | "*" | "/" | "^"

<RULE_NUMBER_LIST> ::= <RULE_DIGIT> <RULE_NUMBER_LIST> | <RULE_DIGIT>
<RULE_NEGATIVE>    ::= "-"
<RULE_NON_ZERO>    ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<RULE_DIGIT>       ::= "0" | <RULE_NON_ZERO>
<RULE_WHITESPACE>  ::= <RULE_WS> | ""
<RULE_WS>          ::= " " <RULE_WHITESPACE> | "\n" <RULE_WHITESPACE> | " " | "\n"
`;

// Create a BNF parser instance with the defined grammar
const parser = new Grammars.BNF.Parser(mathGrammar);

// Parse an arithmetic expression and get the Abstract Syntax Tree (AST)
const ast = parser.getAST('(2 + (2 * -123)) * 5332');

console.log(JSON.stringify(ast, null, 2));

/*
Expected AST structure (simplified representation):
{
  "type": "Equation",
  "text": "(2 + (2 * -123)) * 5332",
  "children": [
    // ... detailed AST nodes for operations and numbers
  ]
}
*/