1

How could one write a parser for BNF without causing and infinite loop in the following case:

Something ::= AnotherThing|Something

?

Comments
  • 2
    What are you trying to parse? The form S ::= a | S can only parse a single "a". It's pretty much equivalent to S ::= a because S ::= S does nothing (might even be removed if your parser does any optimization during construction).
  • 0
    If your parser looks at the first match only (as opposed to longest match), this rule shouldn't be an issue.
  • 0
    @RememberMe Here's a more realistic example. Matching addition expressions

    Addition ::= Number '+' (Number|Addition)
    Number ::= 'regexp:[0-9]+'

    This would allow you to match something like:

    1+2+3+4+5

    Without the Number OR (|) Expression it would only match 1+2, 3+4, which would also be separate matches.
  • 0
    @Berkmann18 okay I see. They way my parser works at the moment is that if it finds a reference to another rule it looks up that rule, which in this case would require a lookup of the same rule again, and again in infinity
  • 0
    BNF? This brings back memories.
  • 0
    @pythondev I see, are you able to get it to short-circuit by stopping at the first match?
Add Comment