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.

Zur Verdeutlichung betrachten wir das folgende Programm:

links
while nichtVorWand:
  ziegelHinlegen
  schritt
#while

Beim vorliegenden Quelltext ergeben sich folgende lexikalische Einheiten:

'links', 'while', 'nichtVorWand', ':', 'ziegelHinlegen', 'schritt', '#while'

Diese lexikalischen Einheiten können unterschiedlichen Mustertypen zugeordnet werden. So gibt es ein Muster, nach dem elementare Anweisungen gebildet werden. Ein weiteres Muster gibt vor, wie das Schlüsselwort zur Einleitung einer Wiederholeanweisung gebildet wird. Für jedes dieser Muster wird jetzt ein Name eingeführt, z.B. ELANW für elementare Anweisungen.

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:

(ELANW,'links')
(WH,'while')
(BED,'nichtVorWand')
(DP,':')
(ELANW,'ziegelHinlegen')
(ELANW,'schritt')
(WH_ENDE,'#while')

Festlegung der Token

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

Als Beispiel betrachten wir die elementaren Anweisungen. Das Muster ELANW lässt sich durch den folgenden regulären Ausdruck beschreiben: beschreiben.

r'schritt|links|rechts|ziegelHinlegen|ziegelAufheben|markeSetzen|markeAufheben'

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_ELANW    = r'schritt|links|rechts|ziegelHinlegen|ziegelAufheben|markeSetzen|markeLoeschen'
t_BED      = r'vorZiegel|nichtVorZiegel|vorWand|nichtVorWand|aufMarke|nichtAufMarke'
t_DP       = r':'
t_WH       = r'while'
t_WH_ENDE  = r'\#while'
t_IF       = r'if'
t_IF_ENDE  = r'\#if'
t_ELSE     = r'else'
t_PASS     = r'pass'

Nutzung von 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.

Bevor wir LEX aktivieren, speichern wir die Tokenfestlegung in einer Datei (z.B. syntaxMyKa.py) ab.

# Namen der Token
tokens = ['ELANW', 'BED', 'DP', 'WH', 'WH_ENDE', 'IF', 'IF_ENDE', 'ELSE', 'PASS']

# Beschreibung der Token
t_ELANW    = r'schritt|links|rechts|ziegelHinlegen|ziegelAufheben|markeSetzen|markeAufheben'
t_BED      = r'vorZiegel|nichtVorZiegel|vorWand|nichtVorWand|aufMarke|nichtAufMarke'
t_DP       = r':'
t_WH       = r'while'
t_WH_ENDE  = r'\#while'
t_IF       = r'if'
t_IF_ENDE  = r'\#if'
t_ELSE     = r'else'
t_PASS     = r'pass'

# 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 zusätzliche Festlegungen vorgenommen werden. So wird beispielsweise festgelegt, dass Leerzeichen, Tabulatoren und Zeilenumbrüche überlesen und nicht als eigene Token betrachtet werden.

Einen Scanner zu den vorgegebenen Tokenmustern kann man jetzt folgendermaßen erzeugen:

import ply.lex as lex
from syntaxMyKa import *

# Testprogramm
programm = '''
links
while nichtVorWand:
  ziegelHinlegen
  schritt
#while
'''

# 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(ELANW,'links',2,1)
LexToken(WH,'while',3,7)
LexToken(BED,'nichtVorWand',3,13)
LexToken(DP,':',3,25)
LexToken(ELANW,'ziegelHinlegen',4,29)
LexToken(ELANW,'schritt',5,46)
LexToken(WH_ENDE,'#while',6,54)

Aufgabe 1

(a) Probiere das selbst einmal aus. Teste auch andere Quelltexte. Teste u.a. den Quelltext linkswhilenichtVorWand:ziegelHinlegenschritt#while. Teste auch solche Quelltexte, die sich nicht in die vorgegebenen Token zerlegen lassen. Wie reagiert der Scanner auf Zeichenketten wie z.B. li? Hast du eine Vermutung? Was macht der Scanner mit einem unsinnigen Quelltext wie z.B. :while if:? Hast du eine Vermutung?

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

(c) Ändere selbst die Beschreibung der Token in sinnvoller Weise ab (z.B. linksDrehen statt links) und teste die neuen Festlegungen.