Parsing-with-Cocke-Kasami-Younger-CKY-Algorithm

Project Overview

This project implements the Cocke-Kasami-Younger (CKY) algorithm, a fundamental parsing algorithm used in computational linguistics and formal language theory. The CKY algorithm determines whether a given string can be generated by a context-free grammar (CFG) in Chomsky Normal Form (CNF). Additionally, an extension to the Probabilistic CKY (PCKY) algorithm is implemented, which computes the probability of different parse trees.

Features

• Implementation of the CKY algorithm for syntactic analysis of strings.
• Transformation of any CFG to CNF, allowing the use of CKY on arbitrary grammars.
• Handling of the empty string (ϵ) in grammar transformations.
• Implementation of the Probabilistic CKY (PCKY) algorithm, which assigns probabilities to different parses.
• Dictionary-based grammar representation for efficient rule lookup.

Installation

1. Clone the repository:

   git clone <repository_url>
   cd cky-algorithm

2. Install dependencies (if required):

   pip install numpy

Usage

Run the main script to test the CKY algorithm:

python main.py

This script will:

• Load the grammar.
• Convert it to Chomsky Normal Form (if needed).
• Parse input strings using CKY or PCKY.

Files Included

• main.py – The main program that runs the CKY algorithm.
• cky_fnc_pcky.py – Contains implementations of CKY, CFG-to-CNF transformation, and PCKY.
• test_cases/ – A folder containing test grammars and input strings.
• PAA_Pràctica.pdf – The project report detailing the implementation.

Grammar Representation

Grammars are stored as Python dictionaries, where:

• Keys are non-terminal symbols.
• Values are lists of possible productions.

Example:

{
    "S": [("NP", "VP"), ("VP",)],
    "NP": [("Det", "N")],
    "VP": [("V", "NP"), ("V",)],
    "Det": ["the", "a"],
    "N": ["cat", "dog"],
    "V": ["chased", "saw"]
}

Algorithm Explanation

1. CKY Algorithm

The CKY algorithm operates as follows:

• Constructs a parsing table using dynamic programming.
• Fills in the table bottom-up, checking which non-terminals can generate substrings.
• If the start symbol S appears in the final cell, the string is accepted.

2. CFG to CNF Conversion

To use CKY, grammars must be in Chomsky Normal Form (CNF). The conversion involves:

• Removing empty rules (ϵ-productions).
• Eliminating unit productions (rules of the form A → B).
• Converting long right-hand sides into binary rules (A → BC).

3. Probabilistic CKY (PCKY)

• Extends CKY to probabilistic grammars.
• Stores probabilities of different parse trees.
• Uses dynamic programming to keep track of the most probable parse.

Future Improvements

• Implement a user interface for interactive parsing.
• Optimize performance for large grammars.
• Extend PCKY to generate parse trees.

Authors

• Zhihao Chen
• Zhiqian Zhou

References

• Formal Language & Parsing Theory – Cocke, Kasami, Younger (1970s)
• Natural Language Processing – Use of CKY for sentence parsing
• Wikipedia: CKY Algorithm

---

This README provides a comprehensive overview of the project, guiding users on installation, usage, and algorithm details. 🚀