Aalborg den 11.02.2003
Kompilerkonstruktion: Leksikalsk analyse
Det første trin i en kompiler er at læse kildeteksten til det
program man gerne vil have kompileret. Til dette formål bruges en lexer
(også kaldet en scanner) og trinnet kaldes leksikalsk analyse.
Det lexeren gør er at dele kildeteksten op i tokens (ord). Som et
eksempel kildeteksten totalPris = pris + pris * momsSats;
er en streng totalPris, efterfulgt af et tegn =,
efterfulgt af en streng pris, efterfulgt af et tegn +,
osv. Fordelen ved have kildeteksten splittet op i tokens er, at disse er
nemmere at arbejde videre med i det næste faser af kompileringen, parsningen.
Til at beskrive tokens anvendes regulære udtryk. Regulære udtryk er
et simpel sprog som I sikkert kender dels fra f.eks. Windows
søgefacilitet, hvor man kan find alle filer der starter med abc med
følgende regulære udtryk abc*.*.
Litteratur
Appel kapitel 2 "Lexical Analysis".
Læsevejledning
I sektion 2.1 beskrives tokens og token typer samt, hvordan token kan
specificeres i et naturligt sprog. Moralen er, at det er de naturlige sprog dårlige til. Derfor anvendes i stedet et sprog, der kaldes
regulære udtryk. Disse er netop emnet for sektion 2.2. Regulære
udtryk er centrale for den leksikalske analyse så brug tid på af
forstå dem.
Endelig automater en en måde at implementere regulære udtryk på i et
programmeringssprog som VisualBasic eller Pascal. Det er også ved
vha. endelig automater de værktøjer vi bruger i kurset implementerer
en leksikalsk analysator. De endelige automater er emnet for sektion
2.3 og ideen er at forklaret hvad værktøjerne vi bruger gør, altså at
"kigge under motorhjelmen" på f.eks. JavaCC og SableCC.
Sektion 2.4 omhandler NFA'er. Disse er ikke anvendelig i praksis, men
er en meget brugbare notation til at visualisere regulære
udtryk. Herudover kan en NFA altid konverteres til en DFA og disse er
praktisk anvendelige.
Leksikalske analysatorer kodes sjælent i hånden fordi, der eksisterer
gode værktøjer der kan generere den del af en kompiler ud fra
bl.a. regulære udtryk. To sådanne værktøjer (JavaCC og SableCC) til
Java beskrives i sektion 2.5. I skal højest sandsynlig bruge en af
disse i jeres projekt, så det er en god ide at lære at bruge dem.
Opgaver
Appel opgave 2.1, 2.2, 2.4 og 2.5.
Venlig hilsen
Kristian Torp