@article{4556,
  author = {Naveneetha Vasudevan, Laurence Tratt},
  title = {Exploring Ambiguity in Context-Free Grammars through Randomized Search},
  journal = {International Journal of Computational Linguistics Research},
  year = {2025},
  volume = {16},
  number = {3},
  doi = {https://doi.org/10.6025/ijclr/2025/16/3/91-98},
  url = {https://www.dline.info/jcl/fulltext/v16n3/jclv16n3_1.pdf},
  abstract = {Ambiguity detection in context-free grammars (CFGs) is critical for parsing programming languages, yet it is
undecidable in the general case. Traditional methods, such as exhaustive search and approximation techniques,
either struggle with scalability or risk false positives. This paper introduces a novel search-based approach,
embodied in the prototype tool SinBAD, for detecting ambiguity in context-free grammars (CFGs). SinBAD
employs random search techniques to generate sentences from a given grammar and uses an Earley-based
parser to identify ambiguous parses. The tool's architecture supports configurable backends that influence
sentence generation strategies. An extensive experiment compares SinBAD against existing tool-ACLA
(approximation-based) and AmbiDexter (hybrid)-on two datasets: randomly generated CFGs and manually
altered ambiguous grammars from real programming languages (Pascal, SQL, Java, C). Results show that
SinBAD detects more ambiguities in random grammars within shorter time frames and performs comparably
on programming language grammars. The study highlights the strengths of random search in exploring diverse
parts of the search space, though results vary across runs. The paper concludes with a discussion on the
limitations of the random grammar generator. It suggests future directions, including expanding experiments
to larger, real-world grammars and exploring additional search-based techniques.},
}