Grammar composer

A library to define, build and efficiently parse context-free grammars.

* Grammars are defined using TypeScript class declarations
* No need for separate tokenization step. Tokenization is defined as part of the grammar via embedded Pattern objects that are internally processed through the regexp-composer regular expression library
* The generated parser accepts raw characters as input, meaning it's a form of lexer-free, or hybrid parser, supporting contextual tokenization - that is, low-level character patterns can be specialized to different high-level parser contexts, and sub-patterns captured in the low-level regular expressions are directly embedded as part of the resulting parse tree
* Top-down parsing (roughly equivalent to PEG parsing), with optional "packrat" caching that can be enabled or disabled for individual productions
* Supports right-recursion, but will currently error when left-recursion is detected
* Uses sophisticated static analysis to automatically identify and annotate optional productions
* Provides useful parse-time error reporting, identifying the exact production involved and most likely alternatives at the failed position

Installation

``
npm install grammar-composer
`

And also the related regular expression builder package:
`
npm install regexp-composer
`

Example: XML grammar

The grammar is defined within a container class XmlGrammar. It contains a mixture of higher-level, context-free productions and lower-level, regular expression productions.

* Context-free grammar productions are defined by anonymous functions () => ...
* Regular expression productions are defined by pattern(...)

In this example, context-free operators are prefixed with G, and regular expression operators are prefixed with R, to avoid confusion between similarly named operators:
`ts
import * as G from 'grammar-composer'
import * as R from 'regexp-composer'

export class XmlGrammar {
document = () => [
G.zeroOrMore(
G.anyOf(
this.textFragment,
this.openingTag,
this.closingTag,
this.comment,
this.declarationTag,
)
)
]

textFragment = G.pattern([
R.oneOrMore(R.notAnyOfChars('<'))
])

openingTag = () => [
this.openingTagStart,

G.zeroOrMore(this.attribute),

this.tagEnd
]

openingTagStart = G.pattern([
'<',

R.possibly('?'),

R.captureAs('tagName',
R.oneOrMore(R.notAnyOfChars(R.whitespace, '"', "'", '?', '!', '/', '>'))
),

R.zeroOrMore(R.whitespace),
])

tagEnd = G.pattern([
R.zeroOrMore(R.whitespace),

R.possibly(R.anyOf('/', '?')),

'>'
])

attribute = G.pattern([
R.zeroOrMore(R.whitespace),

R.captureAs('attributeName',
R.oneOrMore(R.notAnyOfChars(R.whitespace, '=', '"', "'", '?', '/', '>'))
),

R.zeroOrMore(R.whitespace),

R.possibly([
'=',

R.zeroOrMore(R.whitespace),

quotedString,

R.zeroOrMore(R.whitespace),
])
])

closingTag = G.pattern([
'

R.zeroOrMore(R.whitespace),

R.captureAs('tagName',
R.oneOrMore(R.notAnyOfChars(R.whitespace, '/', '>'))
),

R.zeroOrMore(R.whitespace),

'>'
])

declarationTag = () => [
this.declarationTagOpening,

G.zeroOrMore(this.declarationTagAttribute),

this.tagEnd
]

declarationTagOpening = G.pattern([
'

R.captureAs('tagName',
R.oneOrMore(R.notAnyOfChars(R.whitespace, '"', "'", '/', '>'))
),

R.zeroOrMore(R.whitespace)
])

declarationTagAttribute = G.pattern([
R.zeroOrMore(R.whitespace),

R.anyOf(
R.captureAs('attributeName',
R.oneOrMore(R.notAnyOfChars(R.whitespace, '"', "'", '/', '!', '?', '>'))
),

quotedString,
),

R.zeroOrMore(R.whitespace),
])

comment = G.pattern([
''
])
}

const quotedString = R.anyOf(
[
'"',
R.captureAs('doubleQuotedStringContent',
R.zeroOrMore(R.notAnyOfChars('"'))
),
'"'
],
[
"'",
R.captureAs('singleQuotedStringContent',
R.zeroOrMore(R.notAnyOfChars("'"))
),
"'"
],
)
`

Building and parsing using the XML grammar:

`ts
import { buildGrammar } from 'grammar-composer'

const xmlString =

// Build the grammar. 'document' is the starting production.
//
// Although XmlGrammar is defined as a class, there's no need to instantiate it,
// just pass it as it is.
const grammar = buildGrammar(XmlGrammar, 'document')

// Parse the XML string with the built grammar
const parseTree = grammar.parse(xmlString)
`

The resulting parse tree looks like:

`ts
[
{
"name": "document",
"startOffset": 0,
"endOffset": 644,
"sourceText": "\n\n\n