Context Free Grammer (CFG)

Introduction

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 non-terminals
  Σ =  Finite set of terminals
  P =  Set of production rules
  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.

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.
• Used in compiler design (parsing).
• Used in natural language processing.
• Describes languages not possible with regular expressions.