Context Free Grammer (CFG)

Introduction

• A Context-Free Grammar (CFG) is a formal system that provides a precise way to define valid strings in a language.

Definition

• A Context-Free Grammar (CFG) is a formal grammar used to define context-free languages, where each production rule has a single non-terminal on the left-hand side.
• A language is said to be context-free if and only if it is accepted by a Pushdown Automaton (PDA).
• A context-free grammar is defined as a 4-tuple:
  G = (V, Σ, P, S)
  where
  V =  Finite set of variables(non-terminals)
  Σ =  Finite set of terminals(alphabet of the language)
  P = Finite set of production rules of the form $A\to \alpha$, where $A\in V$ and $\alpha \in (V\cup \mathrm{\Sigma }{)}^{\ast }$
  
  S =  Start symbol
  Non-terminals (V)
  – are variables used to generate strings.
  – are written in uppercase letters.
  – can be replaced using production rules.
  – For example, S, A, B
  Terminals (Σ)
  – are actual symbols of the language.
  – cannot be replaced.
  – are written in lowercase letters.
  – For example, a, b, 0, 1
  Production Rules (P)
  – Rules that define how non-terminals are replaced.
  – Format: A → α
  – Where A is a single non-terminal, and α is a string of terminals and/or non-terminals.
  Start Symbol (S)
  – are special non-terminal.
  – are used to begin string generation.

Terminology

• Terminals: These are the actual symbols of the language (like a, b, +, id).
• Non-terminals: These are the placeholders for patterns (like E for expression, T for term).
• Productions: These are the rules that replace non-terminals with terminals/non-terminals.
• Derivation: This is the sequence of rule applications to generate strings. There may be 3 types of derivations – 
  • Leftmost derivation: It always replaces the leftmost non-terminal first.
  • Rightmost derivation: It always replaces the rightmost non-terminal first.
  • Parse tree: Tree representation of the derivation showing the structure of the string.
• Language of CFG: This is the set of all strings derivable from the start symbol using production rules.

Characteristics

• A grammar is said to be ambiguous if a string has more than one parse tree.
• Context-free grammars provide a powerful mechanism for defining language syntax and form the foundation of parsing techniques used in compiler design.

Examples

• CFG Example1:

Use/Applications

• CFGs are mainly used to describe the syntax of programming languages.
• The concept of CFG is used in compiler design (parsing).
• CFG is also used in Natural language processing.
• CFG helps in describing languages that are not possible with regular expressions.
• The concept of CFG is used to ensure or validate the documents to follow proper nesting rules, such as XML/HTML/XHTML.

Limitations

• CFGs can describe context-free languages, but not all possible languages.
• They cannot handle languages requiring cross-references or equal counts across multiple symbols (e.g., $\{a^n{b}^n{c}^n\mid n\ge 0\}$).
• For more complex languages, Context-Sensitive Grammars or Turing Machines are needed.