Comparative Analysis of Dynamic Programming, Divide-and-Conquer, and Earley Parsing Approaches for JSON Grammar Recognition

Note

This research, titled "Comparative Analysis of Dynamic Programming, Divide-and-Conquer, and Earley Parsing Approaches for JSON Grammar Recognition," was conducted as part of my final project for the Algorithmic Strategies and Analysis course. It compares the performance of three different parsing approaches for recognizing valid JSON. The final version differs slightly from the one I've uploaded to my lecturer, as I was finally able to spend an entire day running the experiments and include a more comprehensive performance comparison. Feel free to check it out, and don't hesitate to share any feedback or criticism. I'd really appreciate it, and I'll take it as an opportunity to improve my research and writing skills.

Abstract

JavaScript Object Notation (JSON) is one of the most widely used data exchange formats in modern computing systems. Ensuring that JSON documents conform to their syntactic specifications requires efficient grammar recognition techniques. This study presents a comparative performance analysis of three grammar recognition algorithms: dynamic programming based CYK Parsing, divide-and-conquer based Top-Down Predictive Parsing, and generalized Earley Parsing. A CFG representation of JSON was constructed based on RFC 8259 and transformed as necessary to satisfy the requirements of each parsing algorithm. The algorithms were evaluated using JSON datasets of varying structural complexity and compared in terms of execution time, memory consumption, and scalability. Experimental results show that Top-Down Predictive Parsing achieved the best overall performance, consistently recording the lowest execution time and memory usage across all dataset categories. Earley Parsing demonstrated moderate performance while maintaining the flexibility to process arbitrary context-free grammars. In contrast, CYK Parsing incurred the highest computational cost and exhibited limited scalability when processing highly complex JSON documents. The findings indicate that Top-Down Predictive Parsing is the most suitable approach for JSON grammar recognition when an LL(1)-compatible grammar is available, whereas Earley Parsing offers a practical alternative when greater grammatical flexibility is required.