Zur Haupt­na­vi­ga­ti­on sprin­gen [Alt]+[0] Zum Sei­ten­in­halt sprin­gen [Alt]+[1]

An­wen­dun­gen und Bei­spie­le (BP: Items 1, 15)

Klassengruß als Sequenzdiagramm

Ab­bil­dung 9: Klas­sen­gruß als Se­quenz­dia­gramm ZPG In­for­ma­tik [CC BY-SA 4.0 DE], aus zpg_­spra­chen­au­to­ma­ten_hin­ter­grund.odt

Bei­spiel: Mor­gend­li­cher Gruß als Mealy-Au­to­mat

Zu­min­dest in der Un­ter­stu­fe gibt es an vie­len Schu­len ein Be­grü­ßung­ri­tu­al: Die Leh­re­rin be­tritt den Raum und war­tet bis alle ste­hen; die Schü­ler er­he­ben sich, war­ten auf ihren Gruß und er­wi­dern ihn; die Leh­re­rin sagt „Setzt euch“ und die Klas­se setzt sich.

Wenn man die ein­zel­nen Ak­tio­nen als „Nach­richten“ zwi­schen den Be­tei­lig­ten ver­steht, sieht die­ses sehr ein­fa­che Pro­to­koll im Se­quenz­dia­gramm so aus wie in Abbil­dung 9.

Wäh­rend das Se­quenz­dia­gramm den Nach­rich­ten­aus­tausch in den Mit­tel­punkt stellt, durch­laufen auch die Teil­neh­mer selbst wäh­rend des Pro­to­kolls be­stimm­te Pha­sen, die sich als Zustän­de eines Au­to­ma­ten dar­stel­len las­sen; beim Ein­tref­fen einer „Nach­richt“ wech­selt der Auto­mat den Zu­stand. Mit Mealy-Au­to­ma­ten kann man so model­lieren, dass die Aus­ga­ben des einen Au­to­ma­ten als Nach­rich­ten an den an­de­ren gehen, der sie dann als Ein­ga­ben ver­ar­bei­tet.

Ab­bil­dung 10 zeigt einen Mealy-Auto- maten für die Rolle der Klas­se beim mor­gend­li­chen Be­grü­ßen; die Aktio- nen der Leh­re­rin sind die Ein­ga­ben für die­sen „Schü­ler­au­to­ma­ten“. Ein ähn- li­cher Au­to­mat kann um­ge­kehrt die Ak­tio­nen und Re­ak­tio­nen der Leh­re­rin be­schrei­ben.

 Mealy-Automat für die Rolle der Klasse im Grußprotokoll

Ab­bil­dung 10: Mealy-Au­to­mat für die Rolle der Klas­se im "Gruß­pro­to­koll". Jede Tran­si­ti­on ent­hält links die Ein-, rechts die Aus­ga­be. ZPG In­for­ma­tik [CC BY-SA 4.0 DE], aus zpg_­spra­chen­au­to­ma­ten_hin­ter­grund.odt

Üb­ri­gens gibt es für die Er­stel­lung von Se­quenz­dia­gram­men na­tür­lich Werk­zeu­ge; Ab­bil­dung 9 wurde bei­spiels­wei­se von dem Ge­ne­ra­tor auf der Seite https://​seq​uenc​edia​gram.​org/ aus fol­gen­der Be­schrei­bung er­zeugt:

title Klassengruß
Lehrerin->Klasse: betritt den Raum
Lehrerin->Klasse: wartet, bis alle stehen
activate Klasse
Lehrerin -> Klasse: "Guten Morgen, liebe 5B!"
Klasse->Lehrerin: "Guten Morgen, Frau Klug!"
Lehrerin -> Klasse: "Setzt euch, wir fangen an..."
deactivate Klasse

Auch hier kommt üb­ri­gens eine Spe­zi­al­spra­che (zur Be­schrei­bung von Se­quenz­dia­gram­men) zum Ein­satz, die von ent­spre­chen­den Werk­zeu­gen ge­le­sen, über­prüft und in­ter­pre­tiert wird.

Bei­spiel: Ver­ein­fach­tes TCP als Mealy-Au­to­mat

TCP (stark vereinfacht) mit Verbindungsaufbau und Datenaus­tausch, aber ohne Verbindungs­abbau.

Ab­bil­dung 11: TCP (stark ver­ein­facht) mit Ver­bin­dungs­auf­bau und Datenaus­tausch, aber ohne Verbindungs­abbau. ZPG In­for­ma­tik [CC BY-SA 4.0 DE], aus zpg_­spra­chen­au­to­ma­ten_hin­ter­grund.odt

Als grö­ße­res Bei­spiel zeigt Ab­bil­dung 11 sehr stark ver­ein- facht den Ver­bin­dungs­auf­bau („Hand­shake“) und Da­ten­aus- tausch einer TCP-Ver­bin­dung. Der Hand­shake be­inhal­tet den Aus­tausch und die ge­gen­sei­ti­ge Be­stä­ti­gung von zu­fäl­li­gen Se­quenz­num­mern (hier ab 174 für Da­ten­pa­ke­te vom Cli­ent zum Ser­ver und 309 für die Ge­gen­rich­tung). Wäh­rend der Aus­tausch­pha­se wer­den die Da­ten­pa­ke­te durch­num­me­riert; nach Ein­gang be­stä­tigt der Emp­fän­ger sie („ACK­now­ledge“) und nennt dabei die Se­quenz­num­mer. Bleibt eine Be­stä­ti- gung aus, muss der Ab­sen­der das Paket er­neut schi­cken oder (nach ei­ni­gen Fehl­ver­su­chen) an­neh­men, dass die Ver­bin­dung ab­ge­ris­sen ist.

Der Ver­bin­dungs­ab­bau, der eben­falls zu TCP ge­hört, ist hier nicht dar­ge­stellt.

Die Soft­ware, die eine Seite eines sol­chen Pro­to­kolls durch- führt, heißt üb­li­cher­wei­se Trei­ber.

Auch in die­sem Bei­spiel las­sen sich die TCP-Trei­ber von Ser­ver und Cli­ent als Mealy-Au­to­mat dar­stel­len. Zwar kann ein end­li­cher Au­to­mat im en­ge­ren Sinne nicht un­be­grenzt Se­quenz­num­mern hoch­zäh­len; den­noch ist die Vor­stel­lung, dass Pro­to­koll­trei­ber „Zu­stän­de“ haben, zwi­schen denen sie bei be­stimm­ten Er­eig­nis­sen wech­seln, ein hilf­rei­ches Mo­dell für eine struk­tu­rier­te Im­ple­men­tie­rung.

Ab­bil­dung 12 skiz­ziert einen Au­to­ma­ten für die­sen Trei­ber: Der obere Pfad wird durch­lau­fen, wenn der Trei­ber selbst den Ver­bin­dungs­auf­bau in­iti­iert; der un­te­re, wenn von außen eine Ver­bin­dungs­an­fra­ge ein­geht. Nach­dem die Ver­bin­dung auf­ge­baut und die Se­quenz­num­mern ver­ein­bart sind (SeqIn für ein­ge­hen­de, Se­qOut für aus­ge­hen­de Da­ten­pa­ke­te), kann der Trei­ber Daten so­wohl ver­schi­cken als auch emp­fan­gen; nach jedem emp­fan­ge­nen bzw. ver­schick­ten Paket wird die je­wei­li­ge Se­quenz­num­mer er­höht. Be­kommt der Trei­ber für ein ge­sen­de­tes Paket keine Quit­tung, wech­selt er von q6 nach q7; nach dem zwei­ten Fehl­ver­such (auch in q7 wie­der ein Time­out) be­trach­tet er die Ver­bin­dung als ab­ge­ris­sen und wech­selt ganz zu­rück nach q0.

TCP-Treiber (stark vereinfacht) als Mealy-Automat.

Ab­bil­dung 12: TCP-Trei­ber (stark ver­ein­facht) als Mealy-Au­to­mat. ZPG In­for­ma­tik [CC BY-SA 4.0 DE], aus zpg_­spra­chen­au­to­ma­ten_hin­ter­grund.odt

Der Ab­lauf ist hier aus di­dak­ti­schen Grün­den sehr stark ver­ein­facht: Er ent­hält bei­spiels­wei­se kei­nen Ver­bin­dungs­ab­bau, igno­riert Stö­run­gen des Ver­bin­dungs­auf­baus sowie Pa­ke­te, die in fal­scher Rei­hen­fol­ge an­kom­men, ver­wen­det die Se­quenz­num­mern an­ders als „rich­ti­ges“ TCP dast tut, und vie­les mehr.

An­wen­dung: Au­to­ma­ten für Scan­ner, Par­ser und Com­pi­ler

Die Com­pi­lie­rung eines Pro­gramms ist ein kom­ple­xer Vor­gang, der mehr­fach Ge­brauch von for­ma­len Spra­chen und ent­spre­chen­den Werk­zeu­gen macht.

Ein Java-Schnip­sel wie...

1 for (int wert; wert <= 5; wert ++) {
2   if(zahl % 17 == 0) {
3     System.out.println(„durch 17 teilbar:“ + k);
4    }
5 }
wird dabei für die le­xi­ka­li­sche Ana­ly­se zu­nächst von einem so­ge­nann­ten Scan­ner (auch „Lexer“ ge­nannt) ge­le­sen. Der fasst die Ein­ga­be zu­nächst als Zei­chen­strom auf...

Tabelle

... und ver­sucht darin Be­deu­tungs­ein­hei­ten, so­ge­nann­te To­kens, der be­tref­fen­den Pro­gram­mier­spra­che zu fin­den. Das Er­geb­nis ist ein To­ken­stream:

Tabelle

Im To­ken­stream kom­men nur noch Ele­men­te vor, die syn­tak­tisch be­deut­sam sind; Leer­zei­chen, Zei­len­um­brü­che und Kom­men­ta­re tra­gen keine Be­deu­tung und feh­len daher.

Die Buch­sta­ben­fol­ge i n t wurde vom Scan­ner als Java-Schlüs­sel­wort er­kannt und zu einem INT-Token zu­sam­men­ge­fasst. Das ist zwar nicht tri­vi­al, weil er die Zei­chen­ket­te i n t e r n na­tür­lich nicht als INT-Token ein­stu­fen, son­dern als „Iden­ti­fier“ er­ken­nen und dar­aus ein ID- Token er­zeu­gen müss­te. Den­noch kann die le­xi­ka­li­sche Ana­ly­se von DEAs er­le­digt wer­den. Die Spra­che der in Java er­laub­ten To­kens ist also re­gu­lär. Passt eine Zei­chen­fol­ge zu kei­nem Token, mel­det der Scan­ner einen le­xi­ka­li­schen Feh­ler.

Teilhierarchie der Java-Syntax (von oben nach unten im Sinne von

Ab­bil­dung 13: Teil­hier­ar­chie der Java-Syn­tax (von oben nach unten im Sinne von "Klas­se ent­hält Me­tho­de", „Me­tho­de ent­hält An­wei­sung“ usw.) ZPG In­for­ma­tik [CC BY-SA 4.0 DE], aus zpg_­spra­chen­au­to­ma­ten_hin­ter­grund.odt

Der To­ken­stream ist ein Zwi­schen­pro­dukt und dient an­schlie­ßend als Ein­ga­be für den so­ge­nann­ten Par­ser, der die syn­tak­ti­sche Ana­ly­se des Pro­gramms durch­führt, also seine Struk­tur prüft. Ein Feh­ler auf die­ser Ebene heißt dem­entspre­chend syn­tak­ti­scher Feh­ler. Wie zuvor erläu­tert, ist wegen der Klam­me­rungs­ebe­nen dafür min­des­tens ein Kel­ler­au­to­mat er­for­der­lich, bei den meis­ten Program­mier­sprachen dar­über hin­aus zu­sätz­li­che Hilfs­mit­tel wie z.B. eine Sym­bol­ta­bel­le (als Ver­zeich­nis schon deklarier­ter Va­ria­blen, Funk­tio­nen usw.). Das Er­geb­nis die­ser Phase ist oft ein Syn­tax­baum, der die Hier­ar­chie des Pro­gramms wie­der­gibt. In die­sem Baum be­steht z.B. das Pro­gramm aus Klas­sen, die Klas­sen aus At­tri­bu­ten und Me­tho­den, die Me­tho­den aus Kopf und Rumpf, ein Me­tho­den­rumpf aus An­wei­sun­gen usw.

An­schlie­ßend (in vie­len Com­pi­lern auch schon gleich­zei­tig mit dem Par­sing) wird als Aus­ga­be na­tür­lich noch das com­pi­lier­te, lauf­fä­hi­ge Pro­gramm er­zeugt.

Durch die Theo­rie der for­ma­len Spra­chen und der zu­ge­hö­ri­gen Au­to­ma­ten hat sich das Er­stel­len von Com­pi­lern dras­tisch ver­ein­facht. Der erste FOR­TRAN-Com­pi­ler wurde in den 50er Jah­ren noch voll­stän­dig von Hand pro­gram­miert, was einen Auf­wand von 18 Man­n­jah­ren(!) ver­ur­sacht haben soll26 . Die Er­stel­lung des Scan­ners hin­ge­gen er­le­digt heute ein Ge­ne­ra­tor: Die Ent­wick­le- rin muss nur noch die To­kens mit re­gu­lä­ren Aus­drü­cken be­schrei­ben – der zu­ge­hö­ri­ge NEA wird au­to­ma­tisch er­zeugt, in einen DEA um­ge­wan­delt und mi­ni­miert. An­schlie­ßend er­zeugt der Ge­ne­ra­tor sogar noch ein Pro­gramm, das die le­xi­ka­li­sche Ana­ly­se durch­führt. Mit etwas Übung baut man damit den Scan­ner für eine nicht allzu kom­pli­zier­te Pro­gram­mier­spra­che in­ner­halb we­ni­ger Stun­den oder Tage. Der Par­ser (der auf einem Kel­ler­au­to­mat ba­siert) wird auf ähn­li­che Weise aus einer Gram­ma­tik er­zeugt, die die Struk­tur der zu com­pi­lie­ren­den Spra­che be­schreibt. Zwar er­ge­ben Scan­ner und Par­ser noch kei­nen voll­stän­di­gen Com­pi­ler; trotz­dem lässt sich der Ge­winn durch Über­sicht­lich­keit, Fle­xi­bi­li­tät und Zeit­er­spar­nis gar nicht hoch genug ein­schät­zen!

Scan­ner- und Par­ser­ge­ne­ra­to­ren wur­den vor allem da­durch mög­lich, dass die Theo­rie der for­ma­len Spra­chen und ihrer Au­to­ma­ten so gründ­lich ver­stan­den ist. Diese Hilfs­mit­tel und etwas Di­dak­tik er­lau­ben es sogar, klei­ne Com­pi­ler bin­nen ei­ni­ger Un­ter­richts­wo­chen im Un­ter­richt von Schü­lern er­stel­len zu las­sen (zu­min­dest im Leis­tungs­fach).

Hier zei­gen sich zwei Ei­gen­hei­ten der In­for­ma­tik, die der Un­ter­richt bei sol­chen Ge­le­gen­heit auch gerne her­vor­he­ben darf:

  • Ers­tens geht In­for­ma­tik recht ein­falls­reich mit Spra­che um: In­for­ma­ti­ke­rin­nen be­nut­zen näm­lich Spra­che nicht nur, um damit an­spruchs­vol­le Ideen aus­zu­drü­cken – wir sind viel krea­ti­ver und er­fin­den sogar bei Be­darf Spe­zi­al­spra­chen, die wir auf be­stimm­te Zwe­cke pass­ge­nau zu­schnei­den. Wel­che An­glis­tin, wel­cher Phi­lo­lo­ge hat das je­mals getan? Java, As­sem­bler, SQL, XML und HTML sind Bei­spie­le künst­li­cher Spra­chen, die alle be­son­de­re Ei­gen­schaf­ten haben und sich für ihren spe­zi­el­len Zweck je­weils be­son­ders gut eig­nen. Der In­for­ma­tik­un­ter­richt be­han­delt ei­ni­ge sol­che Spra­chen, und tat­säch­lich be­zeich­net in der In­for­ma­tik sogar fast jede Ab­kür­zung auf -L ir­gend­was mit „lan­gua­ge“. Tech­ni­ken wie re­gu­lä­re Aus­drü­cke und Gram­ma­ti­ken die­nen gar als Meta-Spra­chen für die Be­schrei­bung eben die­ser Spra­chen – wo sonst außer in der In­for­ma­tik ler­nen Schü­le­rin­nen so etwas ken­nen?
  • Zwei­tens ist es vor allem sehr gut ver­stan­de­ne Theo­rie, die die er­wähn­ten Ge­ne­ra­to­ren mit ihren un­ge­heu­ren prak­ti­schen Aus­wir­kun­gen mög­lich macht. Hier be­wahr­hei­tet sich mal wie­der das Bon­mot

Nichts ist so prak­tisch wie eine gute Theo­rie.

 

26 Quel­le: http://​web.​cs.​wpi.​edu/~kal/com­p409/over­view.html

 

Hin­ter­grund­in­for­ma­tio­nen: Her­un­ter­la­den [odt][669 KB]

 

Wei­ter zu Ma­te­ria­li­en