Ambiguity Detection for Programming Language Grammars

Context-vrije grammatica's vormen de basis voor ontwikkeling van nieuwe programmeertalen of domeinspecifieke talen (DSLs), maar ook voor analyse van bestaande talen. Net als de Nederlandse grammatica bestaat een programmeertaalgrammatica uit regels die beschrijven wat een geldige zin (broncode) is. Tegelijkertijd kunnen de regels worden gebruikt om de betekenis van een zin te achterhalen. Een groot probleem is echter dat een grammatica ambigu kan zijn, wat betekent dat er zinnen zijn met meerdere betekenissen. Dit kan leiden tot 'spraakverwarring' tussen de programmeur en de computer, waardoor er bugs kunnen ontstaan. Het is daarom van belang dat alle ambiguïteiten worden opgelost voordat een taal in gebruik wordt genomen. Helaas is het detecteren van ambiguïteit een klassiek onbeslisbaar probleem, waardoor er geen sluitende detectiemethode mogelijk is. Toch kunnen gedeeltelijke oplossingen in de praktijk zeer waardevol zijn. Het doel van Bas Bastens onderzoek is om methoden voor ambiguïteitsdetectie te vinden die bruikbaar zijn voor grammatica's van realistische programmeertalen. De hoofdbijdrage is een nieuwe aanpak voor het sneller vinden van ambiguïteiten, genaamd AmbiDexter. AmbiDexter maakt gebruik van een filter om regels uit een grammatica te verwijderen die zeker niet bijdragen aan ambiguïteit. Hierdoor blijft een kleinere grammatica over die nu sneller kan worden doorzocht op eventuele resterende ambiguïteit. Door middel van experimenten op grammatica's uit de praktijk toont Basten aan dat het detectieproces met AmbiDexter soms wel duizenden keren kan worden versneld.