0

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>
2

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 ::=.

  • The reason I want to avoid backtracking is to avoid an increasing time complexity (although, admittedly, my parser may very well be inefficient in other areas (using PHP, anyone?! har har! ;-) )). I'm just trying to keep it as efficient as I can within my current knowledge-scope and the language I work with — especially for more complex grammars. Anyway, everything you wrote is reassuring and I like the "line ending with a vertical bar" idea; I had not thought about that. I'm going to ponder on such an option. So, thank you! – Decent Dabbler Feb 20 '16 at 20:55
  • I think even if you backtracked at every ::= you'd still only do O(n) backtracking in total, and parsing already has to be O(n) for obvious reasons. But then that's just theoretical bounds since I don't know how you implemented your parser...maybe this is something for a follow-up question. – Ixrec Feb 20 '16 at 21:11
  • Forgive me my possible ignorance and misunderstanding of time complexity, but wouldn't backtracking mean added complexity because I possibly have to evaluate a character multiple times? Thus leading to something like O(n+b) (I'm sure that's not the correct notation, but I hope you see what I'm trying to get at), where b is the total amount of backtracks? – Decent Dabbler Feb 20 '16 at 22:25
  • @DecentDabbler Yes but O(n+b) is still O(n). It's not the kind of difference that matters unless this happens to be a hotspot for the program. The whole point of big-O notation is that we're usually more concerned with O(n) vs O(n^2) than we are with n vs n+2. – Ixrec Feb 20 '16 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.