Convert the following EBNF rule into ordinary BNF You will n

Convert the following EBNF rule into ordinary BNF. (You 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

<set> -> [ <qualident> ] \"{\" [ <element> { , <element> } ] \"}\"

Let S represetnt <set>, So, the earlier expression can be re-written as

S -> [<qualident>] \"{\" [ <element> { , <element> } ] \"}\"

Please note that in EBNF, [ ] represents zero or one occurence and { } represents zero or more occurence

Step 1 : Seperate out all the terminals, and replace them with non-terminal variables in the expression

S -> [Q] A [ E {C E}] A
A-> {
B -> }
C -> ,
Q -> <qualident>
E -> <element>

Step 2 : Convert all the option of type [Y] to a new non-terminal variable X and add X -> | Y

S -> T A U A
T -> | Q
U -> | E {CE}
A-> {
B -> }
C -> ,
Q -> <qualident>
E -> <element>

Step 3 : Convert all repetitions of type {Y} to a non terminal variable, say, X and add X -> | Y

S -> TAUA
T -> | Q
U -> | EV
V -> | VCE
A-> {
B -> }
C -> ,
Q -> <qualident>
E -> <element>