Backtracking support

[amitzur]

Hi @dmaevsky 👋 thanks for sharing this!

I noticed that there is not backtracking happening in rd-parse. I was wondering if this is by design, and if so, do you have any thoughts or pointers on how to make it work with backtracking?

I'll explain what I mean. Consider the following use case:

I want my grammar to accept the string on the table. But because of the order I provide to Any, then a seemingly valid grammar fails on this string. I need to switch the order of on and on the in order for it to work.

import test from 'node:test'
import assert from 'node:assert/strict'
import Parser, {Any, All, Node} from 'rd-parse'

test('backtracking', () => {
  const grammar = Node(All(Any(/^(on)/, /^(on the)/), /^table/), stack => stack.join(''))
  // const grammar = Node(All(Any(/^(on the)/, /^(on)/), /^( table)/), stack => stack.join('')) // <----- uncomment this to make it work
  const parse = Parser(grammar)
  assert.equal(parse('on the table'), 'on the table')
})

[dmaevsky]

This is unfortunately a "feature" of recursive descent parsing in general. However, in my experience, even with fairly complicated grammars like this one you can always work around this limitation by (as you correctly noticed) putting the greedier rules before the less greedy ones in Any clauses.

[amitzur]

@dmaevsky Thanks for the response! I will go in the way you proposed