CKY Parser

The CKY Parser is a Python-based implementation of the Cocke-Kasami-Younger (CKY) algorithm. It effectively parses grammatical structures provided in the Doty syntax, enabling the recognition of strings in the Chomsky Normal Form.

Features

• Grammar Parsing: Parses grammars following the Doty syntax and represents them as a dictionary in Python.
• Sliding Window Technique: This technique is employed while reading the grammar to facilitate efficient extraction and storage of grammar rules.
• CKY Algorithm: Uses the CKY algorithm—a tabulation method that employs dynamic programming—to parse the string based on the provided grammar.
  • The main data structure is a 2D list (table) initialized with empty sets and filled according to the CKY algorithm.
  • Helps determine if a given string can be generated by the specified grammar.

Grammar Examples

grammar.txt:

S -> AB | BC
A -> BA | a
B -> C | b
C -> BB | a

With this grammar:

• Parsable Strings: a
• Non-Parsable Strings: abba

Usage

1. Default Execution: Run the code using the default values provided:

python3 parser.py grammar.txt words.txt

2. Custom Execution: Provide your own grammar and string files for parsing:

python3 parser.py your_grammar_file.txt your_string_file.txt

Note: Ensure words.txt or your custom string file contains only one string in Chomsky Normal Form.

Code Structure

• read_grammar(grammar_file): Reads and parses the provided grammar, expecting Doty syntax. Outputs a dictionary representation of the grammar.

• grammar_parse(word, grammar): Executes the CKY algorithm on the provided word using the specified grammar. It determines if the word can be generated by the grammar.

• main(grammar_file, string_file): Main driver function to orchestrate the reading of grammar, word, and the execution of the CKY algorithm.

Contributing

I welcome contributions, suggestions, and feedback. Feel free to fork the repository, raise issues, or submit pull requests.

License

This project is open-source under MIT license.