Geek asks and answers

What is the difference between EBNF and CFG

I understand that EBNF can be used to express the grammar of contextual freedom, but is there a difference between the two?

I ask, because there are questions that require converting EBNF to CFG, but, based on my current understanding, they look the same. Therefore, what is the purpose of this transformation?

+4
source share
3 answers

EBNF can be used to write context-free grammar.

The Latin alphabet can be used to write English.

Pascal can be used to express an algorithm.

"- " - , EBNF . - - . , .

+3

: EBNF CFG, EBNF .

- - :

  • V

  • & Sigma; V

    v → ω

V - V, ω - (V ⋃ Σ)* ( , , .

  • S, V.

(. . , V A, V Σ.)

CFG 1959 , Algol; Backus-Naur Form, , , . BNF CFG , |:

     v → ω1 | ω2
    ⇒
      v → ω1
      v → ω2

, , Kleene Star, . BNF , Niklaus Wirth. , BNF , RFC (- IETF), ISO. "" Extended BNF, ISO/IEC 14977 BNF, RFC-5234.

EBNF CFG, - - , . , EBNF, ABNF , CFG, , . (. Ebnf - LL (1)?)

+2

. ABNF RBNF, EBNF , , - .

:

  1. L1 = {a ^ n b ^ n a ^ m | n, m ≥ 0} :

    L1 :: = X, A

    X :: = "a", X, "b" | Emptystring

    A :: = A, "a" | Emptystring

  2. L2 = {a ^ n b ^ m a ^ m | n, m ≥ 0} :

    L2 :: = A, X

  3. L 1 ∩ L 2 = {a ^ nb ^ na ^ n | n ≥ 0} is not a context-free pumping lemma, because for a given p ≥ 1 we can choose n> p such that s = a ^ nb ^ na ^ n is in our language, and we cannot choose any substring q from s such that q has length p, s = xqy for some rows x and y and xq ^ ny ∈ L 1 ∩ L 2 (since q must take at least one a and must take the same number as on the left, as on the right )

    P :: = L1 - L2

    {a ^ nb ^ na ^ n | n ≥ 0} is the language Q, where

    Q :: = L1 - P

0
source

More articles:


All Articles