How to design a formal grammar to convert EBNF description to a list of CFG production rules

Question

I would like to write a grammar to convert EBNF description to a list of CFG production rules, instead of an algorithm.

Can CFG production rules is generated from an EBNF description by a rewrite system rewrite EBNF description to halt state that final string is composed by CFG production rules and separate character for that list (for example character '/')?

For example: From intuition view, I could convert as below:

EBNF Description:

letter = "A" | "B" | "C" ;

digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;

identifier = letter , { letter | digit | "_" } ;

Generated production rules:

letter ⟶ "A"

letter ⟶ "B"

letter ⟶ "C"

digit ⟶ "0"

digit ⟶ "1"

digit ⟶ "2"

digit ⟶ "3"

digit ⟶ "4"

digit ⟶ "5"

digit ⟶ "6"

digit ⟶ "7"

digit ⟶ "8"

digit ⟶ "9"

identifier ⟶ letter

identifier ⟶ letter noname_nonterminal

noname_nonterminal ⟶ letter noname_nonterminal

noname_nonterminal ⟶ digit noname_nonterminal

noname_nonterminal ⟶ "_" noname_nonterminal

noname_nonterminal ⟶ letter

noname_nonterminal ⟶ digit

noname_nonterminal ⟶ "_"

Thank you for your reading,

Answer 1

I have a solution as below:

• Given G0 = (N0, Σ0, P0, S0) is grammar of object language generated by EBNF descriptions. Where: N0 and P0 is unknown and needed to be generated by another language.
• Given G1 = (N1, Σ1, P1, S1) is grammar of language generating EBNF descriptions.

G = (N, Σ, P, S) is EBNF description to production rules conversation grammar which is defined as below:

• N = {'(', ')', '∣', ',', '[', ']', '{', '}', '='}
• Σ = N0 ⋃ Σ0 ⋃ {'→', '/'}

Production rules:

A = α, (γ), β ⟶ A = α, YA, β / YA = γ

Where:

• A, YA ∈ N0
• α ∈ N1 ⋃ Σ1 ∖ {'('}
• β ∈ N1 ⋃ Σ1 ∖ {')'}
• γ ∈ N1 ⋃ Σ1 ∖ {'ε'}

A = α ∣ β ⟶ A = α / A = β

Where:

• A ∈ N0
• α ∈ N1 ⋃ Σ1 ∖ {'(', ')', '[', ']', '{', '}'}
• β ∈ N1 ⋃ Σ1 ∖ {'(', ')', '[', ']', '{', '}'}

A = α[γ]β ⟶ A = α, (γ), β / A = α, β

Where:

• A ∈ N0
• α ∈ N1 ⋃ Σ1 ∖ {'['}
• β ∈ N1 ⋃ Σ1 ∖ {']'}
• γ ∈ N1 ⋃ Σ1 ∖ {'ε'}

A = α{γ}β ⟶ A = α , YA, β / YA = γYA / YA = ε

Where:

• A, YA ∈ N0
• α ∈ N1 ⋃ Σ1 ∖ {'{'}
• β ∈ N1 ⋃ Σ1 ∖ {'}'}
• γ ∈ N1 ⋃ Σ1 ∖ {'ε'}

A = B,C ⟶ A = BC

Where:

• A, B, C ∈ N0

A = B ⟶ A → B

Where:

• A, B ∈ N0

Start rule:

S ⟶ a

• Where a ∈ Σ1

This grammar will re-write EBNF description to a terminal string like: A → B / B → C / B → D which means that the generated production rules are the set {A → B, B → C, B → D}. The token '/' is list seperator.