| > Are Perl 6 "regexes" as powerful as a context-free grammar? TL;DR If you can code it, you can code it using Perl 6 grammars. Perl 6 is designed as a collection of "slangs" (short for sub-languages) that recursively embed each other. (There are about a half dozen slangs in standard Perl 6 but you can add more.) So the full power of the "main" Perl 6 slang is available within the regex slang (and vice-versa). During execution each slang automatically tracks the interesting state of the other slangs. So, while the compiler is free to analyze a given rule and generate a suitably optimized DFA or NFA, they are, in general, capable of turing complete power. > I guess they use the same kind of backtracking algorithm The main answer is No. There are four types of "rule". Only one of these, using the `regex` declarator, backtracks in the usual regex way. Most extant grammars contain nothing but `rule`s, `token`s, and occasionally `method`s. The fact that the latter are just ordinary methods hints at what's going on; the "regex slang" is really just a built in recursive ascent/descent parser generator with a convenient DSL (slang) for writing grammars. |