How should I modify the grammar to allow optional expression without backtracking

Question

Here's a simple grammar:

filling = fill? align
fill = .
align = [<>=^]

and it should match the following:

<
0<
<<

However, PEG.js doesn't allow backtracking, and fill simply consumed the < character:

<    (does not work)
0<   (works)
<<   (works)

How should I modify the grammar to make it work?

Answer 1

PEG.js doesn't allow backtracking

That is not entirely true. The following code works as you want:

filling = fill align / align

The reason that this works and the version with ? does not is that backtracking is only performed over the alternatives within a single rule. That is, if one alternative fails, the parser backtracks and tries the next alternative until an alternative matches or all alternatives are exhausted. What the parser doesn't do though is to try other alternatives in a subrule that already succeeded. So in fill? align, if fill? succeeds by matching <, it won't try the alternative of it matching the empty string when align doesn't match afterwards. But in fail align / align, if fail align fails because align fails, it does try the next alternative, which then succeeds.

This behavior means that you can often get backtracking by inlining subrules or, as in this case, "inlining" operators like ?.