Is it possible to parse my grammar with multi-line productions without backtracking?

Question

I'm playing around with creating a parser in PHP for my own flavor of BNF, to match strings against grammar in this BNF variant. It's still a work in progress and subject to change (I may even end up switching to support ABNF or EBNF, in stead of my own variant), but it's coming along quite nicely.

Now, forgive me if I mix up nomenclature here, but I believe what I have created so far could be called a LL(1) parser (or perhaps it would be better to call it a lexer), in that it evaluates the source one character at a time, without backtracking.

In my BNF variant a production rule is terminated by a new line. But one thing, amongst other things, that a grammar defined in my BNF variant does not allow yet, is to have multi-line production rules. It surely isn't a necessity, but it would be a nice-to-have, for improved readability of the grammar rules.

However, I'm struggling to find a way to parse such a rule, without backtracking. I guess I could decide to have, for instance, a semicolon be the terminating character for a production rule. But just out of curiosity: should it, in principle, be possible to disambiguate newlines as either being part of a rule, or the end of a rule, without backtracking? Or is that simply not possible?

For your consideration, here is a small (non-exhaustive) example grammar in my BNF variant:

<DIGIT>      ::= "0"-"9"
<ALPHAHI>    ::= "A"-"Z"
<ALPHALO>    ::= "a"-"z"
<ALPHA>      ::= <ALPHAHI> |
                 <ALPHALO>
<ALPHANUM>   ::= <ALPHA> |
                 <DIGIT>

Answer 1

Strictly speaking, the only way to prevent any backtracking whatsoever while supporting multi-line statements is to either have an explicit "the upcoming newline is not the end of a rule" character, or have an explicit "this is the end of a rule" character other than a newline. As you mentioned, you can end rules with semicolons. But you could also say that any line ending with the vertical bar | means "this rule continues to the next line", and for BNF that might not be entirely unreasonable. Makefiles use the backslash character in exactly this way.

A much simpler solution for your immediate problem would be to assume that every rule must start with a < on a new line, and vice versa, so that every line starting with something else must be a continuation of a rule started earlier. This arguably still involves one or two characters of backtracking, so whether that's good enough depends on why you want to avoid backtracking in the first place. But that rule seems more intuitive and flexible to me than the "vertical bars end lines" rule.

Of course, the most formally correct way to parse this would be to assume only that all rules must start with a single non-terminal and ::=, but that would definitely involve backtracking at every ::=.