Regex kleene star question

gmarik · February 24, 2021, 6:49am

reading again the book since it’s complete and stumbled on

A regular expression a*a will match one or more letters a. However, a*a in PEG will never match anything…

On page 44.

TIL! I assumed regex matched like PEG but turns out it’s not the case.
Is it due to backtracking in regexp? Where is this behaviour documented?

Thanks!

keleshev · February 24, 2021, 4:31pm

PEG backtracks only at the points where the alternative (/) operator is used. You can see this behaviour from the code here:

github.com

keleshev/compiling-to-assembly-from-scratch/blob/8a6424fd640e8c13eac8e31b82cdb952f98e1f83/part-1/compiler.ts#L61-L69


or(parser: Parser<T>): Parser<T> {
  return new Parser((source) => {
    let result = this.parse(source);
    if (result)
      return result;
    else
      return parser.parse(source);
  });
}

If this.parse(source) fails then the other parser.parse(source) is retried with the same source.

Regexes, on the other hand, backtrack in general when a match is not found.
The following regex example might be useful: https://riptutorial.com/regex/example/3179/what-causes-backtracking.

I’ve never implemented a regex engine, so I have only an intuitive understanding of it.

gmarik · February 24, 2021, 5:42pm

Thanks!

Yeah, PEG backtracking wasn’t surprising for me but regexp’s was; but only the ones with O(n) guarantees like RE2(tested on play.golang.org). So i was wondering how is that implemented since it’s working allegedly without backtracking…

Not expecting the answer from you since it’s off topic, just thinking out loud