Context-Free Grammar and Bacchus-Naur Form (BNF)

Introduction to Context-Free Grammar

• Context-Free Grammar: A type of grammar suitable for describing the syntax of programming languages.
• BNF (Bacchus-Naur Form): Notation used for writing grammars, first used for Algol 60.
• Developed by Bacchus and Naur.

Grammar Rules and Terms

• Grammar Rule:
  • Consists of a left-hand side (non-terminal) and a right-hand side (terminals or non-terminals).
  • Example: The rule defining a digit as a non-terminal can expand into terminals (0, 1, 2, etc.).
• Terminals:
  • Also known as lexemes.
  • Elements of the grammar that cannot be simplified further.
• Non-Terminals:
  • Indicated by angled brackets.
  • Can be expanded into other grammar rules.
• Vertical Bars:
  • Represent "or" in grammar rules.

Defining Numbers with Grammar

• To define multi-digit numbers, we introduce recursive rules.
• Example:
  • Two rules: digit (for single digits) and NAT (for natural numbers).
  • NAT can be a digit or a digit followed by a NAT (recursive).
  • Allows creation of numbers of arbitrary length.

Derivation Process

• Derivation:
  • Starts with a non-terminal and expands step-by-step.
  • Example derivation of the number 930 using grammar rules.
  • Leftmost derivation: Always expand the leftmost non-terminal first.

Avoiding Leading Zeros

• Problem: Grammar allows numbers starting with zero (e.g., 0930).
• Solution: Redefine grammar to avoid leading zeros.

Redefining Grammar for Natural Numbers

• New Grammar Rules:
  • NAT = digit or non-zero followed by digits.
  • digit = 0 or non-zero.
  • non-zero = any terminal digit from 1 to 9.
  • digits = digit or digit followed by digits (recursive).
• Ensures numbers don't start with zero unless they are standalone zero.

Conclusion

• This new grammar allows generation of non-negative integers correctly.
• Future videos will cover more aspects of syntax and grammar examples.