Creating a recursive LPeg pattern

Question

In a normal PEG (parsing expression grammar) this is a valid grammar:

values <- number (comma values)*
number <- [0-9]+
comma  <- ','

However, if I try to write this using LPeg the recursive nature of that rule fails:

local lpeg   = require'lpeg'

local comma  = lpeg.P(',')
local number = lpeg.R('09')^1
local values = number * (comma * values)^-1
--> bad argument #2 to '?' (lpeg-pattern expected, got nil)

Although in this simple example I could rewrite the rule to not use recursion, I have some existing grammars that I'd prefer not to rewrite.

How can I write a self-referencing rule in LPeg?

score 5 · Accepted Answer · answered Oct 01 '14 at 20:24

Use a grammar.

With the use of Lua variables, it is possible to define patterns incrementally, with each new pattern using previously defined ones. However, this technique does not allow the definition of recursive patterns. For recursive patterns, we need real grammars.

LPeg represents grammars with tables, where each entry is a rule.

The call lpeg.V(v) creates a pattern that represents the nonterminal (or variable) with index v in a grammar. Because the grammar still does not exist when this function is evaluated, the result is an open reference to the respective rule.

A table is fixed when it is converted to a pattern (either by calling lpeg.P or by using it wherein a pattern is expected). Then every open reference created by lpeg.V(v) is corrected to refer to the rule indexed by v in the table.

When a table is fixed, the result is a pattern that matches its initial rule. The entry with index 1 in the table defines its initial rule. If that entry is a string, it is assumed to be the name of the initial rule. Otherwise, LPeg assumes that the entry 1 itself is the initial rule.

As an example, the following grammar matches strings of a's and b's that have the same number of a's and b's:
equalcount = lpeg.P{
  "S";   -- initial rule name
  S = "a" * lpeg.V"B" + "b" * lpeg.V"A" + "",
  A = "a" * lpeg.V"S" + "b" * lpeg.V"A" * lpeg.V"A",
  B = "b" * lpeg.V"S" + "a" * lpeg.V"B" * lpeg.V"B",
} * -1
It is equivalent to the following grammar in standard PEG notation:
  S <- 'a' B / 'b' A / ''
  A <- 'a' S / 'b' A A
  B <- 'b' S / 'a' B B

Definitely the right answer; but can I really accept an answer that is a copy/paste from the manual, without even an attempt at formatting? :p — Phrogz, Oct 01 '14 at 20:25
@Phrogz Should you really have asked a question that's directly addressed by that manual? =) And that is "formatted", try pasting that quote from the manual directly into an answer and then just block quoting it all you don't get the above. =) — Etan Reisner, Oct 01 '14 at 20:41
I shouldn't have, but I didn't recognize this part of the manual as applying at first. My `:p` should have been a `:)`. You did well, thank you. — Phrogz, Oct 01 '14 at 21:41

score 0 · Answer 2 · answered Jan 03 '16 at 20:03

I know this is a late answer but here is an idea how to back-reference a rule

local comma  = lpeg.P(',')
local number = lpeg.R('09')^1
local values = lpeg.P{ lpeg.C(number) * (comma * lpeg.V(1))^-1 }

local t = { values:match('1,10,20,301') }

Basically a primitive grammar is passed to lpeg.P (grammar is just a glorified table) that references the first rule by number instead of name i.e. lpeg.V(1).

The sample just adds a simple lpeg.C capture on number terminal and collects all these results in local table t for further usage. (Notice that no lpeg.Ct is used which is not a big deal but still... part of the sample I guess.)

Creating a recursive LPeg pattern

2 Answers2