inf-schule | Entwicklung eines Compilers - MiniPython » Station

Station - Tokenerzeugung mit dem Scanner

Aufgabe des Scanners

Aufgabe eines Scanners ist es, einen Quelltext in lexikalische Einheiten zu zerlegen oder anzuzeigen, dass eine solche Zerlegung nicht möglich ist.

x = 9
y = 6
while x != y:
    if x <= y:
        y = y - x
    else:
        x = x - y
    #end
#end

Beim vorliegenden Quelltext ergeben sich folgende lexikalische Einheiten:

'x', '=', '9', 'y', '=', '6', 'while', 'x', '!=', 'y', ':', ...

Die lexikalischen Einheiten können unterschiedlichen Mustertypen zugeordnet werden. So gibt es ein Muster, nach dem Variablenbezeichner gebildet werden. Ein weiteres Muster gibt vor, mit welchem Symbol eine Zuweisung dargestellt wird. Für jedes dieser Muster wird ein Name eingeführt, VAR für Variablenbezeichner, ZUW für das Zuweisungssymbol usw..

Ein Scanner muss also erkennen, ob sich der Quelltext so in Zeichenketten zerlegen lässt, dass alle Teilzeichenketten einem der vorgegebenen Muster zugeordnet werden können. Zudem muss er die Folge der Token bestehend aus dem Mustername und der zugehörigen Zeichenkette erzeugen:

(VAR,'x')
(ZUW,'=')
(ZAHL,'9')
(VAR,'y')
(ZUW,'=')
(ZAHL,'6')
(WHILE,'while')
(VAR,'x')
(UG,'!=')
(VAR,'y')
(DP,':')
...

Token-Festlegung mit regulären Ausdrücken

Der Aufbau lexikalischer Einheiten wird in der Regel mit Hilfe regulärer Ausdrücke beschrieben.

Als Beispiel betrachten wir Variablenbezeichner. Variablenbezeichner beginnen mit einem Kleinbuchstaben. Danach können beliebig viele Kleinbuchstaben oder Ziffern folgen. Dieses Muster lässt sich mit dem regulären Ausdruck [a-z][a-z0-9]* beschreiben.

Aufgabe 1

Der folgende Auszug aus einer Python-Implementierung zeigt, wie die regulären Ausdrücke zur Beschreibung der Token gebildet werden können.

# Beschreibung der Token
t_ZAHL    = r'[\+|-]?[1-9][0-9]*'
t_NULL    = r'0'
t_ZUW     = r'='
t_PLUS    = r'\+'
t_MINUS   = r'-'
t_GL      = r'=='
t_UG      = r'!='
t_KL      = r'\<'
t_KLGL    = r'\<='
t_DP      = r':'
t_WHILE   = r'while'
t_IF      = r'if'
t_ELSE    = r'else'
t_PASS    = r'pass'
t_END     = r'\#end'

(a) Welche Zeichenketten passen auf das Token-Muster ZAHL?. Gib Beispiele für solche Zeichenketten an. Beachte die Sonderrolle der Zahl Null, für die ein eigenes Token-Muster vorgesehen ist.

(b) Die Festlegung der Token-Muster ist in der vorliegenden Form nicht eindeutig. So passt z.B. die Zeichenkette 'if' auf zwei verschiedene Token-Muster. Welche sind das? Gibt es weitere problematische Zeichenketten?

Tokenerzeugung mit LEX

Das Programm LEX ist in der Lage, ausgehend von einer Tokenbeschreibung in Form regulärer Ausdrücke ein System zur lexikalischen Analyse zu erzeugen. Letztlich generiert LEX aus den regulären Ausdrücken endliche Automaten, die die Analyse von Zeichenketten vornehmen.

Der folgende Quelltext zeigt, wie man die LEX-Implementierung von PLY zur Tokenfestlegung nutzt.

# reservierte Wörter

reserved = {
   'if'    : 'IF',
   'else'  : 'ELSE',
   'while' : 'WHILE',
   'pass'  : 'PASS'
}

# Namen der Token

tokens = ['VAR', 'ZAHL', 'NULL', 'ZUW', 'PLUS', 'MINUS', 'GL', 'UG', 'KL', 'KLGL', 'DP', 'END']
tokens = tokens + list(reserved.values())

# Beschreibung der Token

def t_VAR(t):
    r'[a-z][a-z0-9]*'
    t.type = reserved.get(t.value, 'VAR') # Überprüfung auf reservierte Wörter
    return t

t_ZAHL    = r'[\+|-]?[1-9][0-9]*'
t_NULL    = r'0'
t_ZUW     = r'='
t_PLUS    = r'\+'
t_MINUS   = r'-'
t_GL      = r'=='
t_UG      = r'!='
t_KL      = r'\<'
t_KLGL    = r'\<='
t_DP      = r':'
t_END     = r'\#end'

# Ignorierte Zeichen
t_ignore = " \t"

def t_newline(t):
    r'\n+'
    t.lexer.lineno = t.lexer.lineno + t.value.count("\n")

def t_error(t):
    print("Illegal character '%s'" % t.value[0])
    t.lexer.skip(1)

Zunächst werden reservierte Wörter festgelegt. Das sind die Bezeichner, die nicht als Variablenbezeichner betrachtet werden sollen und daher vom Token-Muster VAR ausgeschlossen werden.

Es folgt die Festlegung der Tokennamen und der zugehörigen regulären Ausdrücke.

Beachte, dass weitere Festlegungen vorgenommen werden. So wird beispielsweise festgelegt, dass Leerzeichen, Tabulatoren und Zeilenumbrüche überlesen und nicht als eigene Token betrachtet werden.

Bevor wir LEX aktivieren, speichern wir die Tokenfestlegung in einer Datei (z.B. syntaxWhile.py) ab. Einen Scanner zu den vorgegebenen Tokenmustern kann man jetzt folgendermaßen erzeugen:

import ply.lex as lex
from syntaxWhile import *

# Testprogramm
programm = '''
x = 9
y = 6
while x != y:
    if x <= y:
        y = y - x
    else:
        x = x - y
    #end
#end
'''

# Erzeugung des Scanners
scanner = lex.lex(debug=0)

# lexikalische Analyse mit Erzeugung der Token
scanner.input(programm)
token = []
tok = scanner.token()
while tok:
    token = token + [tok]
    tok = scanner.token()

# Ausgabe
for tok in token:
    print(tok)

Der im Programm integrierte Test liefert dann folgende Ausgabe:

>>> 
LexToken(VAR,'x',2,1)
LexToken(ZUW,'=',2,3)
LexToken(ZAHL,'9',2,5)
LexToken(VAR,'y',3,7)
LexToken(ZUW,'=',3,9)
LexToken(ZAHL,'6',3,11)
LexToken(WHILE,'while',4,13)
LexToken(VAR,'x',4,19)
LexToken(UG,'!=',4,21)
LexToken(VAR,'y',4,24)
LexToken(DP,':',4,25)
LexToken(IF,'if',5,31)
LexToken(VAR,'x',5,34)
LexToken(KLGL,'<=',5,36)
LexToken(VAR,'y',5,39)
LexToken(DP,':',5,40)
LexToken(VAR,'y',6,50)
LexToken(ZUW,'=',6,52)
LexToken(VAR,'y',6,54)
LexToken(MINUS,'-',6,56)
LexToken(VAR,'x',6,58)
LexToken(ELSE,'else',7,64)
LexToken(DP,':',7,68)
LexToken(VAR,'x',8,78)
LexToken(ZUW,'=',8,80)
LexToken(VAR,'x',8,82)
LexToken(MINUS,'-',8,84)
LexToken(VAR,'y',8,86)
LexToken(END,'#end',9,92)
LexToken(END,'#end',10,97)

Aufgabe 2

(a) Probiere das selbst einmal aus. Teste auch andere Quelltexte. Teste u.a. den folgenden Quelltext: x=2 y=4 if y <= x :d = x - y else: d=y-x#end while d != 0 : if y <= x : x = x - y else: y=y-x #end if y <= x : d = x - y else: d=y-x#end #end. Teste auch solche Quelltexte, die sich nicht in die vorgegebenen Token zerlegen lassen. Wie reagiert der Scanner auf Variablenbezeichner der Gestalt 007? Hast du eine Vermutung? Was macht der Scanner mit einem unsinnigen Quelltext wie z.B. :while 7:? Hast du eine Vermutung?

(b) Versuche, durch Tests herauszufinden, welche Bedeutung die zusätzlichen Zahlangaben in den Token haben.

Aufgabe 3

Das oben gezeigte MyWhile-Programm würde man in einer Java-ähnlichen Schreibweise so darstellen:

x = 9:
y = 6;
while (x != y) {
    if (x <= y) {
        y = y - x;
	}
    else {
        x = x - y;
    };
};

Ändere die Beschreibung der Token so ab, dass sie auf die Java-ähnliche Schweibweise passt.