1

Following up on Converting EBNF to BNF, which has a rule of:

From EBNF to BNF

For building parsers (especially bottom-up) a BNF grammar is often better, than EBNF. But it's easy to convert an EBNF Grammar to BNF:

  • Convert every repetition { E } to a fresh non-terminal X and add

    X = ε | X E

  • Convert every option [ E ] to a fresh non-terminal X and add

    X = ε | E

    (We can convert X = A [ E ] B. to X = A E B | A B.)

  • Convert every group ( E ) to a fresh non-terminal X and add

    X = E

but the question is on W3C's EBNF notation, whose definition can be found at https://www.bottlecaps.de/rr/ui, which has a different notation:

Item ::= Primary ( '?' | '*' | '+' )*

I can understand both cases, but applying them to real examples is where I'm stuck.

E.g., for,

Y ::= A E+ B

I believe that translate to:

Y = A { E } B

And the corresponding BNF notation would be the following right?

Y = A X B
X = ε | X E

Now, this is the real question that I'm not sure:

(Item ( '-' Item | Item* ))?

I believe that translate to:

Items = [Item ( '-' Item | {Item} )]

And would the corresponding BNF notation be the following?

Items
  = Item
  | Items ItemsApp
  | ε

ItemsApp
  = '-' Item
  | Item
  | ε

And moving further, for

Choice
 ::= SequenceOrDifference ( '|' SequenceOrDifference )*

SequenceOrDifference
 ::= (Item ( '-' Item | Item* ))?

Is the | Item* part really necessary? Would the above be equivalent to the following?

Choice
 ::= SequenceOrDifference ( '|' SequenceOrDifference )*

SequenceOrDifference
 ::= Item ( '-' Item )?

(given that normally there won't be any BNF definition that has an empty RHS in real world)

xpt
  • 20,363
  • 37
  • 127
  • 216
  • Be careful in your transformations from one notation to another. Note difference with `*` and `+` operators: `Y ::= A E+ B` => `Y = A (E | { E }) B`. Do not drop stating LHS of a production `Items ::= (Item ( '-' Item | Item* ))?` == `Items = [Item ( '-' Item | {Item} )]`. `SequenceOrDifference ::= (Item ( '-' Item | Item* ))?`. "Is the | Item* part really necessary?" YES! "Would the above be equivalent to the following?" NO! Watch your transformations. `SequenceOrDifference` could derive empty string. You have it after refactoring deriving `Item` minimally. – kaby76 Jan 13 '22 at 10:23
  • Thanks a lot for the answer @kaby76, as for the last point, ***if*** BNF definition does not allow empty RHS, would my transformation be equivalent _then_? – xpt Jan 13 '22 at 14:49
  • Yes, BNF--as defined by the Algol60 group--does not have empty alts or rules. So, there is no direct equivalent for `Items ::= (Item ( '-' Item | Item* ))?` because `Items` derives empty (it has '?' op at the outer grouping on RHS). So, your BNF for `Items` and `ItemsApp` are incorrect. Note, the "BNF" notation used here and the other SO question isn't "BNF" per se because meta symbols must have '<' and '>' surrounding the name, and use '::=' not '='. People need to read "Revised report on the algorithmic language ALGOL 60". – kaby76 Jan 13 '22 at 15:23

0 Answers0