Skip to content

README.md

Latest commit

 

History

History
55 lines (37 loc) · 2.09 KB

README.md

File metadata and controls

55 lines (37 loc) · 2.09 KB
Raw

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
  1. 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.