Module: nupp.peg

Parsing-expression grammars#

nupp.peg compiles textual parsing-expression grammars into reusable pure-Lua matchers. The same grammar language works inside comptime and at runtime, and neither path requires LPeg to be installed.

A parsing-expression grammar, or PEG, describes a deterministic top-down parse. Its choice operator is ordered: p / q tries q only if p fails. This differs from a regular expression alternation that may choose whichever alternative makes the complete expression work.

Compiling at either phase#

nupp.peg.compile(source, options?) is the only constructor.

A constant call inside comptime is parsed and validated by the compiler. The compiler derives nupp.peg.Peg<R...> from the validated capture shape, so recognizers, substring and position captures, and collections do not need result annotations. The emitted program receives an already-materialized matcher and does not carry the textual grammar parser unless some runtime call also needs it.

A normal call with literal grammar text gets the same inferred Peg<R...> type. It still compiles at runtime; parsed plans are cached by grammar source and backend, so compiling the same grammar again avoids parsing, lowering, and code-generation work. A genuinely dynamic string returns Peg<...any> because its capture shape is not yet known.

Prefer comptime for source-owned constant grammars. Runtime compilation is for configuration, plugins, user-selected formats, and other genuinely dynamic input.

Every Peg<R...> satisfies nupp.peg.Matcher<R...>. A generic adapter can forward the complete result pack without collecting it into another value:

Matching and positions#

A matcher can be called directly or through match:

Matching begins at byte position 1 unless init is supplied. Positions are 1-based. A negative init counts from the end like Lua string operations. Positions before 1 clamp to 1, and positions after #subject + 1 fail.

A recognizer with no captures returns the byte position immediately after its match. It does not return a boolean. Failure returns nil.

Use find when the grammar may begin after the starting position. It returns the first byte, the exclusive next byte, and every grammar result without constructing a match record.

For Peg<R...>, success has the pack (integer, integer, R...); failure has (nil, nil). The byte range is half-open, [first, nextPosition), so an empty match has equal positions. On failure the positions are nil. Test first for success because a grammar action may successfully return nil or false. A recognizer's third result is the same next-byte position it returns from match.

Use isMatch when only existence matters. It performs the same search and returns only a boolean:

The default init is 1 and its normalization is the same as for match. The position after the last byte is included, allowing an empty or end assertion to match there. Use match when the exact starting position is already known.

Repeated matching#

forEachMatch visits non-overlapping matches without constructing match records or an iterator closure. Its callback receives first, nextPosition, R..., the same values as find, and the return value is the number of visits:

The next search begins at the exclusive end of a consuming match. An empty match instead advances one byte, so an empty grammar cannot repeatedly report the same position. The boundary at #subject + 1 remains eligible and is visited at most once. For example, '' visits positions 1, 2, and 3 in a two-byte subject.

The optional init controls the first position considered and follows find's normalization rules. Text before it is not visited. The visitor's return value is ignored; an error is the way to abort a traversal.

Replacement#

replace replaces the first match, while replaceAll replaces every non-overlapping match. A string replacement is inserted literally:

Replacement strings do not interpret $, %, or capture references. Use a typed callback when replacement text depends on the match. It receives the raw positions followed by every grammar result and must return a string:

Neither operation builds match records. A callback can use a substring capture as above, use another typed grammar result, or slice the original subject with the reported half-open range. When no match exists, the original string is returned. The optional init leaves the prefix before it unchanged.

Empty matches insert without removing a byte. replaceAll then preserves one byte while advancing to the next search position; an empty grammar therefore turns "ab" into "-a-b-" when replacing with "-". This is the same progress rule used by forEachMatch.

Append !. to require the end of the subject and therefore a complete match:

All positions and classes are byte-oriented. The grammar does not decode UTF-8 codepoints. A literal UTF-8 character is matched as its encoded byte sequence, while . consumes one byte rather than one Unicode character.

Expression syntax#

Whitespace between expressions is ignored. A -- comment outside a quoted literal or byte class continues to the end of the line.

Precedence runs from tightest to loosest:

1. primary expressions such as literals, classes, captures, and groups;
2. repetition and capture-transformation suffixes;
3. predicates;
4. sequence;
5. ordered choice /.

Parentheses can make any grouping explicit.

Literals and any byte#

Single-quoted and double-quoted literals match their contents exactly:

'GET'
"Content-Type"

The grammar notation does not process backslash escapes. A backslash in a literal is a literal backslash byte. Use the other quote delimiter when the text contains one kind of quote:

"it's"
'say "yes"'

An empty literal '' succeeds without consuming input. It is occasionally useful in a choice, but it must not appear inside * or + because such a loop could never advance.

. matches any one byte. It fails at the end of the subject.

Byte classes#

Square brackets match one byte from a set. Ranges are inclusive:

[abc]
[a-zA-Z_]
[0-9a-fA-F]

^ immediately after [ complements the class:

[^0-9]

The predefined ASCII classes are:

The one-letter uppercase forms %A, %C, %D, %G, %L, %P, %S, %U, %W, and %X match the complement of their lowercase class. Predefined classes can also appear inside square brackets:

[%a_]
[%w.-]

Class contents are literal bytes except for ranges and % classes. An empty class and a descending range such as [z-a] are errors.

Sequence#

Adjacent expressions form a sequence and must match in order:

'HTTP/' [0-9] '.' [0-9]

Spacing is optional when token boundaries remain clear, but whitespace usually makes grammars easier to read.

Ordered choice#

p / q tries p first and uses q only when p fails:

'GET' / 'POST' / 'PUT'

Put a longer literal before its prefix. With 'in' / 'integer', the first arm succeeds after two bytes and the second arm is never considered. Write 'integer' / 'in' instead, or add a boundary assertion to each arm.

PEG backtracking is local and deterministic. If a later expression fails, the parser can return to a still-open choice and try its next arm. Ordinary -> transformations are deferred until the entire match succeeds, so speculative paths do not run them. Match-time => definitions are intentionally immediate, as in LPeg.

Repetition#

Suffix operators repeat the expression immediately to their left:

Use parentheses to repeat a sequence:

[0-9]+ ('.' [0-9]+)?

Repetition is possessive in PEG fashion. It consumes as much as it can and does not backtrack to a smaller count merely to make a following expression work. A repeated expression must consume at least one byte whenever it succeeds. Nullable repetition, such as ('')*, is rejected rather than allowed to loop forever.

Explicit repetition counts are limited to 4096.

Predicates and end of input#

&p succeeds when p would succeed and consumes nothing. !p succeeds when p would fail and also consumes nothing.

&[a-z] [a-z]+
!('if' !.) [a-z]+ !.

The first expression requires a lowercase next byte before consuming a word. The second rejects the complete keyword if while still accepting identifiers beginning with those letters, such as iffy.

!. is the standard end-of-input assertion: it succeeds only when . cannot consume another byte.

Captures and result types#

{ p } captures the substring consumed by p:

{} captures the current byte position without consuming input:

{| p |} collects every capture produced by p into one table:

Adjacent captures are adjacent native Lua results. For example, the following grammar is inferred as Peg<(string, integer)> and returns two values without a tuple or table allocation:

The parentheses in Peg<(string, integer)> delimit one explicit type-pack argument; they do not construct a tuple type or a runtime tuple value. Usually the compiler infers that pack, so the annotation is only needed at an API boundary.

{| ... |} and p -> {} remain explicit table captures. Use one when the grammar semantically produces a collection, especially around capture-producing repetition; the table allocation then comes from the grammar rather than from the matcher API.

Every ordered-choice arm must produce the same capture shape. This keeps the inferred Peg<R...> result pack true regardless of which arm matches.

Groups, substitution, and back captures#

{: name: p :} groups the captures made by p under name. Inside a table capture, that group becomes a named field. Leave out name: to make an anonymous group. =name matches the exact string stored by an earlier named group:

{~ p ~} is LPeg's substitution capture. It returns the complete substring consumed by p, replacing each captured range inside it by that capture's value:

Transformations and definitions#

The suffix p -> {} collects p's captures into a table. p -> n selects capture number n; zero suppresses all captures. p -> 'format' uses LPeg's capture format, where %0 is the whole text consumed by p, %1 through %9 select captures, and %% writes a percent sign.

p -> name applies the value named by name. A function receives p's captures, or the complete matched substring when p has no explicit capture. LPeg-compatible string, number, and table transformations are accepted too. Ordinary function transformations are deferred until the whole match wins.

For a runtime grammar, pass named values in CompileOptions.definitions:

Here Integer is inferred as nupp.peg.Peg<integer> from the transformation's declared return pack. A transformation may return several values; they are spliced into the grammar's surrounding result pack. If either the grammar or definitions table is dynamic, annotate or cast the result where the application has the missing knowledge.

For a static grammar, declare a factory whose parameter is a closed record containing exactly the named callbacks:

Every named slot is required and extra slots are rejected for static factories. CompileOptions.actions remains a deprecated alias for older Nupp grammars.

The other LPeg re definition operators retain their distinct meanings:

• %name uses a supplied value as a pattern. Strings match literally, non-negative integers match that many bytes, and booleans always succeed or fail.
• p => name invokes a match-time function with the subject, current byte position, and captures. It returns a new position followed by replacement captures, or nil to fail. Because it participates in parsing, backtracking may invoke it speculatively.
• p >> name combines the previous capture with p's capture.
• p ~> name folds p's captures from left to right.

Rules and recursion#

A source beginning with name <- is a grammar made of rule definitions. The first rule is the start rule:

start <- value !.
value <- 'x' / '(' value ')'

Refer to a rule as name or <name>. Angle brackets are useful where adjoining text would make the boundary unclear.

Rules may recurse after consuming input. Direct and indirect left recursion are rejected because a top-down PEG cannot enter a rule again at the same position:

-- Invalid: value calls itself before consuming anything.
value <- value ',' item / item

Rewrite left-recursive lists as a head followed by repetition:

value <- item (',' item)*

Every reference must resolve, rule names must be unique, and expression nesting is limited to 256 levels.

Backends#

CompileOptions.backend accepts "auto" or "vm".

auto is the default. Recognition and simple captures lower to validated bytecode with constant pools and search metadata. The automatic backend translates that program into cached Lua matcher and search functions. Fixed-width, repeated-byte, and safe whole-match searches are emitted as straight-line functions; other ordinary programs get an opcode-specialized Lua dispatch loop. LuaJIT can then compile those functions when they become hot. Stateful LPeg captures retain the canonical capture graph and use its executor.

vm interprets bounded recognition bytecode without generating Lua source:

Use vm for cold or one-shot dynamic grammars, reproducible backend comparisons, or hosts that disallow loadstring. It retains bytecode-owned fixed and scan peepholes, then uses the opcode loop for ordinary programs. Stateful captures use the same graph executor in either backend. The VM never invokes runtime source generation. auto pays a one-time loadstring cost per cached program; it does not regenerate code for each match. Neither backend directly allocates native executable memory, though LuaJIT may compile hot Lua in its usual way.

Repeated byte or class plans also emit a direct byte-scanning forEachMatch loop, so traversal does not re-enter the matcher or Lua pattern engine for every match. For patterns that safely map to a Lua pattern, automatic literal replaceAll gets a fused generated path. Typed replacement callbacks retain the general search loop for plans that cannot use direct traversal.

LPeg re relationship#

The expression syntax is LPeg 1.1 re syntax: the same operators have the same parsing and capture meanings, and the test suite runs the official re module as a differential oracle. Nupp gives those open-ended Lua results a static R... pack and also exposes find, isMatch, repeated matching, and replacement directly on the compiled matcher.

A bad expression fails during comptime for a static grammar or during compile for a runtime grammar, with a line and byte-column location.

Compiles textual parsing-expression grammars into reusable matchers.

nupp.peg has one construction operation, compile. It accepts the same expression language during compilation and at runtime. A constant call inside a comptime block is validated and materialized into the program; a call with a runtime string parses and caches the grammar when the program runs. Neither form requires LPeg to be installed.

PEGs use ordered choice. first / second tries second only when first fails, and a later failure may backtrack into an earlier choice. Sequence is written by placing expressions beside one another. The usual precedence, from tightest to loosest, is primary expressions, repetition and actions, predicates, sequence, then /.

Expression quick reference#

Whitespace separates expressions and is otherwise ignored. -- starts a comment extending to the end of the line. Quoted strings contain their bytes literally; this grammar notation does not process backslash escapes. Use the other quote character when a literal needs one kind of quote.

Recognize a complete identifier#

A successful recognizer returns the byte position immediately after the match. Add !. when the pattern must consume the complete subject. Without it, a prefix match is successful.

Capture and convert a value#

Static grammars with definitions materialize as factories because runtime values cannot be captured during comptime. Runtime grammars instead receive them through CompileOptions.definitions.

type Action = function(string): any

type Actions = {[string]: Action}

type Backend = 'auto' | 'vm'

type CompileOptions = {
        --- Values named by `%name`, `-> name`, `=> name`, `>> name`, or `~> name`.
        definitions: Definitions?,

        --- Deprecated alias for `definitions` retained for existing Nupp grammars.
        actions: Actions?,

        --- Matcher implementation, `auto` when omitted.
        backend: Backend?
    }

type Definitions = {[string]: any}

interface Matcher<R...>
    match: function(self, subject: string, init: integer?): ((R...) | (nil))
    find: function(self, subject: string, init: integer?): ((integer, integer, R...) | (nil, nil))
    isMatch: function(self, subject: string, init: integer?): boolean
    forEachMatch: function(
        self,
        subject: string,
        visitor: function(first: integer, nextPosition: integer, R...),
        init: integer?
    ): integer
    replace: function(
        self,
        subject: string,
        replacement: string | function(first: integer, nextPosition: integer, R...): string,
        init: integer?
    ): string
    replaceAll: function(
        self,
        subject: string,
        replacement: string | function(first: integer, nextPosition: integer, R...): string,
        init: integer?
    ): string

    metamethod __call: function(self, subject: string, init: integer?): ((R...) | (nil))
end

match: function(self, subject: string, init: integer?): ((R...) | (nil))

find: function(self, subject: string, init: integer?):
            ((integer, integer, R...) | (nil, nil))

isMatch: function(self, subject: string, init: integer?): boolean

forEachMatch: function(
            self,
            subject: string,
            visitor: function(
                first: integer,
                nextPosition: integer,
                R...
            ),
            init: integer?
        ): integer

replace: function(
            self,
            subject: string,
            replacement: string | function(
                first: integer,
                nextPosition: integer,
                R...
            ): string,
            init: integer?
        ): string

replaceAll: function(
            self,
            subject: string,
            replacement: string | function(
                first: integer,
                nextPosition: integer,
                R...
            ): string,
            init: integer?
        ): string

record Peg<R...> is Matcher<R...>
    match: function(self, subject: string, init: integer?): ((R...) | (nil))
    find: function(self, subject: string, init: integer?): ((integer, integer, R...) | (nil, nil))
    isMatch: function(self, subject: string, init: integer?): boolean
    forEachMatch: function(
        self,
        subject: string,
        visitor: function(first: integer, nextPosition: integer, R...),
        init: integer?
    ): integer
    replace: function(
        self,
        subject: string,
        replacement: string | function(first: integer, nextPosition: integer, R...): string,
        init: integer?
    ): string
    replaceAll: function(
        self,
        subject: string,
        replacement: string | function(first: integer, nextPosition: integer, R...): string,
        init: integer?
    ): string

    metamethod __call: function(self, subject: string, init: integer?): ((R...) | (nil))
end

match: function(self, subject: string, init: integer?): ((R...) | (nil))

find: function(self, subject: string, init: integer?):
            ((integer, integer, R...) | (nil, nil))

isMatch: function(self, subject: string, init: integer?): boolean

forEachMatch: function(
            self,
            subject: string,
            visitor: function(first: integer, nextPosition: integer, R...),
            init: integer?
        ): integer

replace: function(
            self,
            subject: string,
            replacement: string | function(first: integer, nextPosition: integer, R...): string,
            init: integer?
        ): string

replaceAll: function(
            self,
            subject: string,
            replacement: string | function(first: integer, nextPosition: integer, R...): string,
            init: integer?
        ): string

local compile: function(source: string, options: CompileOptions?): Peg<...any>