CKY Parsing with Probabilistic Context-Free Grammars

Overview

This project implements the CKY (Cocke-Kasami-Younger) parsing algorithm for Probabilistic Context-Free Grammars (PCFGs). The parser can perform membership checking, probabilistic parsing with backpointers, and parse tree reconstruction. The project works with the ATIS (Air Travel Information Services) dataset from the Penn Treebank.

Project Structure

Core Files

• cky.py - Main CKY parser implementation
• grammar.py - PCFG grammar representation and validation
• evaluate_parser.py - Parser evaluation script using PARSEVAL metrics
• atis3.pcfg - PCFG grammar file (980 rules) extracted from ATIS corpus
• atis3_test.ptb - Test corpus (58 sentences) in Penn Treebank format

Technical Requirements

Python Version

• Python 3.6+ is required. The code is not compatible with Python 2.x.

Required Packages

This project uses only standard Python libraries:

• collections
• math
• sys
• itertools

No external packages are required. For best results, use a recent Python 3 distribution (e.g., Anaconda or Miniconda).

Environment Setup

1. Install Python 3.6 or higher
   • Download Python
   • Or use Anaconda
2. Clone or download this repository
3. Ensure all data files are present
   • atis3.pcfg and atis3_test.ptb must be in the same directory as the Python scripts.

Usage

Basic Grammar Operations

from grammar import Pcfg

# Load grammar
with open('atis3.pcfg', 'r') as grammar_file:
    grammar = Pcfg(grammar_file)

# Check grammar validity
print(f"Start symbol: {grammar.startsymbol}")
print(f"Number of rules: {len(grammar.lhs_to_rules)}")

# Look up rules
print(grammar.lhs_to_rules['PP'])  # All PP rules
print(grammar.rhs_to_rules[('NP', 'VP')])  # Rules with NP VP on RHS

Parsing Operations

from cky import CkyParser

# Initialize parser
parser = CkyParser(grammar)

# Test sentence
tokens = ['flights', 'from', 'miami', 'to', 'cleveland', '.']

# Membership checking
is_grammatical = parser.is_in_language(tokens)
print(f"Sentence is grammatical: {is_grammatical}")

# Full parsing with probabilities
table, probs = parser.parse_with_backpointers(tokens)

# Get most probable parse tree
from cky import get_tree
tree = get_tree(table, 0, len(tokens), grammar.startsymbol)
print(f"Parse tree: {tree}")

Evaluation

# Run evaluation on test corpus
python evaluate_parser.py atis3.pcfg atis3_test.ptb

Troubleshooting

• FileNotFoundError: Ensure all data files are in the correct directory.
• UnicodeDecodeError: If you encounter encoding issues, open files with encoding='utf-8'.
• Python Version Errors: Confirm you are using Python 3.6 or higher (python --version).
• Parse Failures: If the parser fails to parse a sentence, check that the grammar is in Chomsky Normal Form and that the start symbol matches the test data.

Implementation Details

CKY Algorithm

The implementation follows the standard CKY dynamic programming approach:

1. Initialization: Fill diagonal with terminal productions
2. Main Loop: For each span length and position:
   • Try all possible split points
   • Combine constituents using grammar rules
   • Keep track of best probability and backpointers
3. Completion: Check if start symbol spans entire sentence

Data Structures

Parse Table Format

table[(i,j)][nonterminal] = backpointers
# Example: table[(0,3)]['NP'] = (("NP",0,2), ("FLIGHTS",2,3))

Probability Table Format

probs[(i,j)][nonterminal] = log_probability
# Example: probs[(0,3)]['NP'] = -12.1324

Tree Representation

Parse trees are represented as nested tuples:

('TOP', ('NP', 'flights'), ('VP', ('V', 'depart'), ('PP', ('P', 'from'), ('NP', 'miami'))))

Grammar Format

PCFG Rules

Each rule is represented as (LHS, RHS, probability):

PP -> ABOUT NP [0.00133511348465]
S -> NP VP [0.694915254237]

Penn Treebank Format

Test sentences use bracketed notation:

(TOP (S (NP i) (VP (WOULD would) (VP (LIKE like) (VP (TO to) (VP (TRAVEL travel) (PP (TO to) (NP westchester))))))) (PUN .))

Performance Benchmarks

• Coverage: ~67% of test sentences parsed
• Average F-score (parsed): ~0.95
• Average F-score (all): ~0.64

Key Features

• Handles unseen words through grammar design
• Graceful degradation for unparseable sentences
• Efficient dynamic programming implementation
• Uses PCFG probabilities for disambiguation
• Logarithmic probability computation for numerical stability
• Backpointer tracking for parse tree reconstruction
• PARSEVAL metrics for constituency parsing
• Compatible with Penn Treebank format
• Comprehensive coverage and accuracy reporting

File Organization

HW2/
├── cky.py                 # Main parser implementation
├── grammar.py             # Grammar representation
├── evaluate_parser.py     # Evaluation framework
├── atis3.pcfg            # PCFG grammar rules
├── atis3_test.ptb        # Test corpus
└── README.md             # This file

Error Handling

• Validates grammar format and CNF compliance
• Checks probability table consistency
• Handles malformed input gracefully
• Provides debugging utilities for table inspection