NPeg: Nim Parsing Expression Grammars

Unlike regular expressions, PEGs in NPeg are always matched in anchored mode. This means the pattern must match from the start of the subject string. For example, the pattern "bar" will not match the string "foobar".

To perform a search (finding a pattern anywhere in a string), you can use a recursive construct or the built-in @P operator.

Manual search pattern:

p <- "bar"
search <- p | 1 * search

By default, PEGs do not care if there is remaining text in the subject string after a successful match. To ensure a pattern matches exactly to the end of the string, use the idiomatic notation !1 (meaning "succeed only if there is not a single character left to match").

rule <- pattern !1

NPeg uses a syntax similar to standard PEG notation but with specific modifications to ensure compatibility with the Nim compiler. Key differences include:

• Prefix Quantifiers: Operators like *, +, -, and ? are used as prefixes (e.g., *P) rather than suffixes.
• Ordered Choice: Uses the | operator instead of / to avoid operator precedence conflicts.
• Explicit Sequence: Uses the * infix operator for concatenation (e.g., P1 * P2).

NPeg patterns are composed of Atoms (the basic building blocks), Operators (which combine atoms), and Precedence Operators (for building Pratt parsers).

The lookahead (&) and not (!) operators are non-consuming; they do not advance the parser state. Any captures made inside these blocks are discarded when the parser state is rolled back.

Note: If you need to capture content within a non-consuming block, use a code block capture, as these are always executed even if the parser state is rolled back.

The peg macro allows you to define named rules that can refer to one another, enabling recursion.

Rule Ordering and Performance: The order in which you define rules in a peg block affects how the parser is generated:

• Inlining: If rule P1 refers to P2 and P2 is defined before P1, P2 is inlined into P1. This increases code size but improves performance.
• Subroutines: If rule P1 refers to P2 and P2 is defined after P1, P2 is generated as a subroutine. This reduces code size but may result in a slower parser.

let parser = peg "ident":
  lower <- {'a'..'z'}
  ident <- *lower
doAssert parser.match("lowercaseword").ok

NPeg can parse subjects of type openArray[T] (e.g., a token stream) instead of just strings.

Requirements:

• The peg() macro must be passed an additional argument specifying the base type T of the subject.
• If no type is provided, it defaults to char (parsing string).

Grammar Adjustments for Non-Strings:

• Literals: Standard string/character atoms may not work. Use square brackets [literal] to specify any Nim code as a literal (e.g., [foo], [1+1], or ["foo"]).
• Captures: Captures are limited to a single element of the base type T.

Note: This is an experimental feature and the API may change.

To follow the DRY (Don't Repeat Yourself) principle, you can create templates. Templates are parameterized rules that perform a basic search-and-replace of arguments within the rule definition.

Defining a simple template:

commaList(item) <- item * *( ',' * item )
numberList <- commaList(+Digit)
wordList <- commaList(+Alpha)

Defining nested/recursive templates:

list(item, sep) <- item * *( sep * item )
commaList(item) <- list(item, ',')
numberList <- commaList(+Digit)
wordList <- commaList(+Alpha)

NPeg supports experimental precedence operators to build Pratt parsers (precedence climbing) for programming languages. This allows you to define associativity and precedence levels directly in the grammar.

• Left associative precedence of N: P ^ N
• Right associative precedence of N: P ^^ N

When P ^ N is matched, if N is higher than or equal to the current precedence, parsing fails and backtracks. If N is lower, the current precedence is updated to N. P ^ 0 resets the precedence to 0, which is useful for sub-expressions in parentheses.

Example Pratt Parser Structure

exp <- prefix * *infix

parenExp <- ( "(" * exp * ")" ) ^ 0

prefix <- number | parenExp

infix <- {'+','-'} * exp ^ 1 |
         {'*','/'} * exp ^ 2 |
         {'^'}     * exp ^^ 3

Backreferences allow you to match a string that was previously matched by another part of the grammar.

NPeg provides the R operator for two purposes:

1. R(name, P): Creates a named reference for pattern P. This stores the result of P under name.
2. R(name): Matches the exact content that was previously stored in the named reference name.

Example: Matching a string where the first and last characters are identical:

# Pattern: R("c", 1) * *(1 - R("c")) * R("c") * !1
# 1. R("c", 1) matches any single character and stores it as "c"
# 2. *(1 - R("c")) matches zero or more characters that are NOT "c"
# 3. R("c") matches the character stored in "c"

NPeg does not support left recursion, which will cause infinite loops.

Examples of problematic patterns:

• Direct left recursion: A <- A | 'a'
• Mutual left recursion: A <- B | 'a' A; B <- A
• Loops matching empty strings: *0 will cause the parser to stall and loop infinitely.