Lexicale analyse

Lexicale analyse is het omzetten van een reeks karakters in een reeks symbolen. In het geval van een natuurlijke taal zijn deze symbolen woorden, bij een programmeertaal zijn dit onder meer identifiers, operators en datatypes. Lexical analysers, lexers of scanners zijn programma's die deze omzetting uitvoeren.

Voor de omzetting van een reeks karakters in een reeks symbolen wordt een aantal regels geformuleerd die aangeven welke opeenvolgende karakters een (geldig) symbool vormen. Deze regels worden meestal gespecificeerd door middel van reguliere expressies.

Lexers worden vooral gebruikt in compilers en interpreters. Daar vormen ze de eerste fase in het lezen en interpreteren van een programma. Nadat een bronprogramma (dat bestaat uit een reeks karakters, meestal in een file) is omgezet in een reeks symbolen, worden deze symbolen verder verwerkt door een parser.

Ook buiten het gebruik in compilers en interpreters worden lexers vaak gebruikt in combinatie met parsers. Dit is echter niet noodzakelijk. Een lexer is bijvoorbeeld ook bruikbaar in een programma dat alle HTML-tags uit een tekst verwijdert. Een parser is daarbij overbodig.

Het gebruik van een aparte lexer die de lexicale analyse uitvoert voordat een parser aan het werk gaat heeft een aantal voordelen. Parsers zijn, vergeleken met lexers, complex. Lexers zijn eenvoudig en zijn snel. Verder verloopt de constructie van lexers vrijwel altijd geautomatiseerd (met behulp van een zogenaamde lexer generator).^[1][2]

• Iedere bewerking op een invoertekst die door de lexer wordt uitgevoerd, hoeft niet door de parser te worden uitgevoerd. Omdat parsers, in tegenstelling tot lexers, meer menselijke bemoeienis nodig hebben maakt het gebruik van een lexer de taak van de programmeur eenvoudiger.
• Lexers zijn snel. Sommige problemen kunnen zowel door een parser als door een lexer opgelost worden (bijvoorbeeld het herkennen van commentaarregels in broncode). Een lexer doet dit vanwege zijn eenvoudige implementatie veel sneller.
• De relatief complexe parser (of de specificatie voor een parsergenerator) hoeft geen rekening te houden met details zoals spaties en witregels of het onderscheid tussen integers en zwevendekommagetallen.
• Een lexer werkt met invoer en zal daarom vaak systeemafhankelijke code bevatten, bijvoorbeeld voor het lezen van karakters uit een invoerbuffer. Door de lexer te scheiden van de parser en andere onderdelen van een compiler/interpreter wordt de systeemafhankelijke code beperkt tot een klein deel van de hele compiler waardoor deze makkelijker naar andere systemen kan worden overgezet.
• De grammatica van verschillende programmeertalen vertoont vaak te veel verschillen om het hergebruik van parsers mogelijk te maken. De verschillen tussen lexicale structuren van programmeertalen zijn vaak veel minder groot (zo hebben veel talen dezelfde regels voor identifiers en integers), waardoor lexers eerder voor hergebruik in aanmerking komen.

Bij een lexicale analyse is een symbool (Engels: token) een combinatie van karakters die een betekenisvolle eenheid vormen. Bij Nederlandse zinnen zijn de letters de karakters en de woorden zijn symbolen: niet alle combinaties van karakters vormen een woord.

Neem bijvoorbeeld de volgende expressie in C:

res = reken(3,5);

Hier worden 13 verschillende karakters gebruikt (r, e, s, =, k, n, 3, 5, spatie, haakje-openen, haakje-sluiten, komma en puntkomma) om 9 symbolen te vormen. De onderstaande tabel geeft de gevormde symbolen weer, het type van elk symbool en de waarde (indien van toepassing):

Het resultaat in de tabel is specifiek voor het lexen van een C-programma. Merk op dat sommige symbolen geen waarde hebben, zoals een haakje of een =-teken. Als een symbool wel een waarde heeft, dan is het de taak van de lexer om deze door te geven aan het programma dat de lexer gebruikt (meestal een parser).

De lexical scan vormt de eerste analyse die toegepast wordt op de invoer van de compiler. Deze invoer is een rij van karakters uit een alfabet, die wellicht een woord vormt in de zin van een formele taal.

Een dergelijke formele taal onderscheidt in een woord meestal twee categorieën van deelrijen (rijen symbolen die voor kunnen komen als onderdeel van een langere invoer): de rijen die een speciale betekenis hebben binnen de formele taal (in programmeertalen vaak sleutelwoorden of keywords genoemd, of anders operatoren (wiskundige operatoren als + en *, bijvoorbeeld)) en de min of meer vrijgevormde rijen die namen aanduiden binnen de invoer (in het geval van een programmeertaal valt te denken aan identifiers).

De taak van een lexicale scanner binnen de compiler is om de invoer onder te verdelen in kleinere onderdelen genaamd tokens en deze tokens in volgorde door te geven aan de parser. Een token is dan een object dat door de parser herkend kan worden als een sleutelwoord binnen de formele taal, dan wel als een naam, en zodanig behandeld kan worden.

De werking van de lexical scanner berust op het berekeningsmodel van een eindigetoestandsautomaat: iedere deelrij van de invoer heeft een eindige lengte en de invoer wordt symbool voor symbool ingelezen – het is dus na ieder symbool direct mogelijk om te zien of de deelrij waaraan de scanner bezig is nog een sleutelwoord kan zijn, of dat het onmogelijk is en dat de deelrij dus een naam moet zijn. Het model van tekeninvoer en toestandsovergangen van de eindigetoestandsautomaat is de perfecte ondersteuning voor dit proces.

Naast het herkennen van sleutelwoorden en namen is de lexical scanner uiteraard ook toegerust om "lege" karakters te herkennen (de karakters die het einde markeren van een deelrij binnen de invoer – in programmeertalen wordt hiervoor vaak de spatie gebruikt) en meestal ook om namen te herkennen die verkeerd gevormd zijn (bijvoorbeeld omdat zij karakters bevatten die door de invoertaal van de compiler niet toegestaan zijn in namen, of bepaalde karakters bevatten op plaatsen waar die karakters niet voor mogen komen). Daarmee is de lexical scanner niet alleen een hulpmiddel voor de parser, maar ook toegerust om de eerste van een serie analyses uit te voeren die bepaalt of de invoer van een compiler werkelijk tot de invoertaal behoort.

Zoals eerder opgemerkt berust de lexical scanner als systeem op de eindige automaat. Deze automaat is gerelateerd aan de reguliere expressie, die uiteraard gebruikt kan worden om tokens te beschrijven (een letterlijke opeenvolging van symbolen voor sleutelwoorden, een algemenere beschrijving voor namen, een categorie voor lege karakters, enzovoorts). Reguliere expressies zijn in staat om de reguliere taal te beschrijven die alle mogelijke tokens van een taal omvat. Reguliere expressies kunnen ook automatisch vertaald worden in eindige automaten. En eindige automaten kunnen via een vast schema geïmplementeerd worden op een computer. Het is dus mogelijk om uit een verzameling reguliere expressies volautomatisch een lexicale scanner te genereren voor gebruik in een compiler.

Hoewel het mogelijk is om zelf een lexer te programmeren, worden lexers meestal gegenereerd met een lexergenerator zoals lex. In dat geval worden een aantal regels gespecificeerd, waarbij elke regel bestaat uit een reguliere expressie en een actie. De reguliere expressie definieert welke karakterreeksen een geldig symbool vormen. De bijbehorende actie wordt uitgevoerd wanneer zo'n symbool gevonden wordt.

Lexergenerators vertalen de gespecificeerde reguliere expressies naar een eindigetoestandsautomaat (finite state machine). Deze eindigetoestandsautomaat wordt geïmplementeerd met behulp van zogenaamde lookup tables. Dit zijn tabellen waarin voor iedere mogelijke combinatie van toestand en invoerkarakter aangegeven wordt wat de volgende toestand is.

• lex
• Lexicale scan