Lexikalische Analyse Stephan Poll. 1 Inhalt I.Einordnung und Funktion der lexikalische Analyse...

Lexikalische Analyse

Stephan Poll

2

InhaltI. Einordnung und Funktion der lexikalische Analyse

II. Grundlagen

II.1 Grundsymbole

II.2 Reguläre Sprachen und reguläre Ausdrücke

II.3 Endliche Automaten

III. Erkennung von Grundsymbolen mit endlichen Automaten

III.1 Konstruktion eines NEA aus einem regulären Ausdruck

III.2 Simulation eines NEA

III.3 Konstruktion eines DEA aus einem NEA

III.3 Minimierung eines DEA

III.4 Simulation eines DEA

IV. Implementierung eines Scanners

V. Zusammenfassung

3

Einordnung und Funktion der lexikalischen Analyse

Lexikalische Analyse

Erste Phase des Analyseteils im Rahmen des Compilerbaus

Modul des Compilers : Scanner

Verschränktes Arbeiten mit dem Modul für die syntaktische Analyse

4

Einordnung und Funktion der lexikalischen Analyse

Aufgaben eines Scanners:

Transformieren des Eingabestroms

Erkennen von Elementen der Quellsprache

Codieren der erkannten Elemente

Output :

Strom atomarer Einheiten

zur Weiterverarbeitung durch Parser

5

InhaltI. Einordnung und Funktion der lexikalische Analyse

II. Grundlagen

II.1 Grundsymbole

II.2 Reguläre Sprachen und reguläre Ausdrücke

II.3 Endliche Automaten

III. Erkennung von Grundsymbolen mit endlichen Automaten

III.1 Konstruktion eines NEA aus einem regulären Ausdruck

III.2 Simulation eines NEA

III.3 Konstruktion eines DEA aus einem NEA

III.3 Minimierung eines DEA

III.4 Simulation eines DEA

IV. Implementierung eines Scanners

V. Zusammenfassung

6

Grundsymbole

Was sind Grundsymbole?

Grundsymbole : zu erkennende Elemente der Zielsprache

Art und Anzahl muss definiert werden

Formale Definition erfolgt mit Hilfe von regulären Ausdrücken

7

Grundsymbole

Beispiel:

if (a < 0) a=a+1;

Mögliche Strukturierung

Keywords if

Identifier a

Delimiter ( , + , ….

Literals 1

8

InhaltI. Einordnung und Funktion der lexikalische Analyse

II. Grundlagen

II.1 Grundsymbole

II.2 Reguläre Sprachen und reguläre Ausdrücke

II.3 Endliche Automaten

III. Erkennung von Grundsymbolen mit endlichen Automaten

III.1 Konstruktion eines NEA aus einem regulären Ausdruck

III.2 Simulation eines NEA

III.3 Konstruktion eines DEA aus einem NEA

III.3 Minimierung eines DEA

III.4 Simulation eines DEA

IV. Implementierung eines Scanners

V. Zusammenfassung

9

Reguläre Sprachen und reguläre Ausdrücke

Reguläre SpracheDie vom Scanner erkannten Einheiten bilden eine nichtleere reguläre

Sprache

Beschreibung erfolgt über reguläre Ausdrücke

10

Reguläre Sprachen und reguläre Ausdrücke

Regulärer AusdruckJedes Element eines Alphabets ist ein regulärer Ausdruck und

beschreibt eine reguläre Sprache

Verknüpfung einzelner Ausdrücke zu neuem Ausdruck

reguläre Ausdrücke r und s:

(rs)

(r|s)

r*

11

InhaltI. Einordnung und Funktion der lexikalische Analyse

II. Grundlagen

II.1 Grundsymbole

II.2 Reguläre Sprachen und reguläre Ausdrücke

II.3 Endliche Automaten

III. Erkennung von Grundsymbolen mit endlichen Automaten

III.1 Konstruktion eines NEA aus einem regulären Ausdruck

III.2 Simulation eines NEA

III.3 Konstruktion eines DEA aus einem NEA

III.3 Minimierung eines DEA

III.4 Simulation eines DEA

IV. Implementierung eines Scanners

V. Zusammenfassung

12

Endliche Automaten

Liegen als formales Modell der Erkennung von Grundsymbolen zu

Grunde

Beschreiben Verhalten mit Hilfe von Zuständen und Aktionen

Ein Automat ist endlich, wenn die ihm zu Grunde liegende

Zustandsmenge endlich ist

Arten

Nichtdeterministische endliche Automaten

Deterministische endliche Automaten

13

Endliche Automaten

Nichtdeterministische Endliche AutomatenZustandsübergänge unter ε

Folgezustand nicht immer eindeutig

Ein NEA ist ein 5-Tupel M = (Σ,Q, Δ,q0,F)

Σ : Eingabealphabet

Q : Zustandsmenge

Δ ⊆ Q ⅹ (Σ ⋃ {ε}) ⅹ Q : Übergangsfunktion

q0 ∈ Q : Startzustand

F ⊆ Q : Endzustände

14

Endliche Automaten

Deterministische endliche AutomatenKeine Übergänge unter ε

Folgezustand eindeutig

Übergangsrelation als partielle Funktion δ:

δ : Q ⅹ Σ → Q

15

Darstellung von Automaten

Übergangsdiagramm

Kantenmarkierter, endlicher und

gerichteter Graph

Beispiel:

regulärer Ausdruck

r = (a|b)+c

0

1

2

a

b

b

a

3

c

c

ab

16

Darstellung von Automaten

ÜbergangstabelleBeispiel: r = (a|b)+c

ZustandEingabesymbol

a b c

0 1 2

1 1 2 3

2 1 2 3

0

1

2

b

a

a

b

3

c

c

ab

17

InhaltI. Einordnung und Funktion der lexikalische Analyse

II. Grundlagen

II.1 Grundsymbole

II.2 Reguläre Sprachen und reguläre Ausdrücke

II.3 Endliche Automaten

III. Erkennung von Grundsymbolen mit endlichen Automaten

III.1 Konstruktion eines NEA aus einem regulären Ausdruck

III.2 Simulation eines NEA

III.3 Konstruktion eines DEA aus einem NEA

III.3 Minimierung eines DEA

III.4 Simulation eines DEA

IV. Implementierung eines Scanners

V. Zusammenfassung

18

Erkennen von Grundsymbolen mit endlichen Automaten

Zu jedem regulären Ausdruck lässt sich ein endlicher Automat

konstruieren

Eingabeüberprüfung durch Simulation

Mögliches Vorgehen

Konstruktion NEA Simulation NEA

Konstruktion NEA Konstruktion DEA Simulation DEA

Konstruktion NEA Konstruktion DEA Minimierung DEA

Simulation DEA

Konstruktion DEA ggf. Minimierung Simulation DEA

19

InhaltI. Einordnung und Funktion der lexikalische Analyse

II. Grundlagen

II.1 Grundsymbole

II.2 Reguläre Sprachen und reguläre Ausdrücke

II.3 Endliche Automaten

III. Erkennung von Grundsymbolen mit endlichen Automaten

III.1 Konstruktion eines NEA aus einem regulären Ausdruck

III.2 Simulation eines NEA

III.3 Konstruktion eines DEA aus einem NEA

III.3 Minimierung eines DEA

III.4 Simulation eines DEA

IV. Implementierung eines Scanners

V. Zusammenfassung

20

Konstruktion eines NEA aus einem regulären Ausdruck

Satz: “Zu jedem regulären Ausdruck r gibt es einen NEA, der die von r

beschriebene reguläre Menge akzeptiert“

Konstruktion aus einem gegebenen Ausdruck r:

Für jedes Symbol a aus dem r zu Grunde liegenden Alphabets ein

Teilautomat:

i fa

21

Konstruktion eines NEA aus einem regulären Ausdruck

Konstruktion Teilautomat für ε

Regeln für die Kombination(s|t)

i f

ε

N(s)

N(t)

ε ε

ε

22

Konstruktion eines NEA aus einem regulären Ausdruck

Regeln für die Kombination (weiter)(st)

i N(s) N(t) f

23

Konstruktion eines NEA aus einem regulären Ausdruck

Beispiel:

Regulärer Ausdruck r = y(x|z)*yz

Vorgehen:

1.: Erstellen der Teilautomaten für x,y,z

und ε

i fx

i fy

i fz

i fε

24

Konstruktion eines NEA aus einem regulären Ausdruck

2. Kombination von den NEA für y

und εy

0ε

1 2

3. NEA für (x|z)

4ε

5 6

7 8ε ε

ε

x

z

9

25

Konstruktion eines NEA aus einem regulären Ausdruck

4. NEA für (x|z)*

3ε

5 6

7 8ε ε

ε

x

z

4 9εε 10

ε

ε

26

Konstruktion eines NEA aus einem regulären Ausdruck

5. NEA für y(x|z)*yz

2

ε

3ε

5 6

7 8ε ε

ε

x

z

4 9

yε

z11 ε 12

ε

13

10

0 ε 1y

ε

ε

27

InhaltI. Einordnung und Funktion der lexikalische Analyse

II. Grundlagen

II.1 Grundsymbole

II.2 Reguläre Sprachen und reguläre Ausdrücke

II.3 Endliche Automaten

III. Erkennung von Grundsymbolen mit endlichen Automaten

III.1 Konstruktion eines NEA aus einem regulären Ausdruck

III.2 Simulation eines NEA

III.3 Konstruktion eines DEA aus einem NEA

III.3 Minimierung eines DEA

III.4 Simulation eines DEA

IV. Implementierung eines Scanners

V. Zusammenfassung

28

Simulation eines NEA

Idee

NEA N zu einem regulären Ausdruck r

Einlesen eines Inputstroms

Ermitteln des Zustandsverlaufs

Prüfen auf akzeptierten Zustand

Problem

Nichtdeterminiertheit

29

Simulation eines NEA

Lösung

Ermitteln aller möglichen Folgezustände

Vorgehen

Gegeben: aktueller Zustand z (oder Menge Z) und nächstes

Eingabesymbol a

move (z , a) = Z

ε-clousure (Z) = Z2

Nach Ende der Eingabe: Prüfen, ob Menge von möglich Zuständen

einen akzeptierten Zustand enthält

30

InhaltI. Einordnung und Funktion der lexikalische Analyse

II. Grundlagen

II.1 Grundsymbole

II.2 Reguläre Sprachen und reguläre Ausdrücke

II.3 Endliche Automaten

III. Erkennung von Grundsymbolen mit endlichen Automaten

III.1 Konstruktion eines NEA aus einem regulären Ausdruck

III.2 Simulation eines NEA

III.3 Konstruktion eines DEA aus einem NEA

III.3 Minimierung eines DEA

III.4 Simulation eines DEA

IV. Implementierung eines Scanners

V. Zusammenfassung

31

Konstruktion eines DEA aus einem NEA

Satz: „ Wird eine Sprache L von einem NEA akzeptiert, so gibt es einen

DEA der L akzeptiert.“

Prinzip:

Konstruktion eines DEA aus NEA durch Bildung von

Zustandsgruppen

32

Konstruktion eines DEA aus einem NEA

Algorithmus

1. Menge DZ = ε-clousure (s0)

2. Prüfen, ob unmarkierter Zustand in DZ wenn ja: weiter, sonst 7.

3. Nimm ersten Zustand Z aus Z der nicht markiert ist

4. Markiere Z

5. Für jedes Eingabesymbol s:

i. Zn = ε-clousure ( move ( Z , s) ) falls Zn nicht in DZ ii. sonst iii.

ii. Zn zu DZ als unmarkierter Zustand

iii. UT [ Z , s ] = Zn

6. Gehe zu 2.

7. Ende

33

Konstruktion eines DEA aus einem NEA

Beispiel

2

ε

3ε

5 6

7 8ε ε

ε

x

z

4 9

yε

z11 ε 12

ε

13

10

0 ε 1y

ε

ε

34

Konstruktion eines DEA aus einem NEA

Beispiel (weiter)

A = ε-clousure (0) = {0,1}

A: Schritt 5. für y

B = ε-clousure ( move ( A , y ) ) = {2,3,4,5,7,10}

B: Schritt 5. für x,y und z

x C = ε-clousure ( move ( B , x ) ) = {4,5,6,7,9,10}

y D = ε-clousure ( move ( B , y ) ) = {11,12}

z E = ε-clousure ( move ( B , z ) ) = {4,5,7,8,9,10}

…

35

Konstruktion eines DEA aus einem NEA

ZustandDEA

Zustandsmenge

NEAA {0,1}B {2,3,4,5,7,10}C {4,5,7,8,9,10}D {11,12}E {4,5,7,8,9,10}F {13}

F

A

D

B

C

E

x

z

x

z x

y

y

y

z

y

z

36

Minimierung eines DEA

Algorithmus

1. Konstruktion der Ausgangspartition P

2. Für jede Gruppe G in P

für jedes Eingabezeichen a

i. Überprüfen, ob jeder Zustand in G unter a Übergang in selbe Gruppe G2 hat

wenn nein, weiter, sonst 3.

ii. G Zerlegen , weiter mit i.

3. Neue Partition P2

37

Minimierung eines DEA

Algorithmus (weiter)

4. Falls P2 identisch mit P weiter, sonst 2. mit P = P2

5. Repräsentanten wählen

38

Minimierung eines DEA

Beispiel

P : G1 = {A,B,C,D,E} , G2 = {F}

F

A

D

B

C

E

x

z

x

z x

y

y

y

z

y

z

39

Minimierung eines DEA

Beispiel (weiter)

G1 : Trennung durch z

G1.1 = {A,B,C,E} G1.2 = {D}

G1.1 : Trennung durch y

G1.1.1 = {A} G1.1.2 = {B,C,E}

Finale Partition:

Pneu : G1.1.1 = {A} , G1.1.2 = {B,C,E} , G1.2 = {D} , G2 = {F}

40

Simulation eines DEA

Simulation durch „Nachschlagen in der Übergangstabelle“

Einzelne Symbole einer Eingabe sequentiell einlesen

Aktuellen Zustand festhalten

Überprüfen, ob nach vollständigem Einlesen aktueller Zustand ein

Endzustand ist

41

Implementierung eines Scanners

2 Möglichkeiten der Implementierung

Verwendung eines Scannergenerators

Definieren der regulären Ausdrücke in festgelegter Terminologie

Festlegen der Aktionen, die bei Erkennen von jeweiligen Grundsymbolen

durchgeführt werden

Beispiel für einen Generator: LEX

Manuelle Implementierung

Überlegungen bzgl. Reihenfolge und Struktur der Automaten

Konstruktion von komplexen Automaten zur Überprüfung von mehreren

regulären Ausdrücken

42

Zusammenfassung

Lexikalische Analyse

Zerlegen des Eingabestroms in atomare Einheiten

Erkennen von Einheiten auf Basis vordefinierter Struktur reguläre

Ausdrücke

Konstruktion von endlichen Automaten zu regulären Ausdrücken

Simulation der Automaten zur Überprüfung einer Eingabe

43

Das war's….

Fragen ?