0
$\begingroup$

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,

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.