2 years ago

#43841

test-img

xpt

Converting W3C's EBNF to BNF

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)

bnf

ebnf

recursive-descent

0 Answers

Your Answer

Accepted video resources