Perl is unparseable

Daarstraks heb ik een verwijzing opgemerkt naar een formeel bewijs dat Perl unparseable is. Dit gaf mij inspiratie voor een bericht met redelijk wat technisch jargon. Indien u dit niet ziet zitten, kan u beter afhaken.

Prima, u heeft er voor gekozen om verder te lezen. Het bericht deed mij terugdenken aan mijn opleiding aan de KULeuven een heel tijdje terug. Een van de vakken die ik toen moest volgen was programmeertalen waarin onder meer aan bod kwam hoe compilers gebouwd werden. De eerste compilers werden nog met de hand gebouwd, nadien zijn er gelukkig efficientere manieren bedacht. Aan het departement Computerwetenschappen hadden ze in die tijd ook een compiler compiler gemaakt, een tool waarmee een compiler automatisch kon gegenereerd worden. Voorwaarde om een dergelijk tool aan de praat te krijgen is het beschikken over een formele syntax van de computertaal waarvoor een compiler moet opgesteld werd worden.

Perl is een programmeertaal - mij niet onbekend - die voornamelijk gebruikt wordt voor het parsen van allerlei documenten. Omdat de syntax van Perl vrij complex in elkaar zit werd reeds gesteld : "Only perl can parse Perl". Het formeel bewijs haalt deze uitspraak bijgevolg onderuit.

De concrete gevolgen van het formeel bewijs lijken mij eerder van academische aard te zijn. Er zijn tools op de markt waarmee Perl-programma's kunnen uitgevoerd worden (strikt genomen zijn het geen compilers maar wel interpreters ...). Een Perl-parser zou onder meer zijn diensten kunnen bewijzen voor tools voor het automatisch analyseren van Perl-programma's, het herformatteren van Perl-programma's, het automatisch genereren van documentatie voor Perl-programma's.

In het bewijs wordt nog verwezen naar een Turing machine. Dit is nog uitvoerig aan bod gekomen in mijn cursus numerieke algebra. Gezien het late uur ga ik daar geen herinneringen meer aan ophalen. U kan elders over dergelijke machines al uitvoerig informatie terugvinden.

Technorati : Perl - parser - Turing machine