Context Free Grammars
• Chomsky(Liguist) describe four classes of generative devices grammars that defines four classes of languages.
• Two of these grammar classes
•• Context free Grammer
•• Regular Grammer
• These Grammars turned out to be useful for describing the syntax of programming language.
Basically: Contextt free grammar is a language generator which describes Syntax of natural language.
Backus-Naur form:
In 1960 John Bakus and Peter Naur introduced formal method For describing Syntax of programming language which is known as Backus Naur form or simply BNF.
BNF was basically designed for ALGOL60
BNF and context free grammars was nearly identical.
BNF is a meta language for primary languages. Meta Language is a language that is used to describe another language.
BNF: Symbols to describe a syntax
::= means 'is defined as'
<> means ' can be described as'
| means 'or'
BNF uses" abstractions" for syntatic structures.
For example: JAVA assignment statement:
Terminals: Symbol that can appear in the output of a language because of its rules themselves.
Non Terminals: • Syntatic entities that defines a part of the grammar.
• Non-Terminals can be replaced and they are string, composition of Terminals and non-Terminals.
Example of Terminals:
+={}*|
if, while, do,int
Double, float, A,B
Example of non terminal:
Sentences, expressions, List of numbers, words, terms, statements, programs
Example
if loop
Structure (1)
If(condition)
{
body
}
structure (2)
if(condition)
{
Body
}
else
{
body
}
