Turbo Toolbox

home *** CD-ROM | disk | FTP | other *** search

/ Turbo Toolbox / Turbo_Toolbox.iso / spezial / 02 / texte / pascomp.3 < prev next >

Wrap

Text File | 1980-01-03 | 32.3 KB | 801 lines

Pascomp Pascal baut einen Pascal-Compiler Teil 4: Der Parser VON JOHANNES VELMANS In der vierten Folge der Serie "Pascal baut einen PASCAL-Compi- ler" geht es rund um die Zerteilung (Parsing). Die ersten beiden Kapitel vermittelten einen Einblick in die Grundlagen des Compi- lerbaus und zeigten auch, was der Mensch so alles braucht, um einen Scanner für seine Programmiersprache auf die Beine zu stel- len. Jetzt wollen wir etwas tiefer in den Compilerbau eindringen und uns ein Bild davon verschaffen, was alles geschieht, wenn der Parser des Compilers die vom Scanner erhaltene Symbolfolge "durchnudelt". Die einzelnen Stationen im Parser werden dabei immer unter dem Gesichtspunkt der "allgemeinen Verwendbarkeit" beleuchtet - die Anwendung der vorgestellten Verfahren ist, wie schon früher einmal bemerkt wurde, nicht allein auf die Herstel- lung von (Pascal-)Compilern beschränkt, sondern findet auch bei anderen Programmierobjekten wie Datenbankprogrammen oder Adventu- ren (Satzerkennung) Verwendung. Nun genug der Vorrede, einmal tief durchgeatmet und los geht's : Die Rolle des Parsers im Übersetzer Die Aufgabe eines Compilers besteht darin, wohlgeformte Sätze einer Programmiersprache zu erkennen und daraus semantisch äqu- ivalenten Code zu erzeugen. Trifft der Übersetzer dagegen auf einen Satz, der nicht "wohlgeformt" ist, so muß er entsprechende Aktionen (Errorhandling) auslösen. Diesen Prozess der Satzerken- nung nennt der Informatiker Zerteilung (Parsing). Die Art und Weise, in der geparst wird, spielt für die Komplexität des Compi- lers eine entscheidende Rolle. Es ist sicherlich nicht schwierig, einen Parser so zu konstruieren, daß er bei einem auftretenden Syntaxfehler eine entsprechende Fehlermeldung ausgibt und dann den Zerteilungsprozeß abbricht. Der Parsing-Algorithmus sollte jedoch in der Lage sein, Fehler in Programmen so zu handhaben, daß der Übersetzer den restlichen Programmtext in vernünftigem Rahmen weiter bearbeiten kann. Ein großes Problem bei der Über- setzung ist dabei in den meisten Fällen sicherlich nicht die syn- taktische Struktur, sondern die semantische Definition der Spra- che. So hängt es vorwiegend gerade von der Semantik ab, ob eine Sprache in einem Pass übersetzt werden kann, oder ob mindestens zwei Pässe benötigt werden. Ähnlich wie bei der Behandlung des Scanners, so soll auch hier ein Bildchen den Informationsfluß im Parser in entsprechender Weise verdeutlichen. Abbildung 1 : Parser-Interface ────────────── ─────── ─────────────── ( lexikalische )────────>( Parser)────────>( systematische ) ( Analyse ) ─┬───┬─ ( Analyse ) ────────────── │ │ ─────────────── │ │ │ │ │ │ ───┴───┴─── ( ) ( Error ) ( ) ( Handler ) ( ) ─────────── Kleine Auffrischung und Rückblick auf die erste Folge Wir wollen uns nun ein wenig an die Grundlagen zum Compilerbau (1.Folge) erinnern. Von dem Wissen, was wir uns dort angeeignet haben, benötigen wir gerade im Parser eine ganze Menge. Mal ehr- lich : sind Begriffe wie BNF, Grammatik, Syntax etc. noch gut geläufig ? Zur Erinnerung seien sie hier nochmals ganz kurz er- wähnt (genaueres steht in der Ausgabe 9/87 von Pascal-Internatio- nal) : In einer Programmiersprache können Folgen von Wörtern zu Sätzen konstruiert werden, die das Bild der Sprache formen. Die Syntax einer Programmiersprache ist eine Menge von Regeln, die festlegt, ob ein Satz wohlgeformt ist oder nicht. Der 1963 erst- mals erschienene ALGOL60 Report enthält eine Notation zur Syntax- Beschreibung der Programmiersprache ALGOL. Diese Notation wurde auch für andere Sprachen übernommen und wird nach ihren Entwick- lern Backus-Naur-Form (BNF) genannt. Die genaue Konstruktion und der Aufbau von BNF's wurde bereits in der vorletzten Folge erläu- tert und dürfte wohl noch geläufig sein. Um die gleiche Zeit et- wa, in der die BNF ausgedacht wurde, entwickelte der Linguist Noam Chomsky seine Theorien über Grammatiken. Einen speziellen Typ von Grammatiken nannte er kontextfreie Grammatiken . Die De- finition von kontextfreien Grammatiken wurde bereits in der er- sten Folge eingeführt und kommt auch hier zur Anwendung. Zur Er- innerung nochmals die Schreibweise : Eine kontextfreie Grammatik G ist ein Vier-Tupel G=(T,N,P,Z) mit: - T als Menge der Terminalen, - N als Menge der Nichtterminalen, - P als Produktionsmenge, - Z als Startsymbol, - V als Vereinigungsmenge von T und N. Die Frage danach, ob eine eingegebene Zeichenfolge ein Satz der Sprache ist, die durch die zugehörige Grammatik erzeugt wird, war und ist Gegenstand zahlreicher Studien auf dem Gebiet der Synta- xanalyse, die eine Menge von brauchbaren und verwendbaren Ansät- zen geliefert haben. Einem möglichen Ansatz zur Lösung dieses Problems, der gleichzeitig auch der einfachste Weg ist, liegt die Idee des Kellerautomaten zugrunde. Um es gleich zu Beginn zu sa- gen : zum tieferen Verständnis von Kellerautomaten, sowie von Syntaxanalysen mit Hilfe von Kellerautomaten gehört noch eine gehörige Portion Theorie. Um jedoch die Praktiker und die Intu- itions-Programmierer unter den Lesern nicht vom Feld zu jagen, sollen alle hier beschriebenen Verfahren an Beispielen erläutert werden, um den Rahmen des menschlich Verstehbaren nicht zu spren- gen. Begleitende Ausführungen sind so konzipiert, daß das Prinzip des einzelnen Verfahrens herausgestellt wird. Tiefgreifende Er- klärungen und formale Beweise dafür, daß die einzelnen Algorith- men auch ihren Anforderungen genügen, finden sich dagegen in der angegebenen Literatur. Dort können sich interessierte Hobbyisten und Profis den totalen Durchblick verschaffen. Kellerautomaten Der neue Begriff "Kellerautomat" läßt sich von den altbekannten Begriffen des Automaten und des Kellers ableiten. Was ein deter- ministischer endlicher Automat ist, wird dem aufmerksamen Leser der beiden bisherigen Folgen wohl nicht verborgen geblieben sein, und auch die Bedeutung des Kellers wird einigen nicht fremd er- scheinen. Ein Keller (engl. stack ) ist eine Datenstruktur mit folgenden Operationen in Pascal-Notation : - procedure push(var k:keller; x:item); Ablegen (kellern) des Elements x auf die Kellerspitze (top of stack). - procedure pop(var k:keller); Das oberste Element des Kellers wird von der Kellerspitze ge- löscht (entkellern). Der Keller reduziert sich dabei um ein Element. - function top(k:keller):item; Liesert das an der Kellerspitze befindliche Element zurück. Der Kellerinhalt bleibt dabei unverändert. - function empty(k:keller):boolean; empty=true genau dann, wenn der Keller leer ist. - function create:keller; definiert einen neuen, leeren Keller. ( empty(create)=true ) Ein Keller arbeitet also nach dem altbewährten LIFO Prinzip (Last In, Last Out).Einem sich hartnäckig haltenden Gerücht zufolge sollen ja auch Beamte nach diesem LIFO-Prinzip arbeiten : Grund- sätzlich wird zuerst das bearbeitet, was zuletzt auf den Schreib- tisch gekommen ist. Wehe dem armen Bürger, dessen Akte zuunterst im Stapel ruht (- und ruht - und ruht ). Gegen das LIFO-Prinzip hilft in diesem Fall nur Geduld. Aber zurück zu unserem Arbeit- splatz. Wirft man das Keller- und Automatenkonzept einfach zusam- men, so kommt man dem Arbeitsprinzip des Kellerautomaten schon ziemlich nahe. In graphischer Darstellung arbeitet ein Kellerau- tomat etwa wie folgt : Abbildung 2 : Kellerautomat. Eingabe: ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐ │ a │ b │ b │ a │ b │ b │ a │ b │ b │ a │ b │ b │ a │ │ ... └───┴───┴───┴───┴───┴───┴───┴┬─┬┴───┴───┴───┴───┴───┴───┘ │ │ │ │ ┌─────────────┐ │ │ Keller (stack) │ Endliches ├────────>────┘ │ ┌───┐ │ Gedächtnis │ │ │ b │ └─────────────┘ │ ├───┤ │ │ a │ │ ├───┤ │ │ b │ │ ├───┤ │ │ a │ │ ├───┤ │ │ b │ │ ├───┤ └─────────>─────│ a │ ├───┤ │ │ ├───┤ │ │ └───┘ . . Anschaulich betrachtet, ist der Kellerautomat also in der Lage, ein Zeichen zu lesen und, abhängig vom gelesenen Zeichen der Ein- gabe, seinen Keller entsprechend zu verändern. Eine weitere, zu- sätzliche Fähigkeit wollen wir unserem Kellerautomaten jedoch noch zugestehen : er soll in der Lage sein, seinen Zustand und den Kellerinhalt auch spontan ändern zu können, das heißt, ohne dabei ein Zeichen aus der Eingabe zu lesen oder zu verarbeiten. Deterministische endliche Automaten besitzen nach unserer Defini- tion diese Eigenschaft noch nicht. Formal sieht die Definition dann so aus : Ein Kellerautomat A ist ein 7-Tupel A=(T,Q,R,q[0],F,S,s[0])mit: - T,Q,q[0],F wie beim endlichen Automaten. T soll zusätzlich zu den Eingabezeichen noch ein eindeutig bestimmtes Zeichen # besitzen, mit dem die Eingabefolge abgeschlossen wird. - S ist das Kelleralphabet. Es kann Elemente aus T oder Q enthal- ten, aber auch andere Zeichen sind zugelassen. - s[0] aus S ist die Kellervorbesetzung. Vor der Abarbeitung der Eingabe kann der Keller also mit anderen Zeichen aus dem Kel- lerralphabet besetzt werden. s[0] kann auch das leere Zeichen >e< sein. - R entspricht den Regeln des deterministisch endlichen Automa- ten, die nur um einen Kellerteil erweitert sind. In der dabei verwendeten Formulierung werden die Zeichen ++ für Mengenver- einigung und -- für Mengendifferenz verwendet. Die Regeln haben die Form: sqaw -> s'q'w mit : s,s' aus S*, q,q' aus Q, a aus T+ +{e}- -{#} und w aus T*. Die Sprache L(A) , die von einem Kellerautomaten akzeptiert wird, definieren wir wie folgt : L(A):={w aus (T--{#})* | s0,p0# ->* q# , q aus F} Verbal formuliert bedeutet das : Beim Start ist der Kellerautomat im Zustand q[0], hat die Kellervorbesetzung so und die Eingabe w,die durch ein # begrenzt wird. Gelangt der Kellerautomat in den Zustand q aus F (F = Endzustandsmenge), wobei sowohl die Eingabe als auch der Keller leer sind, dann ist die Eingabe w Element der Sprache L(A). Der Übersicht halber (und zum besseren Verständnis) seien die unterschiedlichen Regeltypen eines Kellerautomaten in Tabellenform dargestellt: Übergänge │ Regeltyp ─────────────────────┼───────────────────── zeichenbestimmend │ sqaw -> s'q'w spontan │ sqw -> s'q'w kellernd(push) │ s[1]qaw -> s[1]s[2]q'w entkellernd(pop) │ s[1]s[2]qaw -> s[1]q'w ersetzend │ s[1]qaw -> s[2]q'w Beispiel eines Kellerautomaten : Gesucht sei ein Kellerautomat, der die Sprache L={wcw[r]|w aus {a,b}*} akzeptiert. (w[r] bedeutet w[Reverse(Rückwärts])). Der Automat habe die Form A=(T,Q,R,q0,F,S,s0) mit: T={a,b,c} ; Q={q[0],q[1]} ; S={a,b} ; s[0]=e ; F={q[1]} ; r aus S* ; w aus T* R : rq[0]aw -> raq[0]w (1) rq[0]bw -> rbq[0]w (2) rq[0]cw -> rq[1]w (3) raq[1]aw -> rq[1]w (4) rbq[1]bw -> rq[1]w (5) Um die Arbeitsweise von A zu illustrieren, soll der Kellerautomat auf die Folge abbcbba angewendet werden : Zustand │ Eingabe │ Keller │ Übergang │ ───────────────┼───────────────┼────────────────┼───────────────┼─ q[0] │ abbcbba │ e │ - │ q[0] │ bbcbba │ a │ 1 │ q[0] │ bcbba │ ba │ 2 │ q[0] │ cbba │ bba │ 2 │ q[1] │ bba │ bba │ 3 │ q[1] │ ba │ ba │ 5 │ q[1] │ a │ a │ 5 │ q[1] │ e │ e │ 4 │ Das Wort abbcbba gehört also zur oben definierten Sprache L. So- weit nun zu Kellerautomaten. Was, fragt sich der aufmerksame Le- ser, haben nun Kellerautomaten mit kontextfreien Grammatiken zu tun? Ganz einfach: es existiert ein Satz, der besagt, daß es zu jeder kontextfreien Grammatik einen Kellerautomaten A gibt mit L(A)=L(G). So weit, so gut. Danach ist es relativ einfach, einen passenden Parser für die zugehörige Grammatik zu finden. In unse- rem Fall bedeutet das : Man nimmt die Pascal-Grammatik her, konstruiert daraus einen Kel- lerautomaten und schaut dann nach, ob der Kellerautomat das ein- gegebene Programm akzeptiert oder nicht, das heißt, ob die Syntax korrekt oder fehlerhaft ist. Einen kleinen Haken gibt es aller- dings bei der ganzen Sache. Effizientes Parsing setzt einen de- terministischen Kellerautomaten voraus, und deterministische Kel- lerautomaten existieren nur für Unterklassen von kontextfreien Grammatiken. Wir werden später noch erkennen müssen, daß Stan- dard-Pascal zu allem Übel - wie könnte es auch anders sein - in einigen Fällen nicht uneingeschränkt den Anforderungen dieser speziellen Unterklassen genügt. Nun, wir werden uns trotzdem ei- nen deterministischen Kellerautomaten für unsere Grammatik hin- biegen. Doch dazu müssen wir und erst einmal etwas näher mit den unterschiedlichen Zerteilungsverfahren beschäftigen. Zerteilungsverfahren Grundsätzlich gibt es zwei Arten von Zerteilungsverfahren. Zum einen ist da die zielbezogene Zerteilung ( LL(k)-Zerteilung mit k>0 ) und zum anderen die quellbezogene Zerteilung ( LR(k)-Zerteilung mit k>0 ) zu nennen. Die quellbezogene Zerteilung ( Bottom-up-Analyse ) verfolgt den Ableitungsbaum von der Blättern zur Wurzel ( Quelle ). Das dabei verwendete Konzept ist zwar mächtiger als die zielbezogene Zer- teilung, jedoch benötigt es zur Konstruktion auch ein wesentlich größeres theoretisches Basiswissen. Daher soll die Bottom-up- Analyse an dieser Stelle auch nur namentlich erwähnt bleiben, da deren vollständige Behandlung den Rahmen dieser Reihe gehörig sprengen würde. Wer sich einen tieferen Einblick in die LR(k)-Zerteilung verschaffen will, dem sei hier das Buch von M.A. Harrison, Introduction to formal language theory, Addison Wesley 1978, empfohlen. Im Gegensatz dazu wird bei der zielbezogenen Zerteilung ( Top- down- Analyse) versucht, den Ableitungsbaum von der Wurzel zu den Blättern (Ziel) aufzubauen. Diesem LL(1)-Verfahren werden wir uns im Folgenden eingehender zuwenden. Bevor die LL(1)-Analyse jedoch vollständig vorgestellt werden kann, müssen noch einige notwendi- ge Vorbetrachtungen zu den Anfängen von Wörtern w aus V gemacht werden. Der k-Anfang von w aus V*, - man schreibt das auch als k:w -, ist definiert als k:w := { w# , falls |w|<k x , falls w=xy und |x|=k } (|w| ist die Länge des Wortes w) Der k-Anfang ist also nichts anderes als der ganz normale Anfang eines Wortes, wobei die natürliche Zahl k die Länge dieses Anfan- ges angibt. Ein Beispiel soll das erläutern : Sei T={a, b, c} und w=abccb, dann sind z.B.: 1:w = a 3:w = abc 5:w = abccb 6:w = abccb# n:w = abccb# für alle n>=6 Weiterhin faßt man die Menge aller terminalen k-Anfänge von w aus V* zur Menge Anf[k](w) zusammen. Formal definiert sieht das wie folgt aus : Anf[k](w) := {x | es ex. ein v aus T* mit w=> *v und x=k:v } An dieser Stelle trifft man in der englischsprachigen Literatur meist auf den Begriff first[k](w) anstelle von Anf[k](w). Auch hier soll ein kleines Beispiel die Definition erläutern : Sei G=(T,N,P,Z) mit T={a, b, c} ; N={S, A, B ,C} ; Z=S und P: S -> A | B | C A -> bBa B -> aAa C -> cCc , dann ist Anf1 (S) = {a, b, c} Anf1(A) = {b} Anf1(B) = {a} .... Wie man sieht, lassen sich für kleinere Grammatiken die Mengen Anf[k](w) leicht zu Fuß berechnen. Erreichen Grammatiken dahinge- gen den Umfang von Programmiersprachen-Grammatiken, so wird eine der- artige Bestimmung der einzelnen Anfänge schon wegen des gro- ßen Arbeitsaufwandes im Keim erstickt werden. Glücklicherweise exi- stiert ein einfacher Algorithmus, mit dessen Hilfe die Be- stimmung der Anfänge auch automatisch durchgeführt werden kann. Da wir uns nur mit dem LL(1)-Verfahren beschäftigen, benötigen wir nur ein Verfahren, das alle 1-Anfänge berechnet. Diesen Algo- rithmus wollen wir uns hier zu Gemüte führen. Berechnung von Anf1(x) (gleich Anf(x)) Nach Definition ist # aus Anf(x) genau dann, wenn x=>*e (e ist das leere Wort). Zu Beginn wird die Menge der Anfänge wie folgt initialisiert : Anf(t) := {t} für alle t aus T Anf(X) := { } für alle X aus N. repeat for each X -> x1 x2...xn aus P do begin i:=1; weiter:=true; W:={ }; while (i<=n) and weiter do begin W:=W ++ (Anf(x1)--{#}); if # aus Anf(x1) then i:=i+1 else weiter:=false end; if weiter then W:=W ++ {#}; Anf(X):=Anf(X) ++ w end until alle Anf(X) unverändert Ein Beispiel soll diesen Algorithmus erläutern : Gegeben ist die folgende Grammatik G=(T,N,P,Z) mit : N={E,E1,T,T,P} T={a,b,c,(,),*} Z=E ist das Startsymbol Die zugehörigen Produktionen lauten : (1) E -> T E1 (2) E1 -> +E | e (3) T -> F T1 (4) T1 -> T | e (5) F -> P F1 (6) F1 -> * F1 | e (7) P -> (E) | a | b | c Wendet man nun jeweils auf die einzelnen Produktionen Schritt für Schritt den obigen Algorithmus an, so ergibt sich folgende Tabel- lenaufstellung für die einzelnen Nichterminale : │ Anf(x) │ Anf(x) │ ────┼───────────┼───────────┼── E │ Anf(T E1) │ (,a,b,c │ E1 │ +,# │ +,# │ T │ Anf(F T1) │ (,a,b,c │ T1 │ Anf(T),# │ (,a,b,c,# │ F │ Anf(P F1) │ (,a,b,c │ F1 │ *,# │ *,# │ P │ (,a,b,c │ (,a,b,c │ Zum besseren Verständnis der Tabelleneinträge betrachten wir nun die Produktion E -> T E1 etwas näher : E | Anwendung von Regel (3), es wird der | Anfang von T bestimmt. Anf(T E1) | Regel (3). Da Anf(T)=Anf(F) ist, wird im | nächsten Schritt Anf(F) ermittelt. Anf(F T1) | Regel (3) | Anf(P F1) | Regel (2). Erst hier wird eine Menge von | von Terminalen ermittelt. Da diese Menge { (,a,b,c) } nicht das leere Wort enthält, ist es nicht erforderlich, Anf(F1) zu bilden. Der Algorithmus endet an dieser Stelle. Somit ergibt sich für das Nichtterminal E : Anf[1](E) = { (,a,b,c } Ähnlich wie die terminalen k-Anfänge eines Wortes w aus V*, kann man auch die Menge der terminalen Zeichenreihen der Länge k, die auf w folgen können und mit Folge[k](w) (engl.follow[k](w)) be- zeichnet werden, definieren als : Folge[k](w) := { x | es ex. ein v aus T* und Z=> *uwv, wobei x=k:v } Auch die Folge[k](w)-Menge kann mit dem nachfolgenden Algorithmus automatisch generiert werden. Berechnung von Folge[1](x) (=Folge(x)) Zuerst werden die Mengen Folge(Z) und Folge(X) mit Folge(Z) = {#} und Folge(X) = { } für alle X aus N--{Z}, vorbesetzt. Der zur weiteren Berechnung der Folge-Mengen benötig- te Algorithmus lautet : repeat for each X -> uYv aus P do begin Folge(Y) := Folge(Y) ++ (Anf(v) -- {#}); if (v=e) or (# aus Anf(v)) then Folge(Y):=Folge(Y) ++ Folge(X) end until alle Folge(Y) unverändert; Zur Erklärung der Arbeitsweise dieses Verfahrens sei wieder die Grammatik G aus obigem Beispiel gewählt : │ Folge(x) │ Folge(x) ────┼────────────────────────────┼─────────── E │ #,),Folge(E1) │ #,) E1 │ Folge(E) │ #,) T │ Anf(E1),Folge(E),Folge(T1) │ +,#,) T1 │ Folge(T) │ +,#,) F │ Anf(T1),Folge(T1)=Folge(T) │ (,a,b,c,+,#,) F1 │ Folge(F) │ (,a,b,c,+,#,) P │ Anf(F1),Folge(F) │ *,(,a,b,c,+,#,) Betrachten wir zur Tabellenerläuterung die Berechnung von Fol- ge(T). Zunächst werden alle Regeln gesucht, in denen T auf der rechten Seite der Ableitungsregeln auftritt. Das trifft in diesem Fall auf die Produktionen (1) und (4) zu. Aus dem Verfahren er- gibt sich, daß im nächsten Schritt der Anfang des Teilwortes zu bestimmen ist, das auf T folgt. Für Regel (1) erhält man dabei die Menge M{1}={+,#} und für Regel (4) die Menge M{2}={ }. Eine Vereinigung der Menge M{1}--{#} mit M{2} liefert als Folge(T) die Menge {+}. Da # aus Anf(E1) ist, muß wegen Regel (1) noch Fol- ge(E) bestimmt werden. Auch in Regel (4) tritt kein N aus V nach T auf, weshalb hier noch Folge(T1) bestimmt werden muß. Daraus ergibt sich als Zwischenergebnis : Folge(T)={+,Folge(E),Folge(T1)} Nachdem der Algorithmus auf Folge(E) und Folge(T1) angewandt wur- de, erhält man : Folge(E) ={#,)} Folge(T1)={+,#,)} Damit ergibt sich für Folge(T) als Endergebnis : Folge(T) = {+,#,)} Soweit zu Anf[k](w) und Folge[k](w). Um das Ziel unserer Bemühun- gen nicht aus den Augen zu verlieren, sei es nochmals erwähnt: Wir sind auf der Suche nach einem deterministischen Kellerautoma- ten A mit L(A)=L(G). G ist unsere Standard-Pascal-Grammatik. Es gibt nun einen Satz, der besagt, daß genau dann ein deterministi- scher Kellerautomat existiert, wenn die zugehörige Grammatik LL(k) (in unserem Fall LL(1)) ist. Nun, was besagt dieses LL(1) eigentlich ? LL(1) bedeutet nichts anderes, als daß die Eingabe von links nach rechts gelesen wird, und dabei der zugehörige Ab- leitungsbaum ebenfalls von links nach rechts (Linksableitung) aufgebaut wird. In jedem Schritt darf hierbei nicht mehr als ein Zeichen aus der Eingabe zur Entscheidung beitragen (ein Zeichen Vorschau). Formal wird das so ausgedrückt : Eine kontextfreie Grammatik G=(T,N,P,Z) heißt LL(k)-Grammatik zu gegebenen k>0, wenn für je zwei Linksableitungen Z -> uAv -> uxv -> *uy Z -> uAv -> ux'v -> *uy' mit A aus N, v,x,x' aus V* und u,y,y' aus T* folgt : aus k:y=k:y' folgt : x=x', d.h. A -> x = A -> x'. Äquivalent gilt dann für jedes Produktionenpaar A -> x, A -> x' mit x<>x' : Anf[k] (x Folge [k](A))--Anf[k] (x' Folge[k] (A))={ }. Falls k=1 ist und keine Ableitung der Form S -> e (e= leeres Wort, S aus N) existiert, gilt weitere viel einfachere Aussage: Anf[1](x) und Anf[1](x') müssen disjunkt sein. Mit den so erarbeiteten Grundlagen ist es nun möglich, einen de- terministischen Kellerautomaten für eine LL(k)-Grammatik anzuge- ben. Die Zustände des Kellerautomaten entsprechen dabei Situatio- nen (items ) in der Bearbeitung von speziellen Produktionen der Grammatik. Eine Situation hat die folgende Gestalt : [X -> Y.Z] aus Q (Q ist Zustandsmenge des Kellerautomaten) Der Punkt in der Situation gibt die Analyseposition in der jewei- ligen Produktion an. ((X -> YZ) aus Produktionsmenge P der Gram- matik). Aufgabe ist es jetzt, die Zustandsmenge des Kellerautoma- ten aus den Produktionen der Grammatik zu gewinnen. Dazu defi- niert man als Startzustand q[0]:=[Z -> .S]. Der Keller ist zu Beginn leer (Kellervorbesetzung s[0] =e), Q:={q[0]}, R:={ } und F:={[Z -> S.]}. Für jeden Zustand q=[A ->X.Y] erweitern wir die Mengen des Kellerautomaten wie folgt: 1.) q=[A -> x.] : Erweitere R um : R:=R++{qe -> e} (entkellern) 2.) q=[A -> x.ay'] : Bilde neuen Zustand q'=[A -> xa.y'] und q' ist neuer Nachfolgezu- stand.Erweitere Q um : Q:=Q++{q'} und R um : R:=R++{qa -> q'} (a aus T). 3.) q=[A -> x.By'] : Bilde neuen Zustand q'=[A -> x'B.y'] und kellere ihn. Bilde für jede Produktion B -> Z[1],..,B -> Z[n] neue Zustände h[1] =[B->.Z[1]], .. ,h[n]=[B->.Z[n]]. Die Zustandsmenge des Kellerautomaten wird entsprechend um diese neuen Zustände erweitert : Q := Q ++ {h[1],..,h [n]} ++ {q'} und die Regelmenge R vergrößert sich um die Regeln : R:=R ++ {qw[1]->q'h[1]w[1] | w[1] aus W[1]} .. ++ .. ++ {qw [n] ->q'h[n]w[n] | w[n] aus W[n]} mit W[i]:=Anf(Z[i])für alle i aus {1,..,n} Abhängig vom nächsten Eingabezeichen x aus T, das in genau einer der Mengen W[i] liegen muß, wird h[i] neuer Nachfolgezustand im Automaten. Zur Veranschaulichung konstruieren wir einen deterministischen Kellerautomaten für eine LL(1)-Grammatik. Sei die Ausdrucksgram- matik G=(T,N,P,Z) gegeben mit T={i,+,(}, N={Z,A,A',F} und P : Z -> A A -> FA' A' -> +FA' A' -> e F -> i F -> (A) Für die Berechnung der W[i] aus 3) benötigen wir die 1-Anfänge, die mit dem vorgestellten Algorithmus nun leicht bestimmt werden können. Es ist │ Anf(x) │ Folge(x) ─────┼────────┼────────── Z │ i,( │ # A │ i,( │ #,) A' │ +,# │ #,) F │ i,( │ +,#,) Zum korrekten Nachweis der LL(1)-Eigenschaft überprüfen wir noch schnell, daß Anf(+FA' Folge(A'))={+} und Anf(e Folge(A'))={#,)} disjunkt sind={ }. Ein kleines Beispiel soll die Funktionstüchtigkeit des so erhal- tenen deterministischen Kellerautomaten zeigen : Keller │ Zustand │ Eingabe │ Linksableitung ───────────────────────────┼──────────┼──────────┼─────────────── / │ q[0] │ (i+i)# │ A q[1] │ q[2] │ (i+i)# │ FA' q[1],q[3] │ q[5] │ (i+i)# │ (A) q[1],q[3] │ q[6] │ i+i)# │ q[1],q[3],q[7] │ q[2] │ i+i)# │ FA' q[1],q[3],q[7],q[3] │ q[9] │ i+i)# │ i q[1],q[3],q[7],q[3] │ q[10] │ +i)# │ q[1],q[3],q[7] │ q[3] │ +i)# │ q[1],q[3],q[7],q[4] │ q[12] │ +i)# │ +FA' q[1],q[3],q[7],q[4] │ q[13] │ i)# │ q[1],q[3],q[7],q[4],q[14] │ q[9] │ i)# │ i q[1],q[3],q[7],q[4],q[14] │ q[10] │ )# │ q[1],q[3],q[7],q[4] │ q[14] │ )# │ q[1],q[3],q[7],q[4],q[15] │ q[11] │ )# │ e q[1],q[3],q[7],q[4] │ q[15] │ )# │ q[1],q[3],q[7] │ q[4] │ )# │ q[1],q[3] │ q[7] │ )# │ q[1],q[3] │ q[8] │ # │ q[1] │ q[3] │ # │ q[1],q[4] │ q[11] │ # │ e q[1] │ q[4] │ # │ / │ q[1] │ # │ Auch wenn es auf den ersten Blick nicht ersichtlich scheinen mag: das beschriebene Verfahren stellt eine ausgesprochen einfache Möglichkeit zur Erzeugung von Zerteilern dar. Die vorgestellte Methode wurde gegen Ende der 60'er Jahre von Lewis und Stearns entwofen und eingeführt. Viele Compilerbauer wählen aufgrund grö- ßerer Mächtigkeit heute andere Zerteilungsverfahren als die LL(1)-Zerteilung (LR(k), LALR(k), SLR(k) - Zerteilungen ). Um sich einen grundlegenden Einblick in den Compilerbau zu verschaf- fen, reicht das Verständnis der LL(1)-Analyse jedoch vollständig aus. Im übrigen hat das vorgestellte Verfahren den Vorteil, daß sich dazu Generatoren bauen lassen, die in der Lage sind, syntak- tische Informationen einer fast beliebigen Programmiersprache aufzunehmen und daraus die Implementierung des zugehörigen Par- sers automatisch zu erzeugen. Die Implementierung unseres Parsers ist jedoch nach guter alter Manier noch "von Hand gemacht". Implementierung von LL(1)-Zerteilern Auch wenn einigen Lesern bei der LL(1)-Theorie die Nackenhaare hochgegangen sein mögen, so zeigt sich spätestens bei der Imple- mentierung dieses Zerteilungsverfahrens einer seiner wesentlichen Vorteile : die verhältnismäßig einfache Programmierung. Die Spe- zifikation ist klar. Als Eingabe dient dem Parser die vom Scanner erhaltene Symbolfolge. Ausgegeben werden soll eine Folge von an- gewandten Produktionen, aus denen sich der zugehörige Ableitungs- baum konstruieren läßt. In der Ausprogrammierung tauchen dabei immer wieder 3 "Basisprozeduren" auf, die hier in Pascal-Notation erläutert werden sollen. var symbol: ... ; procedure lesen; begin gib_symbol_aus(symbol); symbol:=next_symbol end; procedure akzeptiere(t:symbolklasse); begin if symbol.klasse=t then lesen else fehlerbehandlung end; procedure gib_produktion_aus(p:produktion); begin ... end; Der zentrale Algorithmus - der eigentliche Kellerautomat - kann als tabellengesteuert mit den Regeln R als Übergangsmatrix QxT -> Q programmiert werden. Diese Darstellungsweise kommt dem altbe- kannten deterministisch endlichen Automaten sehr nahe und besitzt den Vorteil der schnellen Ausführbarkeit. Eine andere Variante bietet hinsichtlich Geschwindigkeit zwar einige Nachteile, spiegelt aber wesentlich stärker die Struktur der zu implementierenden Programmiersprache wider. Die Rede ist vom Rekursiven Abstieg (recursiv descent) . Bei diesem Verfahren wird jedem A aus N eine rekursive Prozedur zugeordnet. Die Zu- stände des deterministischen Kellerautomaten entsprechen dann Programmstellen in der Implementierung. Der Stack braucht nicht explizit programmiert zu werden, sondern baut sich durch die Auf- rufe der einzelnen Prozeduren von selbst auf (Laufzeitkeller). Die Implementierung unserer Ausdrucksgrammatik soll dieses Prin- zip verdeutlichen : program Z; procedure A; begin gib_produktion_aus( {A -> FA'} ); F; A' end; procedure F; begin if symbol.klasse in ['i','('] then case symbol.klasse of 'i' : begin gib_produktion_aus( {F -> i} ); lesen; end; '(' : begin gib_produktion_aus( {F -> (A) }; lesen; A; akzeptiere(')') end; end else fehlerbehandlung end; procedure A'; begin if symbol.klasse in ['#','+'] then case symbol.klasse of '#' : gib_produktion_aus( {A' -> e} ); '+' : begin gib_produktion_aus( {A' -> +FA'} ); lesen; F; A' end end else fehlerbehandlung end; begin gib_produktion_aus( {Z -> A} ); A; akzeptiere('#') end. So. Nachdem wir uns nun mit viel Erfolg durch Theorie und Praxis des Parsers gekämpft haben, werden wir das in der nächsten Folge fortsetzen und uns dann mit der "semantische Analyse" beschäfti- gen. Dieses wird dann das letzte Kapitel zum Analyse-Teil sein. Danach werden auch die Fans von Programmauszügen auf ihre Kosten kommen, da der Quelltext des Compilers als Leitfaden den Synthe- se-Teil durchziehen wird.