Disambiguating Context-Free Grammars by Selecting the Minimum-Cost Parse Tree

Taal is een systeem van regels dat ons in staat stelt om complexe ideeën op te bouwen uit eenvoudige onderdelen. In de wereld van computers worden deze regels grammatica's genoemd, en zij vertellen een machine hoe ze een reeks code of een zin moet begrijpen. Ideaal gezien zou een set regels tot slechts één mogelijke betekenis voor een gegeven invoer moeten leiden. Echter, veel grammatica's die worden gebruikt om programmeertalen te beschrijven zijn ambigu, wat betekent dat een enkele reeks tekst op meerdere, tegenstrijdige manieren kan worden geïnterpreteerd. Een klassiek voorbeeld is een zin met twee operaties, zoals het optellen en vermenigvuldigen van getallen. Zonder duidelijke instructies weet een computer niet of hij eerst moet optellen en dan vermenigvuldigen, of eerst moet vermenigvuldigen en dan optellen. Op dezelfde manier kan een computer bij een keten van "if"-statements mogelijk niet weten bij welke voorwaarde een "else"-instructie hoort. Voor een computer om correct te kunnen functioneren, moet hij precies één interpretatie kiezen, maar de regels zelf bieden vaak geen duidelijke winnaar.

Decennialang was de standaardmethode om deze verwarring aan te pakken door de regels te dwingen minder ambigu te zijn door ze handmatig te herschrijven of door speciale verklaringen toe te voegen die de computer vertellen welke weg te nemen als hij vastloopt. Deze methoden werken goed voor specifieke typen problemen, maar ze vereisen menselijke interventie en kunnen soms de oorspronkelijke structuur van de taal verbreken. Een nieuwe benadering, voorgesteld door Mina Hematikarimkhani, behandelt het probleem niet als een puzzel die opgelost moet worden door de regels te herschrijven, maar als een optimalisatievraagstuk. In plaats van te proberen de foute antwoorden te verwijderen, vraagt deze methode de computer om elke mogelijke interpretatie te evalueren en de interpretatie te selecteren die het "goedkoopst" is volgens een specifieke set criteria.

De kern van het idee is om een kostenwaarde toe te kennen aan elke mogelijke boomstructuur die de computer bouwt om de tekst te begrijpen. In dit systeem vertegenwoordigt een boom één manier om de zin te parsen. De kosten zijn geen geldwaarde, maar een score gebaseerd op drie factoren. Ten eerste telt het systeem hoe vaak de boom de voorkeurspatronen van de gebruiker schendt, zoals regels over welke operaties eerst moeten gebeuren. Ten tweede telt het het aantal knooppunten in de boom, wat helpt om te voorkomen dat de computer in oneindige lussen terechtkomt. Ten slotte, als twee bomen dezelfde score hebben, breekt een unieke identifier de gelijke stand om te garanderen dat de computer altijd exact hetzelfde resultaat kiest. De computer houdt vervolgens de boom aan met de laagste totale score. Omdat het systeem slechte keuzes bestraft in plaats van ze direct te verbieden, garandeert het dat elke geldige zin in de taal precies één interpretatie krijgt, zelfs als die interpretatie enkele regelovertredingen bevat.

Om deze beste boom te vinden, gebruiken de onderzoekers een methode genaamd dynamisch programmeren, wat een manier is om complexe problemen op te lossen door ze op te splitsen in kleinere, overlappende stukjes. Stel je voor dat de computer naar een zin kijkt en probeert uit te zoeken wat de beste manier is om elk klein deel ervan te begrijpen, om die stukjes vervolgens te combineren om het geheel te begrijpen. Voor eenvoudige gevallen, zoals het bepalen van de volgorde van operaties, hoeft de computer alleen naar directe buren te kijken. Echter, voor complexere situaties, zoals het "dangling else"-probleem waarbij een "else"-clausule bij een nabijgelegen "if" of een verre "if" kan horen, moet de computer verder in de structuur kijken. Om dit aan te pakken, introduceerden de onderzoekers een concept genaamd een profiel. Terwijl de computer een klein deel van de boom bouwt, creëert het ook een kort overzicht, of profiel, dat de bovenliggende structuur vertelt wat eronder ligt, zoals of een tak eindigt met een specif kind van een specifieke regel. Dit stelt de computer in staat om geïnformeerde beslissingen te nemen over verre delen van de zin zonder telkens de hele boom opnieuw te hoeven opbouwen.

De methode werkt voor elke set regels, inclusief die welke lege stappen of circulaire referenties bevatten die andere systemen zouden verwarren. In tests pasten de onderzoekers deze techniek toe op diverse voorbeelden, waaronder wiskundige expressies met gemengde operatoren en geneste voorwaardelijke statements. In elk geval identificeerde het systeem succesvol de meest passende boom. Wanneer het bijvoorbeeld werd geconfronteerd met een reeks die zowel optellen als vermenigvuldigen bevatte, koos het systeem correct de boom die de standaard wiskundige precedentie respecteerde, door een hogere kostenwaarde toe te kennen aan de boom die deze regel schond. Wanneer het werd geconfronteerd met geneste "if"-statements, koppelde het de "else" correct aan de dichtstbijzijnde "if", wat de standaardconventie in programmeren is. Het systeem handelde ook gevallen af waarbij geen specifieke regels werden verstrekt, waarbij het terugviel op een consistente, deterministische keuze gebaseerd op de structuur van de boom zelf.

Hoewel de methode krachtig is, is de auteur duidelijk over de beperkingen ervan. De tijd die het algoritme nodig heeft om te draaien groeit aanzienlijk naarmate de invoer groter wordt, waardoor het te traag is voor de hoge snelheidseisen van moderne productiecompilers die miljoenen regels code per seconde verwerken. In plaats daarvan suggereren de onderzoekers dat deze benadering het beste geschikt is voor tools die willekeurige, door gebruikers gedefinieerde grammatica's moeten afhandelen, zoals taalredactoren, statische analyse-tools of educatieve software waar reproduceerbaarheid en de afhandeling van complexe, rommelige regels belangrijker zijn dan pure snelheid. De kwaliteit van het resultaat hangt volledig af van de patronen die de gebruiker verstrekt; als de regels incompleet of tegenstrijdig zijn, zal het systeem nog steeds een resultaat teruggeven, maar is het mogelijk niet het resultaat dat een mens bedoelde. De methode lost het fundamentele wiskundige probleem niet op om te bepalen of een grammatica ambigu is in de eerste plaats, maar het biedt een betrouwbare manier om die ambiguïteit te navigeren zodra deze wordt aangetroffen.

Dit werk vertegenwoordigt een verschuiving in hoe we over taalverwerking denken. In plaats van te proberen de regels van een taal perfect te dwingen voordat een computer ze ooit ziet, staat het de computer toe om alle mogelijkheden te verkennen en de beste te kiezen op basis van een duidelijke, meetbare standaard. Het erkent dat ambiguïteit een kenmerk is van veel natuurlijke en kunstmatige talen en biedt een manier om dit te beheren zonder de oorspronkelijke structuur van de taal te verliezen. Door disambiguatie te behandelen als een zoektocht naar de minimale kosten, hebben de onderzoekers een tool gecreëerd die flexibel, robuust en in staat is om de rommelige realiteit van complexe grammatica's te hanteren, waardoor voor elke geldige zin altijd één duidelijk, reproduceerbaar antwoord is.