Grammar and Parsing: CYK Algorithm Implementation

Version: 4 (current) | Updated: 11/12/2025, 10:32:47 PM

Added description

Description

Grammar and Parsing: CYK Algorithm Implementation

Overview

"Grammar and Parsing: CYK Algorithm Implementation" is a software package written in Python that implements the Cocke‑Younger‑Kasami (CYK) parsing algorithm. The code was created in 2023 and is intended for use in computational linguistics and formal language processing. The package is available as a downloadable repository (access URL placeholder) and is distributed under an unspecified license.

Background

The CYK algorithm is a classic dynamic‑programming method for determining whether a string belongs to a language generated by a context‑free grammar (CFG) in Chomsky normal form. This implementation was developed by an anonymous contributor (creator listed as “Unknown”) for a testing environment named “test.” The project was hosted on the PINAX platform, a repository for computational linguistics tools. No institutional affiliation beyond the test environment is recorded.

Contents

The software bundle contains:
  • Python source files that define the CYK algorithm, including functions for parsing input strings, constructing parse tables, and handling grammar rules.
  • Grammar definition files (in a simple text format) that specify a sample CFG in Chomsky normal form, illustrating how the algorithm can be applied.
  • Documentation (README) that explains the algorithm’s theoretical background, usage instructions, and examples of parsing results.
  • Test scripts that demonstrate the parser on sample sentences and verify correctness against expected parse trees.

The code is modular, with separate modules for grammar parsing, table construction, and result interpretation. It includes comments and type annotations to aid readability and maintainability.

Scope

The implementation focuses exclusively on the CYK algorithm for CFGs in Chomsky normal form. It does not support grammars that are not in CNF, nor does it provide a full parser generator or language processing pipeline. The package is designed for educational and research purposes rather than production use. It covers the year 2023 as the creation date and is limited to English-language documentation. Geographic scope is global, with no regional restrictions noted. The software is not accompanied by a formal license, so usage permissions remain unclear.

Entities

(loading...)

Entity Relationships

(loading...)

Raw Cheimarros Data

@file_pinax -> documents -> @cyk_implementation:software {title: "Grammar and Parsing: CYK Algorithm Implementation", created: @date_2023, subjects: ["CYK Algorithm","Grammar Parsing","Python","Computational Linguistics","Context-Free Grammars"], description: "Implementation of the CYK algorithm for parsing strings according to a given context‑free grammar. Includes grammar definitions and parsing logic in Python."}

@cyk_algorithm:concept {description: "Dynamic‑programming parsing algorithm for context‑free grammars (Cocke‑Younger‑Kasami)."}

@grammar_example:document {productions: {"S": [["A","B"],["B","C"]], "A": [["B","A"],["a"]], "B": [["C","C"],["b"]], "C": [["A","B"],["a"]]}}
@string_baaba:document {value: "baaba"}

@file_grammer_check_py -> documents -> @cyk_parser_py:software {language: @python, implements: @cyk_algorithm, defines_grammar: @grammar_example, parses_string: @string_baaba}
@cyk_parser_py -> uses -> @grammar_example
@cyk_parser_py -> parses -> @string_baaba

@rules_example:document {rules: ["S -> AS","S -> AC","S -> c","A -> a","B -> b","C -> SD","D -> BS"]} 
@string_aacbc:document {value: "aacbc"}

@file_cyk_maker_py -> documents -> @cyk_maker_py:software {language: @python, implements: @cyk_algorithm, defines_rules: @rules_example, parses_string: @string_aacbc}
@cyk_maker_py -> uses -> @rules_example
@cyk_maker_py -> parses -> @string_aacbc

Metadata

Title
Grammar and Parsing: CYK Algorithm Implementation
Type
Software
Creator
Unknown
Institution
test
Created
2023
Language
en
Subjects
CYK Algorithm, Grammar Parsing, Python, Computational Linguistics, Context-Free Grammars
Rights
Unknown
Source
PINAX

Version History (4 versions)

  • ✓ v4 (current) · 11/12/2025, 10:32:47 PM
    "Added description"
  • v3 · 11/12/2025, 2:42:55 PM · View this version
    "Added knowledge graph extraction"
  • v2 · 11/12/2025, 2:42:15 PM · View this version
    "Added PINAX metadata"
  • v1 · 11/12/2025, 2:42:07 PM · View this version
    "Reorganization group: Grammar_and_Parsing"

Additional Components

cyk_maker.py
{
  "error": "Failed to fetch: Unexpected token 'd', \"def parse_\"... is not valid JSON"
}
grammer_check.py
{
  "error": "Failed to fetch: Unexpected token 'g', \"grammar = \"... is not valid JSON"
}

Parent

↑ 01K9W87EVXFE21NYG6VGAQDJCD

No children (leaf entity)