Search code examples
syntaxcontext-free-grammarbnf

What are Context-Free Grammars and Backus Naur Form?

Can someone please explain in layman's terms:

  1. what a context-free grammar is?

  2. what Backus Naur Form is?

  3. How to use this notation?

  4. How to do string derivation?

  5. How to describe language syntax?

Solution

  • A context-free grammar (CFG) G is a quadruple (V, Σ, R, S) where

    • V: a set of non-terminal symbols
    • Σ: a set of terminals (V ∩ Σ = Ǿ)
    • R: a set of rules (R: V → (V U Σ)*)
    • S: a start symbol

    Example of CFG:

    • V = {q, f,}
    • Σ = {0, 1}
    • R = {q → 11q, q → 00f, f → 11f, f → ε}
    • S=q
    • (R= {q → 11q | 00f, f → 11f | ε })

    As far as I understand, Backus Naur Form (BNF) is another way of representing the things that are shown in the Context-Free Grammar (CFG)

    Example of BNF:

    [number] ::= [digit] | [number] [digit]

    [digit] ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

    which can be read as something like: "a number is a digit, or any number followed by an extra digit" (which is a contorted but precise way of saying that a number consists of one or more digits) "a digit is any one of the characters 0, 1, 2, ... 9"

    Difference:

    Notation of these two representations are a bit different, i-e

    --> equals ::=

    | equals or

    there must be some other differences but to be honest I don't know any other :)

    String Derivation:

    Let S be the start" symbol

    • S --> A, the initial state
    • A --> 0A
    • A --> 1B
    • A --> ?
    • B --> 1B
    • B --> ?

    Example of String Derivation:

    Does this grammar generate the string 000111?
    yes, it does!

    • S --> A
    • A --> 0A
    • 0A --> 00A
    • 00A --> 000A
    • 000A --> 0001B
    • 0001B --> 00011B
    • 00011B --> 000111

    that's all from my side, I too am working on it and will surely share if I come to know anymore details about defining the language syntax.

    cheers!