Context Free Grammars in Compiler Design

Context free grammar

Context free grammar is a formal grammar which is used to generate all possible strings in a given formal language.

Context-free grammars (CFGs) are used to describe context-free languages. A context-free grammar is a set of recursive rules used to generate patterns of strings. A context-free grammar can describe all regular languages and more, but they cannot describe all possible languages.

Context-free grammars are studied in fields of theoretical computer science, compiler design, and linguistics. CFG’s are used to describe programming languages and parser programs in compilers can be generated automatically from context-free grammars.

Formal Definition

A context-free grammar can be described by a four-element tuple $(�,\mathrm{\Sigma },�,�),$ where

• $�$ is a finite set of variables (which are non-terminal);
• $\mathrm{\Sigma }$ is a finite set $($disjoint from $�)$ of terminal symbols;
• $�$ is a set of production rules where each production rule maps a variable to a string $�\in (�\cup \mathrm{\Sigma })\ast$;
• $�$ $($which is in $�)$ which is a start symbol.

Context free grammar G can be defined by four tuples as:

1. G= (V, T, P, S)  

Where,

G describes the grammar

T describes a finite set of terminal symbols.

V describes a finite set of non-terminal symbols

P describes a set of production rules

S is the start symbol.

In CFG, the start symbol is used to derive the string. You can derive the string by repeatedly replacing a non-terminal by the right hand side of the production, until all non-terminal have been replaced by terminal symbols.

Example:

L= {wcw^R | w € (a, b)*}

Production rules:

1. S → aSa  
2. S → bSb  
3. S → c  

Now check that abbcbba string can be derived from the given CFG.

1. S ⇒ aSa  
2. S ⇒ abSba  
3. S ⇒ abbSbba  
4. S ⇒ abbcbba  

By applying the production S → aSa, S → bSb recursively and finally applying the production S → c, we get the string abbcbba.