@nrsk/sigma

𝝨 sigma

TypeScript parser combinator library for building fast and convenient parsers.

Features

• [x] Capable of parsing LL grammars using recursive descent with backtracking.
• [x] Ergonomic API with excellent TypeScript support.
• [x] Zero dependencies. Supports tree shaking.
• [x] Performant enough to beat similar parser combinator libraries.

All-in-all, Sigma is easy to use and extend, reasonably fast and convenient, but a bit limited regarding what types of grammars it can parse.

Docs

You can find the documentation here. If you want to contribute, feel free to check out the source code.

Installation

Node

Just use your favorite package manager.

npm i @nrsk/sigma

Deno

You can import the library via Skypack (note the ?dts query parameter, this is to pull types):

import { ... } from 'https://cdn.skypack.dev/@nrsk/sigma?dts'
import { ... } from 'https://cdn.skypack.dev/@nrsk/sigma/parsers?dts'
import { ... } from 'https://cdn.skypack.dev/@nrsk/sigma/combinators?dts'

Example

Below is an example of parsing nested tuples like (1, 2, (3, 4)) into an AST.

Click to show the tuples example.

import { choice, map, optional, sepBy, sequence, takeMid } from '@nrsk/sigma/combinators'
import { defer, integer, run, string, whitespace } from '@nrsk/sigma/parsers'
import type { Span } from '@nrsk/sigma'

/* AST. */

interface NumberNode {
  type: 'number'
  span: Span
  value: number
}

interface ListNode {
  type: 'list'
  span: Span
  value: Array<NumberNode | ListNode>
}

/* Mapping functions to turn parsed string values into AST nodes. */

function toNumber(value: number, span: Span): NumberNode {
  return {
    type: 'number',
    span,
    value
  }
}

function toList(value: Array<NumberNode | ListNode>, span: Span): ListNode {
  return {
    type: 'list',
    span,
    value
  }
}

/* Parsers. */

const OpenParen = string('(')
const CloseParen = string(')')
const Space = optional(whitespace())
const Comma = sequence(Space, string(','), Space)

const TupleNumber = defer<NumberNode>()
const TupleList = defer<ListNode>()

TupleNumber.with(
  map(
    integer(),
    toNumber
  )
)

TupleList.with(
  map(
    takeMid(
      OpenParen,
      sepBy(choice(TupleList, TupleNumber), Comma),
      CloseParen
    ),
    toList
  )
)

Then we simply run the root parser, feeding it with text:

run(TupleList).with('(1, 2, (3, 4))')

And in the end we get the following output with the AST, which can then be manipulated if needed:

{
  isOk: true,
  span: [ 0, 14 ],
  pos: 14,
  value: {
    type: 'list',
    span: [ 0, 14 ],
    value: [
      { type: 'number', span: [ 1, 2 ], value: 1 },
      { type: 'number', span: [ 4, 5 ], value: 2 },
      {
        type: 'list',
        span: [ 7, 13 ],
        value: [
          { type: 'number', span: [ 8, 9 ], value: 3 },
          { type: 'number', span: [ 11, 12 ], value: 4 }
        ]
      }
    ]
  }
}

Development

Fork, clone, then instead of npm install run:

npm run install:all

Note

This will install dependencies for the package itself, and also for docs and benchmarks packages. This is due to limitations of the current repository setup and needed to avoid problems with eslint that runs on pre-commit hook.

This project follows the conventional commits spec and uses a slightly modified commitlint preset for automatic linting commits and generating changelog.

License

MIT.