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.

0: tst 1
1: jmp 3 
2: jmp 6
3: dec 1
4: inc 0
5: jmp 0
6: hlt
#3
#5

Beim vorliegenden Quelltext sollen sich folgende lexikalische Einheiten ergeben:

'0', ':', 'tst', '1', '1', ':', 'jmp', '3', ..., '#', '3', '#', '5'

Die lexikalischen Einheiten können unterschiedlichen Mustertypen zugeordnet werden. So gibt es ein Muster für den inc-Befehl. Dieses Muster besteht aus den drei Zeichen 'i', 'n' und 'c', die zusammen die Einheit 'inc' bilden. Entsprechend gibt es Muster für die anderen Befehle. Ein weiteres Muster wird für Zahlangaben benötigt. Zahlangaben wie 2 oder 12 oder 400 bestehen aus den Ziffern '0', ..., '9', die hintereindergereiht werden. Zusätzlich gibt es das Muster Doppelpunkt und das Muster '#' für Kommentare bzw. Datenzeilen.

Für jedes dieser Muster wird ein Name eingeführt: ZAHL für Zahldarstellungen, INC für den inc-Befeh 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:

(ZAHL,'0')
(DP,':')
(TST,'tst')
(ZAHL,'1')
(ZAHL,'1')
(DP,':')
(JMP,'jmp')
(ZAHL,'3')
...
(KO,'#')
(ZAHL,'3')
(KO,'#')
(ZAHL,'5')

Token-Festlegung mit regulären Ausdrücken

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

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

# Namen der Token
tokens = ['ZAHL', 'INC', 'DEC', 'JMP', 'TST', 'HLT', 'DP', 'KO']

# Beschreibung der Token
t_ZAHL  = r'0|[1-9][0-9]*'
t_INC   = r'inc'
t_DEC   = r'dec'
t_JMP   = r'jmp'
t_TST   = r'tst'
t_HLT   = r'hlt'
t_DP    = r':'
t_KO    = r'\#'

Aufgabe 1

Welche Zeichenketten passen auf das Token-Muster ZAHL?. Gib Beispiele für solche Zeichenketten an.

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 Python-Quelltext zeigt, wie man die LEX-Implementierung von PLY zur Tokenfestlegung nutzt.

# Namen der Token
tokens = ['ZAHL', 'INC', 'DEC', 'JMP', 'TST', 'HLT', 'DP', 'KO']

# Beschreibung der Token
t_ZAHL  = r'0|[1-9][0-9]*'
t_INC   = r'inc'
t_DEC   = r'dec'
t_JMP   = r'jmp'
t_TST   = r'tst'
t_HLT   = r'hlt'
t_DP    = r':'
t_KO    = r'\#'

# 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)

Beachte, dass hier 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. syntaxBonsai.py) ab. Einen Scanner zu den vorgegebenen Tokenmustern kann man jetzt folgendermaßen erzeugen:

import ply.lex as lex
from syntaxBonsai import *

# Testprogramm
quelltext = '''
0: tst 1
1: jmp 3 
2: jmp 6
3: dec 1
4: inc 0
5: jmp 0
6: hlt
#3
#5
'''

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

# lexikalische Analyse mit Erzeugung der Token
scanner.input(quelltext)
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(ZAHL,'0',2,1)
LexToken(DP,':',2,2)
LexToken(TST,'tst',2,4)
LexToken(ZAHL,'1',2,8)
LexToken(ZAHL,'1',3,10)
LexToken(DP,':',3,11)
LexToken(JMP,'jmp',3,13)
LexToken(ZAHL,'3',3,17)
LexToken(ZAHL,'2',4,20)
LexToken(DP,':',4,21)
LexToken(JMP,'jmp',4,23)
LexToken(ZAHL,'6',4,27)
LexToken(ZAHL,'3',5,29)
LexToken(DP,':',5,30)
LexToken(DEC,'dec',5,32)
LexToken(ZAHL,'1',5,36)
LexToken(ZAHL,'4',6,38)
LexToken(DP,':',6,39)
LexToken(INC,'inc',6,41)
LexToken(ZAHL,'0',6,45)
LexToken(ZAHL,'5',7,47)
LexToken(DP,':',7,48)
LexToken(JMP,'jmp',7,50)
LexToken(ZAHL,'0',7,54)
LexToken(ZAHL,'6',8,56)
LexToken(DP,':',8,57)
LexToken(HLT,'hlt',8,59)
LexToken(KO,'#',9,63)
LexToken(ZAHL,'3',9,64)
LexToken(KO,'#',10,66)
LexToken(ZAHL,'5',10,67)

Aufgabe 2

(a) Probiere das selbst einmal aus. Lade hierzu die Datei bonsai1.zip herunter und entpacke sie. Führe anschließend die Datei test_scanner.py aus. Teste auch weitere Quelltexte. Teste insbesondere die im vorangegangenen Abschnitt gezeigten Quelltexte, ob sie sich in eine zulässige Tokenfolge zerlegen lassen.

(b) Ändere selbst die Beschreibung der Token in sinnvoller Weise ab und teste die neuen Festlegungen.

Aufgabe 3

Im Abschnitt Zusammenfassung - JOHNNY-Maschinensprache wird die Maschinensprache des JOHHNY-Rechners erläutert. Entwickle einen Scanner für diese Sprache.