Compilerbau/Kapitel 1: Lexikalische Analyse

Aus Halloserv Wiki

Die lexikalische Analyse bildet den ersten Schritt des Compilers und wandelt den Quellcode eines Programmes in eine Liste von Token-Attribut Paaren um. Dabei werden zum Beispiel Whitespaces ignoriert, Schlüsselwörter erkannt und Formatierungszeichen gefiltert. Die lexikalische Analyse wird von einem Lexer durchgeführt, der aus einem Scanner und einem Tokenizer besteht.

zurück zur Compilerbau Übersicht

Inhaltsverzeichnis

1 Lexeme und Token
2 Scanner
3 Konstruktion von Scannern
- 3.1 DFA
- 3.2 reguläre Ausdrücke
4 Vom regulären Ausdruck zum DFA
5 Der echte Scanner
- 5.1 Rule of the Longest Match
- 5.2 Implementation
6 Pragmatik

Lexeme und Token

Der Quellcode eines Programmes ist aus Lexemen zusammengesetzt, der Scanner erkennt diese und wandelt sie in Token-Attribut Paare um.

Definition: Lexeme, Token

Ein Lexem ist ein Sinnabschnitt. Ein Token ist ein symbolischer Name für Gruppen von Lexemen (Gruppierung). Die meisten Token tragen Attribute, welche aus Lexemen berechnet wurden.

Bemerkung: Isomorphie

Lexeme und Token-Attribut Paare sind isomorph.

Beispiel: Lexeme und Token

new Segment(pi/2)

Lexem	Token
new	<new>
Segment	<id [Segment]>
(	<lparen>
pi	<id [pi]>
/	<slash>
2	<integer-literal [2]>
)	<rparen>

Scanner

Definition: Scanner

Sei $Σ$ ein Eingabealphabet, $T$ eine endliche Tokenmenge und $A$ eine beliebige Attribuierung. Ein Scanner ist eine Funktion $scan: \Sigma^* \to (T \times A)^*$ , sodass eine Funktion $unscan: (T \times A)^* \to \Sigma^*$ existiert und gilt:

$scan \circ unscan = id_{(T \times A)^*}$
$u n s c a n$ ist homomorph bezüglich $untoken: (T \times A) \to \Sigma^*, unscan(t_1 t_2 \ldots) = untoken(t_1)untoken(t_2)\ldots$

Bemerkung:

$scan \circ unscan \circ scan = scan$
im Allgemeinen gilt nicht $unscan \circ scan = id_{\Sigma^*}$

Konstruktion von Scannern

Es gibt zur Konstruktion von Scannern folgende Möglichkeiten:

von Hand
benutze Bibliothek (in der Vorlesung)
Scannergenerator (Beispiele: lex, flex für C; jlex, jflex für Java; ocamllex für OCaml)

Bei Ansatz b) und c) werden die Lexeme durch eine reguläre Sprache definiert. Dafür gibt es einige Möglickeiten, namentlich die reguläre Grammatik, einen endlicher Automaten (DFA / NFA / $ε$ -NFA) oder regulärer Ausdrücke. Es wird eine Repräsentation der Lexeme benötigt, die eine abstrakte und prägnante Spezifikation sowie eine effiziente Erkennung bereitstellt. Als optimale Lösung ergibt sich, dass Lexeme durch regulärer Ausdrücke spezifiziert werden und die Erkennung mit Hilfe von DFAs implementiert wird. Die folgenden beiden Abschnitte spezifizieren diese Beschreibungen.

DFA

Definition: DFA

Ein DFA (Deterministic Finite Automaton) ist ein 5-Tupel $M = (Q,Σ,δ, q 0, F)$ :

$\begin{array}{ll} Q & = \mbox{endliche Menge der Zustände} \\ \Sigma & = \mbox{Eingabealphabet} \\ \delta & = Q \times \Sigma \to Q \mbox{ Übergangsrelation} \\ q_0 & = \mbox{Anfangszustand} \\ F & = \mbox{Menge der Endzustände} \end{array}$

Erweiterung: $\delta^* = Q \times \Sigma^* \to Q$

$\begin{array}{ll} \delta^*(q, \epsilon) & = q \\ \delta^*(q, aw) & = \delta^*(\delta(q,a), w) \end{array}$

Damit gilt: $w \in L(M) \Leftrightarrow \delta^*(q_0, w) \in F$ .

reguläre Ausdrücke

Um Literale reguläre Ausdrücke von Symbolen zu unterscheiden, werden sie in diesem Text unterstrichen dargestellt, also $(\underline{a}|\underline{\epsilon})$ statt $(a | ε)$ .

Definition: reguläre Ausdrücke

Die Menge der regulären Ausdrücke ist die kleinste Menge $R E (Σ)$ mit

$\begin{array}{lcll} \underline \emptyset \in RE(\Sigma) & & & \mbox{Null-Ausdruck} \\ \underline \epsilon \in RE(\Sigma) & & & \mbox{leeres Wort} \\ a \in \Sigma & \Rightarrow & \underline{a} \in RE(\Sigma) & \\ r_1, r_2 \in RE(\Sigma) & \Rightarrow & r_1r_2 \in RE(\Sigma) & \mbox{Konkatenation} \\ & & r_1 | r_2 \in RE(\Sigma) & \mbox{Alternative} \\ & & r_1^* \in RE(\Sigma) & \mbox{Wiederholung} \end{array}$

Definition: Sprache

Funktion $L: RE(\Sigma) \to \mathcal{P}(\Sigma^*)$

$\begin{array}{ll} L(\underline{\emptyset}) & = \emptyset \\ L(\underline{\epsilon}) & = {\epsilon} \\ L(\underline{a}) & = \lbrace a \rbrace \\ L(r_1r_2) & = L(r_1)L(r_2) = \lbrace w_1w_2 | w_1 \in L(r_1), w_2 \in L(r_2) \rbrace \\ L(r_1 | r_2) & = L(r_1) \cup L(r_2) \\ L(r^*) & = L(r)^* = \lbrace w_1w_2...w_n | n \in \mathbb{N}, w_i \in L(r) \rbrace = \lbrace \epsilon \rbrace \cup L(r) \cup L(r)L(r) \cup \ldots \end{array}$

Ein Wort $w$ gehört zur von $r$ beschriebenen Sprache genau dann, wenn $w \in L(r)$ .

Bemerkung:

r +

$r + = r r *$

Vom regulären Ausdruck zum DFA

Wie oben beschrieben, werden Lexeme in regulären Ausdrücken spezifiziert, ihre Erkennung aber mit Hilfe eines DFA durchgeführt. Traditionell erhält man den DFA folgendermaßen:

$\mbox{regulärer Ausdruck} \to \mbox{NFA}-\epsilon \to \mbox{NFA} \xrightarrow{\mbox{Potenzmengen-Konstruktion}} \mbox{DFA}$

Hier wählen wir ein anderes Verfahren, wir übersetzen direkt vom regulären Ausdruck in einen DFA (nach Brzozowski, Derivations of Regular Expressions, 1964). Die Idee besteht darin, reguläre Ausdrücke als Zustände des DFA zu nutzen. Da jeder Zustand eines Automaten eine Sprache erkennt (nämlich die Wörter, die von hier aus zu einem Endzustand führen), kann diese Sprache durch einen regulären Ausdruck beschrieben werden, der dann die Beschreibung des Zustands liefert.

Falls $q \in Q$ , dann erkennt der reguläre Ausdruck $q$ die Wörter "ab q", d.h. die Wörter, die $q$ in einen Endzustand überführen (hierbei ist $q$ sowohl Zustandsname als auch regulärer Ausdruck).
$q 0$ ist der zu übersetzende reguläre Ausdruck
$q \in F$ falls $L (q) = ε$

Beispiel:

$r_0 = (\underline{\epsilon} | \underline{-})\underline{d}\underline{d}^*$

Man muss nun aus dem gegebenen regulären Ausdruck einen Automaten konstruieren, der ihn erkennt. Hierzu definiert man die Ableitung eines regulären Ausdrucks als Funktion $D: RE(\Sigma) \times \Sigma \to RE(\Sigma)$ mit $aw \in L(r) \Leftrightarrow w \in L(D(r,a))$ . Bevor wir eine Beschreibung von $D$ geben können, benötigen wir noch die Hilfsfunktion $E: RE(\Sigma) \to RE(\Sigma)$ , die auf $ε$ testet, d.h. $\underline{\epsilon}$ zurückgibt, wenn der reguläre Ausdruck nach $\underline{\epsilon}$ aufgelöst werden kann und $\underline{\emptyset}$ sonst.

Definition:

E

$\begin{array}{ll} E(\underline{\emptyset}) & = \underline{\emptyset} \\ E(\underline{\epsilon}) & = \underline{\epsilon} \\ E(\underline{a}) & = \underline{\emptyset} \\ E(r_1r_2) & = E(r_1)E(r_2) \\ E(r_1 | r_2) & = E(r_1) | E(r_2) \\ E(r^*) & = \underline{\epsilon} \end{array}$

Lemma:

Für $r \in RE(\Sigma)$ gilt $L(E(r)) = L(r) \cap \lbrace \epsilon \rbrace$ .

Definition:

D

$\begin{array}{ll} D(\underline{\emptyset}, a) & = \underline{\emptyset} \\ D(\underline{\epsilon}, a) & = \underline{\emptyset} \\ D(\underline{a},b) & =\begin{cases} \underline{\epsilon}, & \mbox{falls } a = b \\ \underline{\emptyset} & \mbox{sonst} \end{cases} \\ D(r_1r_2, a) & = D(r_1, a)r_2 | E(r_1)D(r_2,a) \\ D(r_1 | r_2, a) & = D(r_1, a) | D(r_2, a) \\ D(r^*, a) & = D(r,a)r^* \end{array}$

Nun können wir an die Konstruktion des Automaten $M$ gehen:

Theorem:

Sei $r_0 \in RE(\Sigma)$ . Definiere $M = (Q,Σ,δ, q 0, F)$ wie folgt:

$Q \subseteq RE(\Sigma)$ ist die kleinste Menge, so dass a) $r_0 \in Q$ und b) $r \in Q, a \in \Sigma \Rightarrow D(r,a) \in Q$ .

$\begin{array}{ll} \delta(q, a) & = D(q, a) \\ q_0 & = r_0 \\ F & = {r \in Q | \epsilon \in L(r)} \end{array}$

Dann gilt: $L (r 0) = L (M)$ . $Q$ ist endlich, falls das Ergebnis von $D$ wie folgt vereinfacht wird:

$\begin{array}{lll} r\underline{\emptyset} & = \underline{\emptyset} & \\ r\underline{\epsilon} & = \underline{\epsilon}r & = r \\ r | \underline{\emptyset} & = \underline{\emptyset} | r & = r \\ \underline{\emptyset}^* & = \underline{\epsilon}^* & = \underline{\epsilon} \\ (r^*)^* & = r* & \end{array}$

Beispiel: Zustandsberechnung

Hier sieht man, wie ein Zustand $d d *$ aus dem Anfangszustand $r 0$ und dem Eingabesymbol $-$ berechnet wird.

$\begin{array}{ll} r_0 & = (\underline{\epsilon}|\underline{-})dd^* \\ D(r_0, -) & = D(\underline{\epsilon} | \underline{-}, -)dd^* | E(\underline{\epsilon} | -)D(dd^*, -) \\ & = (D(\underline{-},-) | D(\underline{\epsilon}, -))dd^* | (E(\underline{\epsilon})| E(\underline{-})) D(dd^*, -) \\ & = (\underline{\epsilon} | \underline{\emptyset}) dd^* | (\underline{\epsilon} | \underline{\emptyset}) D(dd^*, -) \\ & = dd^* | D(dd^*, -) \\ & = dd^* | (D(d,-)d^*|E(-)D(d^*,-)) \\ & = dd^* | \emptyset \\ & = dd^* \end{array}$

Der echte Scanner

Mit Hilfe von regulären Ausdrücken, genauer dem matcher, können wir feststellen, ob ein Wort von einem regulären Ausdruck akzeptiert wird, oder formal, ob gilt: $w \in RE(r)$ . Ein Scanner aber muss eine ganze Reihe von Lexemen erkennen und sie in Token-Attribut Paare wandeln. Er beantwortet also die Frage: $w \in RE(r_1) \cup \ldots \cup RE(r_n)$ und dann $w \in RE(r_i)$ . Genauer heisst das, dass der Scanner für die Eingabe $u$ ein $w, v$ bestimmt, so dass gilt $u = w v$ und $w \in RE(r_i)$ . Leider ist diese Bestimmung nicht eindeutig, da matches überlappen können:

Rule of the Longest Match

Beispiel: unklarer Match

formel1 -> Bezeichner
for     -> Schlüsselwort

Eindeutigkeit erzielt man mit Hilfe der Rule of the longest Match, d.h. der längste passende Abschnitt wird gewählt, in obigem Beispiel also formel1. Sind beide matches gleich lang, wird die als erstes kommende Spezifikation bevorzugt.

Implementation

Im Folgenden wird der Code eines in OCaml geschriebenen echten Scanners vorgestellt, der auf den vorausgegangenen Überlegungen basiert.

Der Typ lex-action beschreibt Aktionen um Lexeme in Token-Attribut Paare zu wandeln.

<div style="padding-left:4px;" id="Code: lex-action">Code: lex-action

type ('a, 'token, 'attrib) lex_action =
  'a list * 'a list -> 'token * 'attrib * 'a list
     a)        b)                            c)

</div> Dabei stehen die Listen für diese Symbole:

erkanntes Lexem
Rest der Eingabe
Rest der Eingabe, ist meistens identisch mit b) (d.h. wird durchgeschleift, es gibt aber Ausnahmen: z.B. werden Kommentare entfernt)

Eine Regel der Scannerspezifikation, lex_rule kombiniert einen regulären Ausdruck (zum Erkennen des Lexems) mit einer Aktion (zur Umwandlung in Token-Attribut Paare).

<div style="padding-left:4px;" id="Code: lex_rule">Code: lex_rule

type ('a, 'token, 'attrib) lex_rule =
  'a Regexp.regexp * ('a, 'token, 'attrib) lex_action

</div>

Während des Durchlaufens des Inputstrings, merkt sich der Scanner den aktuellen Zustand in einer Struktur lex_state:

<div style="padding-left:4px;" id="Code: lex_state">Code: lex_state

type ('a, 'token, 'attrib) lex_state =
  (('a, 'token, 'attrib) lex_rule) list

</div> Eine Scannerspezifikation ist dann nichts weiter als ein solcher Zustand, nämlich eine Liste von lex_rules.

<div style="padding-left:4px;" id="Code: initial_state">Code: initial_state

let initial_state spec = spec

</div>

Mit next_state bearbeitet der Scanner ein Symbol und entfernt alle inaktiven Regeln.

<div style="padding-left:4px;" id="Code: next_state">Code: next_state

let next_state state symbol =
  let after_state =
    List.map 
      (function (regexp, action) -> Regexp.after_symbol symbol regexp, action)
      state
 in
 filter 
   (function (regexp, _) -> not (Regexp.is_null regexp))
   after_state

</div>

Die Methode matched_rules schliesslich ermittelt die Endzustände (jene Regeln, die gerade ein Lexem erkannt haben).

<div style="padding-left:4px;" id="Code: matched_rules">Code: matched_rules

let matched_rules state =
  filter 
    (function (regexp, _) -> Regexp.accepts_empty regexp)
    state

</div>

Sind alle Regeln inaktiv, landen wir bei is_stuck:

<div style="padding-left:4px;" id="Code: is_stuck">Code: is_stuck

let is_stuck state = state = []

</div>

Nun folgt der Scanner Code selbst, scan_one extrahiert das nächste Lexem am Anfang des Inputs und wandelt es mit Hilfe der entsprechenden Aktion in ein Token-Attribut Paar, welches zusammen mit dem Rest des Inputs zurück gegeben wird.

Code: Scanner

let scan_one spec input =  
  let (action, rev_lexeme, rest) =
    scan_loop (initial_state spec) [] None input
  in
  action (List.rev rev_lexeme, rest)

let rec scan_loop state rev_lexeme last_match input =
    if (is_stuck state) or (input = [])
    then 
      match last_match with
        None -> raise Scan_error
      | Some match -> match
    else
      let symbol::rest = input in
      let new_state = next_state state symbol in
      let new_rev_lexeme = symbol::rev_lexeme in
      let new_match = 
        match (matched_rules new_state) with
            [] -> last_match
          | (regexp, action)::_ -> Some (action, new_rev_lexeme, rest)
      in
      scan_loop new_state new_rev_lexeme new_match rest

Typischerweise benötigt eine Sprache mehrere Lexerspezifikationen (zum Beispiel Normalzustand (Bezeichner, Literale, Schlüsselwörter), Stringliterale (inneres) und reguläre Ausdrücke (z.B. in JavaScript)).

Code: Scannerspezifiaktionen

let rec scan_normal input = scan_one <spec_normal> input
    and scan_string input = scan_one <spec_string> input
    and scan_regexp input = scan_one <spec_regexp> input

Zusammen mit der Methode scan_one, welche ein einzelnes Lexem erkennt, kann man mit diesen Spezifikationen nun den kompletten Scanner zusammensetzen:

<div style="padding-left:4px;" id="Code: make_scanner">Code: make_scanner

let make_scanner scan_one input =
  let rec loop result rest =
    if rest = []
    then List.rev result
    else
      let (token, attrib, new_rest) = scan_one rest in
      loop ((token, attrib)::rev_result) rest
  in
  scan [] input

</div>

Pragmatik

Bisher haben wir die Erkennung von Schlüsselwörtern im Scanner durch triviale reguläre Ausdrücke erledigt. Das allerdings führt zu einer großen Zustandsmenge und ist ineffizient. Alternativ kann man aber auch eine effizientere Methode verwenden: Man scannt zunächst alle Schlüsselwörter als Bezeichner und konstruiere vorab eine Hashtabelle mit allen Schlüsselwörtern. Nachträglich klassifizert man dann Bezeichner als Schlüsselwörter. Benutzt man perfektes Hashing, kann diese Klassifizierung in $O (1)$ vorgenommen werden.

Der Compiler verwaltet eine Symboltabelle, die Bezeichner auf zugehörige Informationen (Art, Typ, ...) abbildet, das heisst der Bezeichner dient als Schlüssel. Strings sind als Schlüssel allerdings nicht optimal, weswegen Bezeichner beim Scannen auf eindeutige Zahlen abgebildet werden.

Compilerbau/Kapitel 1: Lexikalische Analyse

Aus Halloserv Wiki

Inhaltsverzeichnis

Lexeme und Token

Scanner

Konstruktion von Scannern

DFA

reguläre Ausdrücke

Vom regulären Ausdruck zum DFA

Der echte Scanner

Rule of the Longest Match

Implementation

Pragmatik

Ansichten

Persönliche Werkzeuge

Navigation

Suche

Werkzeuge