Scribd
Upload
385 views4 pages

BNF and Rules

BNF is a formal way to specify context-free grammars using production rules. It defines a language's components and syntax. EBNF extends BNF with shorthand notation like Kleene star/plus for repetition. Converting BNF to EBNF makes grammars more concise and readable without losing expressive power. The document provides examples of decimal number grammars in both BNF and equivalent EBNF to illustrate the conversion process and benefits of EBNF notation.

Uploaded by

Amna Atiq
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
385 views4 pages

BNF and Rules

BNF is a formal way to specify context-free grammars using production rules. It defines a language's components and syntax. EBNF extends BNF with shorthand notation like Kleene star/plus for repetition. Converting BNF to EBNF makes grammars more concise and readable without losing expressive power. The document provides examples of decimal number grammars in both BNF and equivalent EBNF to illustrate the conversion process and benefits of EBNF notation.

Uploaded by

Amna Atiq
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

ASSIGNMENT BREAKDOWN

1. BNF
2. WHY DO WE NEED BNF
3. GRAMMAR TO BNF
4. RULES OF BNF
5. EBNF
6. RULES OF EBNF
7. BNF TO EBNF
8. WHY THE CONVERSION IS NEEDED- BNF TO EBNF

1.BNF

BNF = Backus-Naur Form. It is a formal, mathematical way to specify context-free grammars. BNF is Meta language
(Meta language - a language that describes a language, which can describe a programming language). It is precise
and unambiguous.

What does BNF look like?

BNF grammar consists of 4 parts,

- The set of tokens -The set of non-terminal symbols -The start symbols -The set of productions

LHS = RHS

Non-terminals = Terminals/non-terminals

Example 1

Below is a sample BNF grammar:

S := '-' FN | FN

FN := DL | DL '.' DL

DL := D | D DL

D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

Example 2

A := B*(A+C)
Assign -> id := expr

A := expr

A := id*expr

A := B*(expr)

A := B*(id + expr)

A := B*(A + expr)

A := B*(A + id)

A := B*(A + C)

2. WHY DO WE NEED BNF

It's used to write a formal representation of a context-free grammar. BNF uses a declarative syntax that allows you
to define terms via “production rules.” Each rule contains terms that each have more concrete rules until you get
down to “terminals,” which are terms that we can only describe as specific characters (literal values).

3. GRAMMAR TO BNF

As an example: a correct answer for “the set of all strings consisting of zero or more concatenated copies of the
string ab” would be the following grammar:

Grammar- The set of all strings consisting of single or more a’s

S=(a+b)*a(a+b)*

BNF- The set of all strings consisting of single or more a’s

<S> ::= ab

4.RULES OF BNF

BNF is sort of like a mathematical game: you start with a symbol (called the start symbol and by convention usually
named S in examples) and are then given rules for what you can replace this symbol with. The language defined by
the BNF grammar is just the set of all strings you can produce by following these rules.

The rules are called production rules, and look like this:

symbol := alternative1 | alternative2 ...

• A production rule simply states that the symbol on the left-hand side of the := must be replaced by one of the
alternatives on the right hand side.
• The alternatives are separated by |s. (One variation on this is to use ::= instead of :=, but the meaning is the
same.) Alternatives usually consist of both symbols and something called terminals.

• Terminals are simply pieces of the final string that are not symbols.

• There is one special symbol in BNF: @, which simply means that the symbol can be removed. If you replace a
symbol by @ you do it by just removing the symbol. This is useful because in some cases it is difficult to end the
replacement process without using this trick.

• So, the language described by a grammar is the set of all strings you can produce with the production rules. If a
string cannot in any way be produced by using the rules the string is not allowed in the language.

5.EBNF

Extended Backus-Naur form (EBNF) is a collection of extensions to Backus-Naur form. Not all of these are strictly a
superset, as some change the rule-definition relation ::= to =, while others remove the angled brackets from non-
terminals. More important than the minor syntactic differences between the forms of EBNF are the additional
operations it allows in expansions.

An EBNF sample grammar

So in extended BNF the above grammar can be written as:

S := '-'? D+ ('.' D+)?

D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

6.RULES OF EBNF

The rules of EBNF revolving around expressions vary, but often are derived from regular expression syntax

• “ *” (The Kleene Star): means 0 or more occurrences

• “ +” (The Kleene Cross): means 1 or more occurrences

• “ ?”: means 0 or 1 occurrences (sometimes “[ … ]” used instead)

• Use of parentheses for grouping

7.BNF TO EBNF

Grammar for decimal numbers in plain

BNF:

<expr> ::= '-' <num> | <num>

<num> ::= <digits>


| <digits> '.' <digits>

<digits> ::= <digit>

| <digit> <digits>

<digit> ::= '0' | '1' | '2' | '3' |

'4' | '5' | '6' | '7' | '8' | '9'

EBNF - Same grammar in EBNF:

<expr> := '-'? <digit>+ ('.' <digit>+)?

<digit> := '0' | '1' | '2' | '3' | '4' |'5' | '6' | '7' | '8' | '9'

8.WHY THE CONVERSION IS NEEDED- BNF TO EBNF

The EBNF is a way to specify a formal language grammar. It can be considered a metalanguage because it is a
language to describe other languages. A formal language is a language with a precise structure, like programming
languages, data languages, or Domain Specific Languages (DSLs). Just for the record: EBNF is not more powerful
than BNF in terms of what languages it can define, just more convenient. Any EBNF production can be translated
into an equivalent set of BNF productions.

You might also like