LPeg

This article is not detailed enough and needs to be expanded. Please help us by adding some more information.

LPeg

Designed by	wikipedia:Roberto Ierusalimschy
Appeared in	2007
Computational class	linear bounded automata
Reference implementation	https://www.inf.puc-rio.br/~roberto/lpeg/
Influenced by	Lua

LPeg is a parsing machine for evaluating PEGs. It was originally proposed along with its reference implementation which provides an algebra of parser combinators in Lua; each parsing expression is compiled to a program for the parsing machine.

Examples

Consider the task of recognizing sequences of bits. A naïve compilation of a regular expression like (0|1)* might read like:

L1: Choice L2
    Choice L3
    Char '0'
    Commit L4
L3: Char '1'
L4: Commit L1
L2:

This can be optimized at compile time before emitting the choice operator:

L1: Choice L2
    Charset "01"
    Commit L1
L2:

The reference implementation of LPeg contains an optimized opcode for this idiom:

Span "01"

Complexity class

The reference implementation of LPeg does not perform packrat optimizations at runtime and thus may spend quadratic time in backtracking.