An efficient C implementation of the Cocke–Younger–Kasami (CYK) algorithm — a classic dynamic programming technique to determine if a given string belongs to a Context-Free Grammar (CFG) in Chomsky Normal Form (CNF). Whether you're parsing grammars or diving into compiler theory, this project has you covered 💡📚
- 📥 Input-friendly: Parses grammar rules from standard input
- ✅ CNF Check: Converts grammar to CNF if not already in CNF
- 📊 Parse Table Output: Displays the parsing matrix step-by-step
- 🔍 Membership Test: Checks if a string can be generated by the grammar
- Clone the repository and compile using the provided Makefile:
git clone <repository-url>
cd CYK_Algorithm
make- a. To run the program after building on Unix-like systems:
./bin/cyk_algorithm.exe- b. To run the program on Windows using Docker:
# Build the Docker image
docker build -t cyk-algorithm .
# Run interactively
docker run -it cyk-algorithm
# Or run with input from a file
docker run -i cyk-algorithm < your_input_file.txt- To clean up build files:
make cleanCYK_Algorithm/
├── include/ # 📁 Header files
│ ├── grammar.h # 🧱 Grammar data structures and CNF utilities
│ └── utils.h # 🛠️ Common utility functions
├── src/ # 🧠 Core source files
│ ├── main.c # 🚪 Entry point
│ ├── input.c # 📥 Input parsing logic
│ └── utils.c # 🧰 Utility implementations
├── bin/ # 📦 Compiled executable
├── core/ # 🧮 Object files
└── Makefile # 🛠️ Build configuration
S -> AB | BC
A -> BA | a
B -> CC | b
C -> AB | a
All grammar rules should strictly be in CNF.
Given grammar and input string:
Enter number of productions: 4
Enter productions:
S -> AB
A -> a
B -> b
Enter input string: ab
Expected output:
✅ The string *ab* is derivable from the given grammar.
Made for an assignment with ❤️ by Vedant Kesarwani (@InventedSarawak)
DMs always open for collabs or questions!
If you found this helpful or learned something new, consider starring ⭐ the repo!