Convert the following EBNF rule into ordinary BNF Yo u will

Convert the following EBNF rule into ordinary BNF. (Yo

u will need more than one

rule, and you will need to introduce one or more new nonterminals.) {, }, [, and ] are

metasymbols unless enclosed in quotation marks.

<

set

>

[

<

qualident

>

]

“

{

”

[

<

element

>

{

,

<

element

>

}

]

“

}

Solution

BNF:When describing languages, Backus-Naur form (BNF) is a formal notation for encoding grammars intended for human consumption.Many programming languages, protocols or formats have a BNF description in their specification.

It is used to formally define the grammar of a language, so that there is no disagreement or ambiguity as to what is allowed and what is not. In fact, BNF is so unambiguous that there is a lot of mathematical theory around these kinds of grammars, and one can actually mechanically construct a parser for a language given a BNF grammar for it.The language defined by the BNF grammar is just the set of all strings you can produce by following these rules.

The rules are called production rules, and given as:

symbol := alternative1 | alternative2 ...

A production rule simply states that the symbol on the left-hand side of the := must be replaced by one of the alternatives on the right hand side. The alternatives are separated by |s. (One variation on this is to use ::= instead of :=, but the meaning is the same.) Alternatives usually consist of both symbols and something called terminals. Terminals are simply pieces of the final string that are not symbols. They are called terminals because there are no production rules for them.Another variation on BNF grammars is to enclose terminals in quotes to distinguish them from symbols.

EBNF:EBNF is a few simple extensions to BNF which make expressing grammars more convenient; adds “syntactic sugar\".Thus it is more concise than BNF.EBNF is no more “powerful” than BNF; that is, anything that can be expressed in EBNF can also be expressed in BNF.

Conversions od EBNF 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.

X = E | E\'. becomes X = E. X = E\'.

\"set\" -> [\"qualident\"] \"{\" [\"element\"]{\";\" \"element \"}

Some productions must be added to convert this to BNF:

{expr} can be replaced by inserting a production as X:=empty |

[expr] can be replaced by inserting X:=empty | expr

Any expression ( expr ) can be replaced by adding a new production X := expr