TransWikia.com

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

Computer Science Asked by phamsodiep on October 21, 2021

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,

One Answer

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.

Answered by phamsodiep on October 21, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP