ts-parsec

Unlike many parser libraries, ts-parsec does not force you to create Abstract Syntax Trees (ASTs) manually. Instead, the parser naturally produces a data structure that mirrors your grammar.

For example, a grammar defined as A B (C|D) {E F, ...} G can be implemented using combinators like seq, alt, and list_sc. The resulting output type will be a tuple representing the sequence of parsed components: [TA, TB, (TC | TD), [TE, TF][], TG].

To convert these grammar-aligned structures into your own domain-specific data structures (like a custom AST), use the apply combinator. This allows you to perform transformations or calculations during the parsing process itself.

// Example: Converting grammar-aligned tuples to a custom structure
function convertToSomething(value: [TA, TB, (TC | TD), [TE, TF][], TG]): Something {
    // ... transformation logic
}

const myParser = apply(
    seq(A, B, alt(C, D), list_sc(seq(E, F), str(',')), G),
    convertToSomething
);

// To ensure the parser consumes the entire input and returns exactly one result:
const output = expectSingleResult(expectEOF(myParser.parse(myTokenizer.parse(`INPUT`))));

The amb(x) combinator is used to manage ambiguity in a parser. When a parser x produces multiple results that consume the same number of tokens, amb(x) groups those results into a single result containing an array of all possible outcomes.

This is useful for preventing exponential growth in the number of ASTs (Abstract Syntax Trees) generated when a large parser contains ambiguous sub-parsers. Instead of duplicating the entire tree structure for every possible branch, amb allows you to represent the ambiguity locally within the AST. You can then resolve the ambiguity later (e.g., during semantic analysis or symbol table construction) rather than mixing parsing and semantic analysis logic.

// Example of how amb groups results that consume the same tokens
const ab = apply(seq(str('a'), str('b')), () => 'ab');
const bc = apply(seq(str('b'), str('c')), () => 'bc');
const a_bc = apply(seq(str('a'), bc), ([_a, _bc]: [Token<T>, string]) => `a, ${_bc}`);
const ab_c = apply(seq(ab, str('c')), ([_ab, _c_]: [string, Token<T>]) => `${_ab}, c`);

// Without amb, alt(a_bc, ab_c) returns 2 separate results for input 'a b c'
// With amb, amb(alt(a_bc, ab_c)) returns 1 result: ['a, bc', 'ab, c']
const abc = alt(a_bc, ab_c);
const ambiguousResult = amb(abc);

When using apply with seq, the resulting tuple contains every element parsed by the sequence. This often leads to large, unwieldy tuples where you must manually track indices (e.g., value[2], value[5]) to extract useful data.

kleft, kmid, and kright are helper functions designed to discard unwanted parts of a sequence, allowing the apply callback to receive a cleaner, smaller tuple containing only the relevant data. This makes your parsers more resilient to syntax changes because you don't need to update tuple indices if non-essential parts of the syntax are added or removed.

• kleft(a, b): Discards the first part (a) and returns the second part (b). It is equivalent to apply(seq(a, b), (value) => value[1]) (Note: The documentation's specific implementation detail value[0] in the snippet appears to be a typo or specific to a different context, but the conceptual goal is discarding one side to keep the other).
• kmid(a, b, c): Discards the outer parts (a and c) and keeps the middle part (b).
• kright(a, b): Discards the second part (b) and keeps the first part (a).

// Example: Parsing an import statement while discarding syntax noise
apply(
    kmid(
        seq(
            str('import'),
            str('{')
        ),
        seq(
            list_sc(
                tok(TokenKind.Identifier),
                str(',')
            ),
            kright(
                seq(
                    str('}'),
                    str('from'),
                ),
                tok(TokenKind.StringLiteral)
            )
        ),
        str(';')
    ),
    (value: [Token<TokenKind>[], Token<TokenKind>]) => {
        // value now only contains the useful parts: [identifiers, stringLiteral]
        return Using(value[0], value[1]);
    }
)

The rep, repr, and rep_sc combinators are used to match a parser x zero or more times. While they may consume the same input, they differ significantly in the results they return:

• rep(x): Returns all possible prefixes of the matched sequence, from the full sequence down to an empty array. For an input like 1 2 3, it returns [[1, 2, 3], [1, 2], [1], []].
• repr(x): Returns all possible prefixes of the matched sequence, from an empty array up to the full sequence. For an input like 1 2 3, it returns [[], [1], [1, 2], [1, 2, 3]].
• rep_sc(x): Returns only the single result containing the full sequence of matches. For an input like 1 2 3, it returns [[1, 2, 3]].

// Example behavior for input: 1 2 3

// rep returns all prefixes from longest to shortest
rep(tok(TokenKind.Number)); // [[1, 2, 3], [1, 2], [1], []]

// repr returns all prefixes from shortest to longest
repr(tok(TokenKind.Number)); // [[], [1], [1, 2], [1, 2, 3]]

// rep_sc returns only the full sequence
rep_sc(tok(TokenKind.Number)); // [[1, 2, 3]]

When dealing with optionality in ts-parsec, you can choose between three patterns depending on how you want the result to be structured and how you want the parser to handle ambiguity:

1. alt(a, nil<T>()): Returns both the result of a and undefined when a succeeds. Because nil<T>() always succeeds, this pattern always succeeds.
2. opt(a): Similar to the alt pattern above, it returns both the result of a and undefined when a succeeds. It returns undefined when a fails.
3. opt_sc(a): When a succeeds, it returns only the result of a. It returns undefined when a fails.

When to use opt_sc to avoid ambiguity: In complex grammars like TypeScript, using opt can cause ambiguity. For example, in the input {DoSomething();}, if you use opt(str(';')) inside an expression parser, the parser might return both the expression and an undefined semicolon, potentially allowing the input to be interpreted as two separate statements (DoSomething() and ;) instead of one expression statement. opt_sc prevents this by consuming the semicolon and returning only the expression, resolving the ambiguity.

// Example of ambiguity resolution using opt_sc
kmid(
    str('{'),
    opt_sc(alt(
        kleft(EXPRESSION, opt(str(';'))),
        str(';'
    )),
    str('}')
)