3.3.Formal Methods of Describing Syntax

The formal definition of the syntax of a programming language is usually called a grammar. A grammar consists of a set of rules that specify the sequence of characters that form allowable programs in the language being defined. The various formal methods for describing of syntax are:

  1. Context free grammars
  2. BNF grammars
  3. Extended BNF
  4. Syntax Graphs
  5. Finite state automata
  6. Regular Grammars and regular expressions.

3.3.1.Context Free Grammars (CFG)

It is a notation used to specify the syntax of language. Context free Grammars are used to design parsers. The context free grammar was developed by linguist Norm Chomsky for thedefinition of natural language syntax. Grammars are rewriting rules and may be used for both recognition and generation of programs.

A context free Grammar (G) can be defined as:

  • It is a 4-tuple (V,∑,P, S)

where

  1. Vis a set of Non-Terminals or variables.
  2. ∑is set of terminals
  3. Pis set of productions or set of rules.
  4. Sis start symbol.

Gis context free is every production (P) is of formA→α, whereA∑Uandα∑(VU∑)*.

Example 3.1

Write down Grammar for language

  • L= {an|n≥1}

Sol.Let

  • G= (V,∑,P, S)

where

  • V= {S}
  • ∑= {a}

These productions generate the languagean

i.e.,

S⇒a
S⇒as / ⇒ / aa / or / a2
S⇒as / ⇒ / aas / ⇒ / aaa / or / a3
⋮
S⇒as / ⇒ / aas / ⇒ / aaas / ⇒ / …‥ / ⇒ / an

The terminals symbols are basically tokens used in a language.

Example 3.2

Find out language generated by a Grammar

  • G=({s}, {a, b})

Sol.

S / ⇒ / a s b
⇒ / a a s b b
⇒ / a aa s b bb
…………………
⇒ / an-1s bn-1
⇒ / an-1a b bn-1
⇒ / anbn

∴Language

  • L= {anbn|n≥1}

Example 3.3

Write a context free Grammar for Palindrome language.

L= {W C WR|W∑{a, b}*}having middle symbol C. Here R means reverse of string.

Sol.Language represents a Palindrome with a middle symbol 'C'.

∴GrammarG= (V,∑,P, S) will have productions.

  • S→a s a
  • S→b s b
  • S→c

Example:

To generate Palindromea b c b a, derivation is

S / ⇒ / a s a
⇒ / a b s b a
⇒ / a b c b a

3.3.2.BNF Grammars

The Backus-Naur-Form (BNF) was developed in the late 1950s by the linguists John Backus and Peter-Naur for the syntactic description of ALGOL. BNF is a very natural notation for describing syntax. It is popular method of describing programming language syntax. BNF is meta languagei.e.,a language used to describe another language. A BNF grammarGis defined as

  • G= (V,∑,P, S)

where

  • V= Set of abstraction in a BNF grammar. The abstractions are often called variables or non-terminals.
  • ∑= Set of terminal symbols.
  • P= A set of productions or rules.
  • S= A special non-terminal called the start symbol.

The various parameters used are described as:

  1. Abstractions.BNF uses abstractions for syntactic structures. The non-terminals or variables are enclosed between < and >.

Example:TheCassignment statement is represented by the abstraction <assign>. The actual definition of <assign> may be given by

  • <assign>→var> = <expression>
  1. Rules or productions.The productions or rules in BNF have the general fromA→α.

The symbol on the left side of→are called the left hand side (LHS) and the text to the right of the arrow is the definition of right hand side (RHS).

Example:Consider a production

  • <assign>→var> = <expression>

The rules specifies that the abstraction <assign> is defined as an instant of the abstraction <var> followed by lexeme =, followed by an instance of the abstraction <expression>.