What are Context-Free Grammars and Backus Naur For

Can someone please explain in layman's terms:

what a context-free grammar is?
what Backus Naur Form is?
How to use this notation?
How to do string derivation?
How to describe language syntax?

回答1:

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)

Eample 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 dont 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 generates the string 000111?
yes it does!

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

thats 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!

回答2:

A context-free grammar is a type of formal language. Backus Naur form is a specification language for this type of grammar. It is used to describe language syntax.
You should read:
http://en.wikipedia.org/wiki/Formal_language_theory
http://en.wikipedia.org/wiki/Context-free_grammar
http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form