Context-Free Grammar Normalizer ⚙️

A Python tool that reads a context-free grammar (CFG) from a file and transforms it into two canonical normal forms used in formal language theory and compiler design.

Normal Forms Implemented

Chomsky Normal Form (CNF)

Every production rule has the form:

• A → BC (two non-terminals)
• A → a (one terminal)

CNF is required by the CYK parsing algorithm.

Greibach Normal Form (GNF)

Every production rule has the form:

• A → aα (terminal followed by non-terminals)

GNF guarantees that every derivation step consumes exactly one input token.

Features

• Reads grammar from a structured text file
• Applies all intermediate normalization steps (ε-removal, unit rule elimination, etc.)
• Transforms to both CNF and GNF
• Enumerates all words of length ≤ n generated by the grammar
• Makefile for streamlined execution and output to text files

Getting Started

make          # displays available commands
make run      # runs the normalizer
make test     # runs tests

Tech Stack

Tool	Purpose
Python 3	Core language
Makefile	Task automation

Authors

Ahmad Hatoum · Bastien Guibert

L3 Computer Science project — Université de Versailles Saint-Quentin-en-Yvelines