LPegLabel - Parsing Expression Grammars (with Labels) for Lua

Introduction

LPegLabel is a conservative extension of the LPeg library that provides an implementation of Parsing Expression Grammars (PEGs) with labeled failures. Labels can be used to signal different kinds of errors and to specify which recovery pattern should handle a given label. Labels can also be combined with the standard patterns of LPeg.

Besides that, LPegLabel also reports the farthest failure position in case of an ordinary failure (which is represented by label fail).

This document describes the new functions available in LpegLabel and presents some examples of usage.

With labeled failures it is possible to distinguish between an ordinary failure and an error. Usually, an ordinary failure is produced when the matching of a character fails, and this failure is caught by ordered choice. An error (a non-ordinary failure), by its turn, is produced by the throw operator and may be caught by a recovery rule.

In LPegLabel, the result of an unsuccessful matching is a triple nil, lab, errpos, where lab is the label associated with the failure (a string or an integer), and errpos is the input position being matched when lab was thrown.

When lab is an ordinary failure and no error was thrown before, errpos is the farthest position where an ordinary failure occurred. In case lab is an ordinary failure and an error was thrown before, errpos is the farthest input position where an ordinary failure occurred after the last error.

Below there is a brief summary of the new functions provided by LpegLabel:

<table border="1"> <tbody><tr><td>Function</td><td>Description</td></tr> <tr><td><a href="#f-t"><code>lpeglabel.T (l)</code></a></td> <td>Throws a label <code>l</code> to signal an error</td></tr> <tr><td><a href="#re-t"><code>%{l}</code></a></td> <td>Syntax of relabel module. Equivalent to <code>lpeglabel.T(l)</code> </td></tr> <tr><td><a href="#re-pow"><code>p^l</code></a></td> <td>Syntax sugar available at relabel for <code>p / %{l}</code> </td></tr> <tr><td><a href="#re-line"><code>relabel.calcline(subject, i)</code></a></td> <td>Calculates line and column information regarding position i of the subject</code> </td></tr> </tbody></table>

Functions

<a name="f-t"></a><code>lpeglabel.T(l)</code>

Returns a pattern that throws the label l, which can be an integer or a string.

When a label is thrown, the current subject position is used to set errpos, no matter whether it is the fartherst failure position or not.

In case the PEG grammar has a rule l, after a label is thrown this rule will be used as a recovery rule, otherwise the whole matching fails.

The recovery rule will try to match the input from the subject position where l was thrown. In case the matching of the recovery rule succeeds, the regular matching is resumed. Otherwise, the result of the recovery rule is the matching result.

When we have a predicate such as -p or #p and a label l is thrown during the matching of p, this causes the failure of p, but does not propagate l, or calls its associated recovery rule.

<a name="re-t"></a><code>%{l}</code>

Syntax of relabel module. Equivalent to lpeglabel.T(l).

Label l must be a valid identifier name.

<a name="re-pow"></a><code>p^l</code>

Syntax of relabel module. The pattern p^l is equivalent to p + lpeglabel.T(l).

Label l must be a valid identifier name.

<a name="re-line"></a><code>relabel.calcline (subject, i)</code>

Returns line and column information regarding position i of the subject.

Examples

Below there a few examples of usage of LPegLabel. The code of these and of other examples is available in the examples directory.

Reporting the farthest failure

This example illustrates the new values returned by the match function in case of an unsuccessful matching. As no error is thrown in this example, when the matching fails errpos represents the farthest suffix where an ordinary failure occurred.

local m = require'lpeglabel'

function matchPrint(p, s)
  local r, lab, errpos = p:match(s)
  print("r: ", r, "lab: ", lab, "errpos: ", errpos)
end

local p = m.P"a"^0 * m.P"b" + m.P"c"
matchPrint(p, "abc")  --> r: 3    lab: nil   errpos: nil
matchPrint(p, "c")    --> r: 2    lab: nil   errpos: nil
matchPrint(p, "aac")  --> r: nil  lab: fail  errpos: 3
matchPrint(p, "xxc")  --> r: nil  lab: fail  errpos: 1

Matching a list of identifiers separated by commas

The following example defines a grammar that matches a (possibly empty) list of identifiers separated by commas. A label is thrown when there is no identifier after a comma, or when the whole input is not matched.

local m = require'lpeglabel'
local re = require'relabel'

local terror = {
  ErrId   =  "expecting an identifier",
  ErrEnd  =  "expecting EOF",
  fail    =  "undefined"
}

local id = m.R'az'^1

local g = m.P{
  'S',
  S      =  m.V'List' * (-m.P(1) + m.T'ErrEnd'),
  List   =  m.V'Id' * (m.V'Comma' * (m.V'Id' + m.T'ErrId'))^0,
  Id     =  m.V'Sp' * id,
  Comma  =  m.V'Sp' * ',',
  Sp     =  m.S' \n\t'^0,
}


function mymatch (g, s)
  local r, e, pos = g:match(s)
  if not r then
    local line, col = re.calcline(s, pos)
    local msg = "Error at line " .. line .. " (col " .. col .. "): "
    return r, msg .. terror[e] .. " before '" .. s:sub(pos) .. "'"
  end
  return r
end
  
print(mymatch(g, "one,two"))              --> 8
print(mymatch(g, "one two"))              --> nil  Error at line 1 (col 4): expecting EOF before ' two'
print(mymatch(g, "one,\n two,\nthree,4")) --> nil  Error at line 3 (col 7): expecting an identifier before '4'

In this example we could think about writing rule List as follows:

List = m.V'Id' * ((m.V'Comma' + m.T'ErrComma') * (m.V'Id' + m.T'ErrId'))^0,

but when matching <code>m.V'Comma' + m.T'ErrComma'</code> against the end of input we would get a failure whose associated label would be errComma, and this would cause the failure of the whole repetition.

Below we rewrite the previous grammar to indicate an error when there is no comma after an identifer. Before tyring to match a comma, we check if we have reached the end of input:

local m = require'lpeglabel'
local re = require'relabel'

local terror = {
  ErrId     =  "expecting an identifier",
  ErrComma  =  "expecting ','",
  fail      =  "undefined"
}

local id = m.R'az'^1

local g = m.P{
  'S',
  S      =  m.V'List',
  List   =  m.V'Id' * (#m.P(1) * m.V'Comma' * (m.V'Id' + m.T'ErrId'))^0,
  Id     =  m.V'Sp' * id,
  Comma  =  m.V'Sp' * ',' + m.T'ErrComma',
  Sp     =  m.S' \n\t'^0,
}


function mymatch (g, s)
  local r, e, pos = g:match(s)
  if not r then
    local line, col = re.calcline(s, pos)
    local msg = "Error at line " .. line .. " (col " .. col .. "): "
    return r, msg .. terror[e] .. " before '" .. s:sub(pos) .. "'"
  end
  return r
end
  
print(mymatch(g, "one,two"))               --> 8
print(mymatch(g, "one two"))               --> nil  Error at line 1 (col 4): expecting ',' before ' two'
print(mymatch(g, "one,\n two,\nthree,4"))  --> nil  Error at line 3 (col 7): expecting an identifier before '4'
print(mymatch(g, " 1,2"))                  --> nil  Error at line 1 (col 2): undefined before '1,2'

Error Recovery

We can specify a recovery rule that should be matched when a label is thrown. After matching the recovery rule, and possibly recording the error, the parser will resume the regular matching. The recovery rule must have the same name (or number) of the label that was thrown.

For example, in the example below we expect to match rule A, but when a failure occur the label Err is thrown and then we will try to match rule Err:

local m = require'lpeglabel'

local recp = m.P"oast"

local g = m.P{
  'S',
  S    =  m.V'A' * '.',
  A    =  m.P't' * (m.P'est' + m.T'Err'),
  Err  =  m.P'oast'
}

print(g:match("test."))   --> 6
print(g:match("toast."))  --> 7
print(g:match("oast."))   --> nil  fail  oast.
print(g:match("toward.")) --> nil  fail  ward.

When trying to match subject 'toast.', in rule A the first 't' is matched, then the matching of m.P"est" fails and label Err is thrown, with the associated inpux suffix 'oast.'. The recovery rule Err successfully matches 'oast', so the regular matching continues, and pattern '.' matches the rest of the input.

When matching subject 'oast.', pattern m.P"t" fails, and the result of the matching is nil, fail, 1.

When matching 'toward.', label Err is thrown after matching 't', with the associated input suffix 'oward.'. As the matching of the recovery pattern fails, the result is nil, fail, 3.

Usually, the recovery pattern is an expression that does not fail. In the previous example, we could have used (m.P(1) - m.P".")^0 as the recovery pattern.

Below we rewrite the grammar that describes a list of identifiers to use a recovery strategy, with the help of some auxiliary functions. Function record, plus function recorderror, will help us to save the input position where a label was thrown, while function sync will give us a synchronization pattern, that consumes the input while it is not possible to match a given pattern p.

When the matching of an identifier fails, a defaul value ('NONE') is provided.

local m = require'lpeglabel'
local re = require'relabel'

local terror = {
  ErrId     =  "expecting an identifier",
  ErrComma  =  "expecting ','",
  ErrList   =  "expecting a list of identifiers",
  fail      =  "undefined"
}

local subject, errors

function recorderror(pos, lab)
  local line,

Lpeglabel

Install / Use

README