The CYK algorithm is a canonical dynamic-programming method for deciding membership in context-free languages. In this work we re-implement CYK in Zig, a systems language that offers explicit memory control and compile-time safety. We formulate the algorithm as a balanced search over a two-dimensional table, preserving a strict height-balanced invariant on the implicit binary decomposition of substrings. The implementation achieves the classical O(n^3· |G|) time bound and O(n^2) space bound, verified by static AST inspection and formal invariant proofs.
Manuscript Attribution: This manuscript is an empirical research preprint synthesized via agentic autonomous systems engineering pipelines adhering to academic two-column preprint conventions under the direction of Mateus Yonathan.
Hardware & Algorithmic Provenance: Algorithmic complexity bounds, execution profiles, and memory models cite verified static AST analysis and compiler toolchains evaluated by autonomous agent feedback loops.
Limitation of Liability & Scholarly Purpose: Disseminated solely for scholarly inquiry, peer discussion, and reproducible empirical comparison. It does not constitute formal peer-reviewed accreditation. Any reliance upon the mathematical proofs or complexity bounds herein is strictly at the reader's own legal and technical risk.
@article{yonathan2026_2026_10_16_cyk_parsing_algorithm_for_context_f,
title={CYK Parsing Algorithm for Context-Free Grammars in Zig: Execution Semantics and Fo...},
author={Yonathan, Mateus},
journal={Polyglot Systems Lab Research Preprints},
year={2026},
publisher={Polyglot Systems Lab},
url={https://myonathanlinkedin.github.io/papers/2026-10-16_cyk_parsing_algorithm_for_context_f/},
howpublished={\url{https://raw.githubusercontent.com/myonathanlinkedin/mini-papers/main/papers/2026-10-16_cyk_parsing_algorithm_for_context_f/2026-10-16_cyk_parsing_algorithm_for_context_f.pdf}}
}