nupp.peg

nupp.peg compiles textual parsing-expression grammars into reusable typed matchers. The same grammar language works inside comptime and at runtime.

const Identifier = comptime do
    return nupp.peg.compile("[a-zA-Z_] [a-zA-Z_0-9]* !.")
end

assert(Identifier("item_2") == 7)
assert(Identifier("2_items") == nil)

A parsing-expression grammar describes a deterministic top-down parse. Its choice operator is ordered, so p / q tries q only if p fails, where a regular expression alternation may pick whichever arm makes the complete expression work.

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

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, which derives nupp.peg.Peg<R...> from the validated capture shape:

const Word = comptime do
    return nupp.peg.compile("{ [a-z]+ } !.")
end

Recognizers, substring and position captures, and collections therefore need no result annotation. 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...>. It still compiles at run time, though parsed plans are cached by grammar source and backend, so compiling the same grammar again avoids parsing, lowering and code generation. A genuinely dynamic string answers Peg<...any>, because its capture shape is not yet known:

local function loadMatcher(configuration: string): nupp.peg.Peg<...any>
    return nupp.peg.compile(configuration)
end

Neither form requires a separately installed LPeg: the resolved native effect asks the build for a host that supplies LPeg 1.1.

Prefer comptime for source-owned constant grammars. Runtime compilation is for configuration, plugins, user-selected formats, and other genuinely dynamic input. A bad expression fails during comptime for a static grammar and during compile for a runtime one, with a line and byte-column location either way.

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

local function match<R...>(matcher: nupp.peg.Matcher<R...>, subject: string): ((R...) | (nil))
    return matcher:match(subject)
end

local Word = nupp.peg.compile("{ [a-z]+ }")
local word: string? = match(Word, "hello")

Matching and positions#

A matcher can be called directly or through match, which mean the same thing:

local Word = nupp.peg.compile("{ [a-z]+ }")
local result = Word("hello")
local same = Word:match("hello")

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. Every operation on this page that takes an init normalizes it that way:

local Word = nupp.peg.compile("{ [a-z]+ }")
assert(Word("one two", 5) == "two")

A recognizer, meaning a grammar with no captures, answers the byte position immediately after its match rather than a boolean. Failure answers nil:

local Prefix = nupp.peg.compile("'get'")
assert(Prefix("getter") == 4)
assert(Prefix("setter") == nil)

Searching with find#

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

local Word = nupp.peg.compile("{ [a-z]+ }")
local first, nextPosition, value = Word:find("123 hello")
assert(first == 5 and nextPosition == 10 and value == "hello")

For Peg<R...>, success has the pack (integer, integer, R...) and failure has (nil, nil). The byte range is half-open, [first, nextPosition), so an empty match has equal positions. Test first for success rather than the value, because a grammar action may successfully answer nil or false. A recognizer's third result is the same next-byte position match would have answered.

Testing with isMatch#

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

local Digits = nupp.peg.compile("[0-9]+")
assert(Digits:isMatch("room 42"))
assert(not Digits:isMatch("room"))
assert(not Digits:isMatch("42 rooms", 3))

The position after the last byte is included in the search, so an empty or end assertion can 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 call answers the number of visits:

local Word = nupp.peg.compile("{ [a-z]+ }")
local words: {string} = {}
local count = Word:forEachMatch("one, two, three", function(first: integer, nextPosition: integer, value: string)
    words[#words + 1] = value
end)

assert(count == 3)
assert(words[2] == "two")

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, which is why '' visits positions 1, 2 and 3 in a two-byte subject.

Text before init is not visited. The visitor's return value is ignored, so raising is the way to abort a traversal.

Replacement#

replace replaces the first match and replaceAll replaces every non-overlapping match. A string replacement is inserted literally, with no interpretation of $, %, or capture references:

local Digits = nupp.peg.compile("[0-9]+")
assert(Digits:replace("room 42, floor 3", "#") == "room #, floor 3")
assert(Digits:replaceAll("room 42, floor 3", "#") == "room #, floor #")

Use a typed callback when the replacement text depends on the match. It receives the raw positions followed by every grammar result and must answer a string:

local Word = nupp.peg.compile("{ [a-z]+ }")
local output = Word:replaceAll("one, two", function(first: integer, nextPosition: integer, value: string): string
    return "[" .. tostring(first) .. ":" .. tostring(nextPosition) .. " " .. value:upper() .. "]"
end)

assert(output == "[1:4 ONE], [6:9 TWO]")

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 answered, and init leaves the prefix before it unchanged.

Empty matches insert without removing a byte, and replaceAll preserves that byte while advancing under the same progress rule forEachMatch uses. An empty grammar therefore turns "ab" into "-a-b-" when replacing with "-".

Expression syntax#

One row is missing above, because a cell cannot hold its delimiters: {| p |} collects every capture produced by p into one array.

Whitespace between expressions is ignored, and 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 notation does not process backslash escapes, so 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 and fails at the end of the subject.

Byte classes#

Square brackets match one byte from a set, and 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 where token boundaries stay clear, and whitespace usually makes a grammar 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 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, so 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. Append it to require a complete match, since without it a prefix match succeeds:

local Whole = nupp.peg.compile("'get' !.")
assert(Whole("get") == 4)
assert(Whole("getter") == nil)

Captures and result types#

{ p } captures the substring consumed by p, {} captures the current byte position without consuming input, and {| p |} collects every capture produced by p into one table:

const Name = comptime do
    return nupp.peg.compile("{ [a-z]+ } !.")
end

const Start = comptime do
    return nupp.peg.compile("{} [a-z]+ !.")
end

const Fields = comptime do
    return nupp.peg.compile("{| { [a-z]+ } (',' { [a-z]+ })* |} !.")
end

Adjacent captures are adjacent native Lua results. The following grammar is inferred as Peg<(string, integer)> and answers two values with no tuple or table allocation:

local Field = nupp.peg.compile("{ [a-z]+ } ':' {}")
local name, nextPosition = Field("size:")

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

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

Every ordered-choice arm must produce the same capture shape, which is what keeps the inferred Peg<R...> result pack true whichever 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:

local Pair = nupp.peg.compile("{| {: key: { [a-z]+ } :} '=' {: value: { [0-9]+ } :} |} !.")
local fields = assert(Pair("size=42"))
assert(fields.key == "size" and fields.value == "42")

local Repeated = nupp.peg.compile("{: word: { [a-z]+ } :} ':' =word !.")
assert(Repeated("same:same") == "same")
assert(Repeated("same:other") == nil)

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

local Normalize = nupp.peg.compile("{~ ({ [0-9]+ } -> '[%0]' / .)* ~} !.")
assert(Normalize("a12b") == "a[12]b")

Transformations and definitions#

The suffix p -> {} collects p's captures into a table. p -> n selects capture number n, and 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.

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

local Integer = nupp.peg.compile("[0-9]+ -> integer !.", {definitions = {integer = function(text: string): integer
    return assert(tonumber(text)) as integer
end,},})
assert(Integer("42") == 42)

Here Integer is inferred as nupp.peg.Peg<integer> from the transformation's declared return pack. A transformation may answer several values, and they are spliced into the grammar's surrounding result pack. If either the grammar or the 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:

local record Definitions
    integer: function(string): integer
end

const IntegerFactory: function(Definitions): nupp.peg.Peg<integer> = comptime do
    return nupp.peg.compile("[0-9]+ -> integer !.")
end

local Integer = IntegerFactory(new Definitions(integer = function(text: string): integer
    return assert(tonumber(text)) as integer
end))

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 answers 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, and 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 a left-recursive list 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 "lpeg". auto is the default: every static grammar becomes a validated canonical PEG graph, Nupp emits straight-line Lua for the few shapes it recognizes, namely fixed-width matches, repeated bytes and packed whole-input scans, and every other graph lowers directly to native LPeg patterns.

local Fast = nupp.peg.compile("[a-z]+ !.")
local General = nupp.peg.compile("[a-z]+ !.", {backend = "lpeg"})

lpeg disables Nupp's straight-line specializations and always lowers the graph to native LPeg, which is what makes a backend comparison possible. There is no Nupp PEG bytecode and no general-purpose interpreter.

Runtime textual grammars are compiled by LPeg's re module and cached by source. They do not invoke loadstring, and auto invokes it only when a static graph selects a Nupp specialization. A repeated byte or class plan also emits a direct byte-scanning forEachMatch loop, so a traversal does not re-enter LPeg for every match; a typed replacement callback keeps the general search loop.

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. Direct require("lpeg") answers the native LPeg 1.1 module, and require("re") answers the bundled official Lua frontend over it. Nupp's declaration and operator checking track capture packs through ordinary LPeg composition, but the runtime object stays LPeg's pattern userdata.

type Action = function(string): any

type Actions = {[string]: Action}

type Backend = 'auto' | 'lpeg'

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

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

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))

local Word = nupp.peg.compile("{ [a-z]+ }")
assert(Word:match("one two", 5) == "two")
assert(Word("123") == nil)

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

local Word = nupp.peg.compile("{ [a-z]+ }")
local first, nextPosition, value = Word:find("123 hello")
assert(first == 5 and nextPosition == 10 and value == "hello")

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

local Digits = nupp.peg.compile("[0-9]+")
assert(Digits:isMatch("room 42"))
assert(not Digits:isMatch("room", 2))

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

local Word = nupp.peg.compile("{ [a-z]+ }")
local seen: {string} = {}
local count = Word:forEachMatch("one, two", function(_, _, word: string)
    seen[#seen + 1] = word
end)
assert(count == 2 and seen[2] == "two")

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

local Digits = nupp.peg.compile("[0-9]+")
assert(Digits:replace("room 42, floor 3", "#") ==
    "room #, floor 3")

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

local Digits = nupp.peg.compile("[0-9]+")
assert(Digits:replaceAll("room 42, floor 3", "#") ==
    "room #, floor #")

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

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

local Words = nupp.peg.compile(
    "{| { [a-z]+ } (',' { [a-z]+ })* |} !."
)
local values = assert(Words("red,green,blue")) as {string}
assert(values[2] == "green")

local General = nupp.peg.compile("[0-9]+ !.", {backend = "lpeg"})
assert(General("123") ~= nil)