BAC Honours Thesis

A Comparative Analysis of Parsing Algorithms for Context-Free Grammars

By Huan Vo

Supervised by: Rahul Gopinath

Abstract

Parsing context-free grammar is a practical problem in computer science. A parser is an algorithm that can infer how an input string is generated from a specific grammar. A general context-free parser is capable of working with any context-free grammar. This thesis is dedicated to the analysis, and comparison of general parsing algorithms efficiency in practical scenarios. We implement different parsers in Python, and compare their performance against real world grammars. Our work includes CYK, Valiant and also Earley, GLL, GLR parsers.

The study benchmarks these algorithms across multiple grammar types TinyC, S-Expression, Calculator, and JSON. The results show of prohibitively large constant factors in Valiant parser, as well as CYK’s less than ideal performance. In contrast, generalised parsers such as Earley, GLL, and GLR demonstrate near-linear performance on practical grammars, with GLR achieving the best scalability overall. BRNGLR further improves runtime efficiency, offering up to an 8.3% speedup without any negative side effects.