Recursive regular expression in Perl 6?

Question

I've been trying to figure out how to do a recursive regular expression in Perl 6. For a toy example, a balanced parentheses matcher, which would match ((())()) inside (((((())()).

PCRE example: /\((?R)?\)/
Onigmo example: (?<paren>\(\g<paren>*\))

I thought this would do it:

my regex paren {
  '(' ~ ')' <paren>*
}

or the simpler

my regex paren {
  '(' <paren>* ')'
}

but that fails with

No such method 'paren' for invocant of type 'Match'
in regex paren at ...

See also [Parsing a possibly nested braced item using a grammar](https://stackoverflow.com/q/47124405/2173773) — Håkon Hægland, Mar 01 '19 at 09:52
@HåkonHægland: Thanks, especially that [link](https://examples.perl6.org/categories/best-of-rosettacode/balanced-brackets.html) was a nice find. However, I was explicitly trying not to look at grammars since I want to find all matching spans, not parse a string from start, and I don't think grammars support that. That said, I am a noob at P6, so I am sure I'm missing something. — Amadan, Mar 01 '19 at 09:58
@HåkonHægland I mean I guess I can make a grammar that has `nonparen` as stuff I don't want, and an action class that will collect the `paren` matches... but that gets complicated fast... It's just very hard to believe P6 regular expressions dropped support for something Perl basically pioneered. — Amadan, Mar 01 '19 at 10:02

score 15 · Accepted Answer · edited Jan 17 '20 at 10:10

You need to make explicit that you're calling a my-scoped regex:

my regex paren {
    '(' ~ ')' <&paren>*
}

Notice the & that has been added. With that:

say "(()())" ~~ /^<&paren>$/    # ｢(()())｣
say "(()()" ~~ /^<&paren>$/     # Nil

While it's true that you can sometimes get away without explicitly writing the &, and indeed could when using it:

say "(()())" ~~ /^<paren>$/    # ｢(()())｣
say "(()()" ~~ /^<paren>$/     # Nil

This only works because the compiler spots there is a regex defined in the lexical scope with the name paren so compiles the <paren> syntax into that. With the recursive case, the declaration isn't installed until after the regex is parsed, so one needs to be explicit.

Perfect, that was the missing piece. Thank you! – Amadan Mar 01 '19 at 11:16 — Amadan, Mar 01 '19 at 11:16

score 2 · Answer 2 · answered Sep 11 '19 at 06:45

You can use the ~~ in the meta-syntax to make a recursive callback into the current pattern or just a part of it. For example, you can match balanced parenthesis with the simple regex:

say "(()())" ~~ /'(' <~~>* ')'/;    # ｢(()())｣
say "(()()"  ~~ /'(' <~~>* ')'/;    # ｢()｣

Try it online!

Unfortunately, matching via a captured subrule (like ~~0) is not yet implemented.

Recursive regular expression in Perl 6?

2 Answers2

Linked