Formale Sprachen Teil 3 Klaus Becker 2006. 2 Syntax und Semantik

Formale SprachenTeil 3

Klaus Becker

2 Syntax und Semantik

3 Teil 1

Mini-Programmiersprache

4 Zielsetzung

Ziel ist es, für eine einfache Programmiersprache einen Interpreter und einen Compiler zu entwickeln. Die hier betrachtete Programmiersprache orientiert sich an der Sprache zur Steuerung des Roboters Karol.

hinlegenschrittwiederhole solange NichtIstZiegel wiederhole solange NichtIstWand schritt *wiederhole linksDrehen*wiederhole

5 Die Programmiersprache

Zur Vereinfachung der Darstellung verwenden wir abkürzende Bezeichner für die Anweisungen der Programmiersprache.

hswh nz wh nw s *wh l*wh

6 Die Programmiersprache MyKa

Elementare Anweisungen:h „Ziegel hinlegen“a „Ziegel aufheben“s „Schritt vorwärts“l „links drehen“r „rechts drehen“

hswh nz wh nw s *wh l*whElementare Bedingungen:

nz „nicht auf Ziegel“nw „nicht vor Wand“

Kontrollanweisung:wh ... ... „wiederhole solange ...“ *wh

Ein MyKa-Programm setzt sich – wie im Beispiel gezeigt – aus elementaren und Kontrollanweisungen zusammen. Bei der Darstellung von MyKa-Programmen dürfen mehrere Anweisungen in eine Zeile geschrieben werden, ...

7 Zweistufige Sprachbeschreibung

Zeichen:Zeichen:

{h, a, s, l, r, nz, nw, wh, *wh}

{h s wh nz wh nw s *wh l *wh , ...}

Sätze / Tokenfolgen:Sätze / Tokenfolgen:

Wörter / Token:Wörter / Token:

{ASCII: a, b, c, ..., ´*´, ´ ´, chr(13), chr(10), ...}

Festlegung der korrekten Token (Wörter)

Festlegung der korrekten Tokenfolgen (Sätze)

Oft ist es sinnvoll, eine formale Sprache zweistufig festzulegen:

Zeilenumbruch

Alphabet für Token

Alphabet für Programme

Sprache der Token

Sprache der Programme

8 Eine Grammatik für MyKa

! Terminalsymbole

S = sL = lR = rH = hA = aNW = n wNZ = n zWHA = w hWHE = '*' w h

"Start Symbol" = <Programm>

! Produktionen <Programm> ::= <Anweisungsfolge><Anweisungsfolge> ::= <Anweisung> <Anweisungsfolge> ::= <Anweisung> <Anweisungsfolge><Bedingung> ::= NW<Bedingung> ::= NZ<Anweisung> ::= S<Anweisung> ::= L<Anweisung> ::= R<Anweisung> ::= H<Anweisung> ::= A<Anweisung> ::= WHA <Bedingung> <Anweisungsfolge> WHE

MyKa1.grm

9 Aufgabe

Starten Sie das Werkzeug „GOLD Parser Builder“ und laden Sie die Datei „MyKa1.grm“. Testen Sie die hier vorgegebene Grammatik zur präzisen Festlegung der Programmiersprache MyKa.

10 Es fehlt die Semantik

Bisher wurde nur die Syntax der Sprache MyKa festgelegt. Die Bedeutung der einzelnen Sprachelemente scheint klar zu sein. Aber ist das wirklich so? Bereits bei der elementaren Anweisung „h“ ist nicht klar, wie viele Ziegel hingelegt werde, ob der / die Ziegel in die Zelle, in der sich der Roboter befindet, gelegt werden, oder in die vor dem Roboter usw. .

Ziel ist es im Folgenden, auch die Semantik der Programmiersprache exakt zu beschreiben. Zwei Ansätze sollen hierzu vorgestellt werden: Zum einen soll die Bedeutung der Konstrukte der Sprache MyKa durch das Verhalten eines Interpreters festgelegt werden (Interpreteransatz). Zum anderen soll die Bedeutung von Konstrukten der Sprache MyKa auf die Bedeutung der Konstrukte einer anderen (bereits bekannten) Sprache zurückgeführt werden (Übersetzeransatz).

Letztlich werden hier somit ein Interpreter und ein Übersetzer (Compiler) für die Programmiersprache MyKa entwickelt. Zur syntaktischen Vorbereitung werden zudem ein Scanner und ein Parser für diese Sprache benutzt.

11 Teil 2

Scanner und Parser

12 Syntaxanalyse

Zur Analyse der Syntax der Sprache MyKa sollen im Folgenden ein Scanner und ein Parser entwickelt werden. Nach der Syntaxanalyse soll feststehen, ob eine vorgegebene Zeichenfolge ein syntaktisch korrektes MyKa-Programm darstellt.

13 Scanner

Aufgabe eines Scanners ist es, aus einer Zeichenfolge lexikalische Einheiten zu bilden und diese als Tokenfolge aufzubereiten.

Scanner

h s wh nz wh nw s *wh l *wh

Scanner-Automat

14 Scanner-Automat

´ ´; chr(13)

´ ´; chr(13); chr(10)

s; l; r; h; a

Fehlerzustand

Der Scanner benutzt einen endlichen Automaten zur Erkennung der lexikalischen Einheiten.

Immer dann, wenn der Endzustand erreicht wird, ist ein Token erkannt. Danach beginnt der Scanner seine Arbeit wieder im Anfangszustand.

15 Parser

Aufgabe eines Parsers ist es, eine Tokenfolge auf syntaktische Korrektheit zu analysieren (und evtl. die Tokenfolge geeignet aufzubereiten).

Parser

Parser-Automat

16 Parser-Automat

any / s : any / l :any / r : any / h :any / a :

wh / *wh : pop

any / wh : push wh

Der Parser benutzt einen Kellerautomaten zur syntaktischen Analyse der Tokenfolge.

any / nz : any / nw :

else / *wh : any / nz :any / nw :

any / wh :any / *wh :

Fehlerzustand

Oberstes Kellerzeichen /

Eingabezeichen: Kelleroperation

Der Kellerautomaten akzeptiert eine Zeichenfolge, wenn der Automat nach Abarbeitung der Zeichenfolge im Enzustand ist und wenn zudem der Keller leer ist.

17 Aufgabe

Testen Sie den implementierten Scanner.

Schauen Sie sich die Implementierung an.

Berücksichtigen Sie beim Scanner-Automaten zusätzlich folgende Kontrollanweisung:

if <Bed.> th <Anw.> el <Anw.> *if

Ergänzen Sie die Implementierung des Scanner-Automaten entsprechend und testen Sie den erweiterten Scanner.

18 Aufgabe

Testen Sie den implementierten Parser.

Berücksichtigen Sie beim Parser-Automaten zusätzlich folgende Kontrollanweisung:

Ergänzen Sie die Implementierung des Parser-Automaten entsprechend und testen Sie den erweiterten Parser.

19 Teil 3

Ein Programm-Interpreter

20 Interpreter

Ein Interpreter führt die Anweisungen Schritt für Schritt aus. Er beschreibt damit das Verhalten der jeweiligen Anweisungen.

Eine präzise Interpreter-beschreibung kann somit zur Festlegung der Semantik der Elemente der Programmier-sprache benutzt werden (Interpreter-Semantik).

Zustand vorher: abzuarbeitendes Programm;

Roboterwelt

Zustand nachher: abzuarbeitendes Programm;

Roboterwelt

21 Ausführungstransformationen

s wh nz wh nw s *wh l *wh

wh nz wh nw s *wh l *wh

wh nw s *wh l wh nz wh nw s ...

s wh nw s *wh l wh nz wh nw s ...

l wh nz wh nw s *wh l *wh

falsch

24 Transformationsregeln

Vor der Wand

Anzahl: n

Anzahl: n+1

<K> wh <K> *wh ...

wh <K> *wh ...

falsch

wh <K> *wh ...

27 Semantikfestlegung mit Regeln

Solange d. Restprogramm-Stapel nicht leer ist

wende die zum obersten Stapelelement passende Transformationsregel an

Das Verhalten des Interpreters wird hier präzise mit Hilfe von Transformationsregeln festgelegt. Diese bilden somit die Grundlage für eine Implementierung des Interpreters.

28 Aufgabe

Testen Sie den implementierten Interpreter.

Entwerfen Sie Transformationsregeln, die die Ausführung der folgenden Kontrollanweisung beschreiben:

Ergänzen Sie die Implementierung des Interpreters entsprechend der Transformationsregeln.

29 Teil 4

Ein Programm-Übersetzer

30 Übersetzer

Ein Übersetzer transformiert Programme der Ausgangs-Programmiersprache (Quellsprache) in eine andere Sprache (Zielsprache).

Eine präzise Übersetzer-beschreibung kann zur Festlegung der Semantik der Elemente der Ausgangs-Programmiersprache benutzt werden, sofern die Semantik der Zielsprache klar ist (Übersetzer-Semantik).

Zustand vorher: abzuarbeitendes Programm;

Roboterwelt

Zustand nachher: abzuarbeitendes Programm;

Roboterwelt

h s nz 10 nw 8 s 4 l 2

31 Von der Quell- zur Zielsprache

falsch

nz?wahr

falschnw?

h s nz 10 nw 8 s 4 l 2h s wh nz wh nw s *wh l *wh

h s wh nz wh nw

s *wh l *wh

Die Quellsprache MyKa verfügt über die Kontrollstruktur wh ... *wh zur Ausführung von Wiederholungen.

Die Zielsprache soll solche Wiederholungen durch GOTO-Sprünge ersetzen.

32 Von der Quell- zur Zielsprache

falsch

nz?wahr

falschnw?

0: h 1: s 2: nz? 3: f: goto 10 4: w: nw? 5: f: goto 8 6: w: s 7: goto 4 8: l 9: goto 210: stop

h s nz 10 nw 8 s 4 l 2

0: h 1: s 2: nz 3: 10 4: nw 5: 8 6: s 7: 4 8: l 9: 210:

h s wh nz wh nw

s *wh l *wh

h s nz 10 nw 8 s 4 l 20 1 2 3 4 5 6 7 8 9

GOTO-Programme werden in verkürzter Form als Folge von Token (siehe oben) dargestellt.

33 Übersetzungsvorgang im Detail

s wh nz wh nw s *wh l *wh

nz wh nw s *wh l *wh

wh nw s *wh l *wh

h s nz *

nz wh nw s *wh l *wh

s *wh l *wh

h s nz * nw *

nw s *wh l *wh

h s nz *

s *wh l *wh

h s nz * nw *

*wh l *wh

h s nz * nw * s

h s nz * nw 8 s 4

h s nz * nw 8 s 4 l

h s nz 10 nw 8 s 4 l 2

Solange die Quellcode-Schlange nicht leer ist

wende die passende Transformationsregel an

Das Verhalten des Übersetzers kann präzise mit Hilfe von Transformationsregeln festgelegt werden.

Diese bilden dann die Grundlage für eine Implementierung des Übersetzers.

Markenzähler

Hilfsstapel für Rücksprungmar

Quellcode

Zielcode

Regel für eine elementare Anweisung

Eine elementare Anweisung wird direkt in die Code-Schlange übernommen. Der Markenzähler wird um 1 erhöht.

Regel für die Wiederhole-Anweisung

wh ...

Die aktuelle Markennummer wird zur späteren Festlegung der Rücksprungadresse in einem Hilfsstapel zwischengespeichert.

Regel für die Wiederhole-Anweisung

... *

...

Die Bedingung wird in die Code-Schlange übernommen. Zusätzlich wird ein Platzhalter (hier *) übernommen, der später mit einer Marke für einen Vorwärtssprung ersetzt wird. Hiermit soll ein Sprung aus der Schleife ermöglicht werden, wenn die Bedingung nicht erfüllt ist. Des weiteren wird der Markenzähler um 2 erhöht. Hiermit soll ein Sprung zur ersten Anweisung innerhalb der Schleife ermöglicht werden, sofern die Bedingung erfüllt ist.

Regel für das Ende einer Wiederholung

... i+1 … k

*wh ...

... * …

Die auf einem Hilfsstapel abgelegte Rücksprungmarke wird in die Codeschlange übernommen. Zusätzlich wird das letzte * in der Codeschlange durch den neuen Markenzähler ersetzt. Hierdurch wird der Sprung „aus der Schleife“ realisiert.

42 Aufgabe

Testen Sie den implementierten Compiler.

Entwerfen Sie Transformationsregeln, die die Übersetzung der folgenden Kontrollanweisung beschreiben:

Ergänzen Sie die Implementierung des Compilers entsprechend der Transformationsregeln.

43 Teil 5

Aufgaben und Lösungsvorschläge

44 Aufgabe

Erweitern Sie die Programmiersprache um folgende Kontrollanweisung:

if <Bed.> t <Anw.> e <Anw.> *if

Ergänzen Sie entsprechend den Scanner, den Parser, den Interpreter und den Übersetzer (Codegenerator).

45 Die Programmiersprache

Zur Vereinfachung der Darstellung verwenden wir abkürzende Bezeichner für die Anweisungen der Programmiersprache.

wh nw if nz th h s el s *if*wh

46 Erweiterter Scanner-Automat

´ ´; chr(13)

´ ´; chr(13); chr(10)

s; l; r; h; a; t; e

Fehlerzustand

47 Erweiterter Parser-Automat

wh / *wh : popif / *if : pop

any / th : push thth / el : pop

any / wh : push wh

any / if : push if

any / nz : any / nw :

Fehlerzustand

Oberstes Kellerzeichen /

Eingabezeichen: Kelleroperation

else / *wh : any / nz :any / nw :

48 Zusätzliche Regeln f. d. Interpreter

<A1> ...

if th <A1> el <A2> *if ...

<A2> ...

falsch

if th <A1> el <A2> *if ...

49 Aufgabe

Beschreiben Sie die Arbeitsweise des Code-Interpreters mit Hilfe geeigneter Transformationsregeln. Ergänzen Sie hierzu den folgenden Lösungsvorschlag.

50 Lösungsvorschlag

... >s ...i

... s >...i+1

51 Lösungsvorschlag

52 Literaturhinweise

A. Hermes, D. Stobbe: Informatik Zwei, Klett-Verlag 1990.

E. Modrow: Automaten, Schaltwerke, Sprachen. Dümmlers-Verlag 1988.

E. Modrow: Theoretische Informatik mit Delphi. Emu-online 2005.

Formale Sprachen Teil 3 Klaus Becker 2006. 2 Syntax und Semantik

Documents

SMART Systems (Vorlesung: KI & XPS) zBeim vorigen Mal: yALCQHI R+, Syntax, Semantik, Anwendung (Pragmatik) zInhalt heute: yRDFS, Vertiefung der Anwendung

Einführung in die allgemeine Sprachwissenschaft Ringvorlesung Phonetik-Phonologie: B. Andreeva (BA) Morphologie-Syntax: T. Augustinova (TA) Semantik: W

Syntax und Semantik der Konnektoren Ein Überblick Hardarik ... · und Semantik der Konnektoren anhand des Deutschen. Das erste Kapitel behan-delt die verschiedenen morphosyntaktischen

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 5 / 1 Syntax und Semantik Die Syntax einer formalen Sprache kann als eine

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 6 / 1 Kapitel 6 Kongruenzen Definition "Kongruenzrelation" Eine -Kongruenz

Syntax Funktionale Kategorien I -- TP · 2009. 6. 16. · Funktionale Kategorien I – TP Modul 04-006-1003 Syntax und Semantik Institut f¨ur Linguistik Universit¨at Leipzig

Syntax versus Semantik - Text und seine Bedeutung · Kapitel1 Syntaxversus Semantik 1.1 WasistSyntax?J Syntax natürlicherSprachen Syntaxvon Programmiersprachen SyntaxlogischerSprachen

Morphologie und Syntax (BA) - Syntax und Semantik ... · 2 / 53 Morphologie und Syntax (BA) Gliederung 1 Übungsaufgabe 9 2 Argumentstruktur 3 Argumentstruktur und syntaktische Struktur

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 4 -Beispiele / 1 Beispiele für Ausdrucksalgebren 1. A = [ AUS ; neg, con,

Eine formale Beschreibung der dynamischen Semantik von … · 2019. 12. 4. · Software-Entwicklungsmethoden definiert unter anderem eine dynamische Semantik (OMG 2014, S. 103-109)

Soziolinguistik. Sprachliche Varietätenweb.vu.lt/flf/d.katinas/files/2013/09/Soziolinguistik.-Varietäten.pdf · –systematische Vereinfachungen in Morphologie, Syntax, Lexik, Semantik

Semantic Web Grundlagen - OWL 2 Syntax und Semantik · Semantic Web Grundlagen Birte Glimm Institut für Künstliche Intelligenz j24. Nov 2011 OWL 2 – Syntax und Semantik Foliensatz

Sprachverarbeitende Systeme - techfak.uni-bielefeld.de file12. Vorlesung Methoden der K nstlichen Intelligenz 9 Universit−t Bielefeld Syntax, Semantik, Pragmatik u Syntax strukturelle

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 13 / 1 Kapitel 13 Finale Semantik und beobachtbares Verhalten Das Ziel der

Lehrbuch der lateinischen Syntax und Semantik · Thorsten Burkard und Markus Schauer Lehrbuch der lateinischen Syntax und Semantik Begründet von Hermann Menge

Syntax („Lehre vom Satzbau“) - file3 Syntax von Programmiersprachen Syntax („Lehre vom Satzbau“) æ formale Beschreibung des Aufbaus der „Worte“ und „Sätze“, die zu

zur Infoveranstaltung Master Deutsch als Fremdsprache · Methodik/ Didaktik • Syntax • Morphologie • Semantik • Phonologie/Phonetik • Vermittlung ... SE Wortschatzerwerb

Einfuhrung in die formale Semantik - Dirk Kindermanndirkkindermann.com/Semantik Einfuehrung Skript Kindermann...Einfuhrung in die formale Semantik Skript Wintersemester 2018/2019 Dirk

Prädikatenlogik: modelltheoretische Semantik Herweg... · Pinkal 2000] Stärken von PL-1 als semantischem Repräsentationsformalismus ... Formale Semantik, WS 2014/15 Dr. Michael