SWP: Zusammenfassung · 2019-07-25 · Anwendung der Ableitung bis das gesuchte Wort gefunden wird ! hohe Zeit- und Speicherkomplexität ! terminiert nicht, wenn Satz ∉ Grammatik

Institute for Software Technology

SWP: Zusammenfassung

Bernhard Aichernig und Alexander Felfernig

Institut für Softwaretechnologie [email protected]


SYNTAX

2


Syntax

§  Struktur einer Sprache §  Werkzeug zur Beschreibung aller

möglichen Sätze: Grammatik §  Tupel (VN,VT,S,Φ)

§  Einsatz: §  Überprüfung von Sätzen §  Ableitung möglicher Sätze der Sprache

3


Sprachhierarchie

§  Unrestricted Grammars G Keine Restriktionen bezgl. α→β

§  Context-sensitive Grammars Gsens |α| ≤ |β|

§  Context-free Grammars Gfree |α| ≤ |β| , α ∈ VN

§  Regular Grammars Greg |α| ≤ |β| , α ∈ VN

β hat Form aA oder a, mit a ∈ VT∪{ε}, A ∈ VN

4


Compiler-Zyklus

5

Lexikalische Analyse

Syntax- Analyse

Code- Generierung

Programm (Ausgangssprache)

Tokens (Keywords, Identifier, Konstante, …)

Parse Tree

Programm (Zielsprache)

i.d.R. reguläre Grammatiken (Greg)

i.d.R. kontextfreie Grammatiken (bspw. LL(1))


Parser §  Parsing durch Breitensuche

§  Anwendung der Ableitung bis das gesuchte Wort gefunden wird

§  hohe Zeit- und Speicherkomplexität §  terminiert nicht, wenn Satz ∉ Grammatik §  Überprüfung „label size“ und „redundancy“

§  Top-Down Parsing §  LL(1)-Grammatiken §  schnell, ausdrucksstark, einfach

6


LL(1)-Parsing

§  Recursive Descend Parser (Alt. 1) §  Tabellengestützes Parsing (Alt. 2)

§  LL(1)-Tabelle erzeugen §  First-Mengen (FIRST(α))

§  Erste Terminale in Ableitungen von α

§  Follow-Mengen (FOLLOW(A)) §  Terminale, die direkt rechts neben A in einer

Ableitung stehen können

7

Institute for Software Technology 8

LL(1) Parser §  Tabellengestützter Parser §  Idee: Stack speichert Stand der Ableitung,

oberstes Element=$ à Satz erkannt.

Satz a a b $ $ S

Stack (Stand der Ableitung)

Tabelle

S→aA



SEMANTIK

10


Semantik

§  Bedeutung von Sprachen §  Semantikfunktionen ordnen den

syntaktischen Konstrukten einer Sprache eine Semantik zu

§  Environments beinhalten Abbildungen §  Sprachen sind meist über Datentypen

(auf semantischer Ebene) definiert

11


Datentypen

§  Ein Datentyp ist ein Tupel ℜ = (A, f1,..,fn, p1,..,pm, c1,..,ck)

§  A: Menge §  fi: Funktionen von Aki → Ali

(für bestimmte ki und li) §  pi: Prädikate Aki → { T,F }

(für bestimmtes ki) §  ci: Konstanten (ausgewählte Elemente von A)

12


Sprachen über Datentypen

§  Datentypen sind Beschreibungen auf Semantikebene

§  Verbindung mit Syntaxebene §  über Symbolmengen SYM bestehend aus:

§  Individuen-Variablen Symbole (IVS) §  Funktionssymbole §  Prädikatensymbole §  Konstantensymbole §  Sondersymbole (if, then, …) und (, ) bzw. ,

13


FUNKTIONALE PROGRAMME

14


Sprachen: T §  Sprache der Terme über beliebige

Datentypen §  ENV = Menge aller Abbildungen IVS→A §  Induktive Definition der Syntax §  Semantikfunktion Iτ: ENV × T → A

§  Iτ(ω,c) = c0 für c∈Γ (Konstanten) und ω∈ENV §  Iτ(ω,v) = ω(v) für v∈IVS §  Iτ(ω,f(t1,..,tn)) = f0(Iτ(ω,t1),..,Iτ(ω,tn)) für ti∈T

15


Sprachen: COND

§  Erweiterung von T um Konditionale §  Syntaktische Erweiterung §  Erweiterung der Semantik:

§  Sei po das Prädikat zu Prädikatensymbol p: §  Falls po(Iγ(ω,u1),..,Iγ(ω,un))=T, dann

Iγ(ω,if p(u1,..,un) then t1 else t2) = Iγ(ω,t1 ) §  Falls po(Iγ(ω,u1),..,Iγ(ω,un))=F, dann

Iγ(ω,if p(u1,..,un) then t1 else t2) = Iγ(ω, t2 )

16


Sprachen: EXP

§  Erweiterung um programmdefinierte Funktionen und iterative Konstrukte

§  FVS .. Menge der Funktionsvariablen §  zum Zugriff auf die Funktionsdefinition §  δ: FVS → EXP wobei δ∈FENV §  δX .. Body der Funktion X §  Variablen x1,..,xn im Body: formale

Parameter (keine Funktionsdeklaration)

17


Funktionsaufrufe (Semantik)

§  Interpretation von F(t1,..,tn) §  Call-by-Value

Definiere neues ω‘ als ω‘(xi)=I(δ,ω,ti) für i=1..n wobei x1,..,xn die formalen Parameter in δF sind. I(δ,ω, F(t1,..,tn)) = I(δ, ω‘, δF)

§  Call-by-Name I(δ,ω, F(t1,..,tn)) = I(δ,ω, δF[x1|t1,..,xn|tn]) (Die Ausdrücke ti werden statt xi in den Body eingesetzt)

18


Kodierungen §  Im Grunde kann jeder Datentyp mit

abzählbarem Bereich in L repräsentiert werden. §  π: A1 → A2

§  z.B. π: N → L §  π(3) = [1 1 1] §  π(+(2,1)) = union(π(x), π(y))

19

A

L

A

L

fi

π[fi]

π π


PRÄDIKATENAUSDRÜCKE

20


Prädikatenlogik

§  Symbole: Variablen, Konstanten, Prädikate, Quantoren (∀,∃), Junktoren (¬,∧,∨), Sonderzeichen

§  Grundaufbau:


Semantik (Junktoren)

§  Semantikfunktion I: ENV×PL(ℜ)→{T,F} §  Ist p Prädikatensymbol zum n-stelligen

Prädikat pi: I(ω,p(t1,..,tn))=pi(I(ω,t1),..,I(ω,tn)) §  I(ω, p∨q)=T, wenn I(ω,p)=T oder I(ω,q)=T. §  I(ω, p∧q)=T, wenn I(ω,p)=T und I(ω,q)=T. §  I(ω, p→q)=T, wenn I(ω,p)=F oder wenn

I(ω,p)=T und I(ω,q)=T. §  I(ω, ¬p)=T, wenn I(ω,p)=F.


Semantik (Quantoren)

§  Definition (Äquivalenz modulo v) Sind ω, ω‘ ∈ ENV, dann heißen ω und ω‘

äquivalent modulo v∈IVS, wenn für alle w∈IVS mit v≠w gilt: ω(w)=ω‘(w). Wir schreiben dann ω ~v ω‘ (äquivalent bis auf v).

§  In anderen Worten: ω darf sich von ω‘ nur in höchstens v unterscheiden.


Semantik (Quantoren)

§  binden Variablen, d.h. wir benötigen Freiheit in der Zuweisung innerhalb des Environments §  Allquantor: I(ω,(∀v)p)=T ⇔ Für alle ω‘ mit ω ~v ω‘ gilt I(ω‘,p)=T

§  Existenzquantor: I(ω,(∃v)p)=T ⇔ Für mind. ein ω‘ mit ω ~v ω‘ gilt I(ω‘,p)=T


Definitionen

§  Ist p∈PL(ℜ), so heißt p gültig in ℜ, wenn für alle ω∈ENV gilt I(ω,p)=T.

§  Ist p∈PL(ℜ), so heißt p erfüllbar in ℜ, wenn es ein ω∈ENV gibt mit I(ω,p)=T.

§  Ist p∈PL(ℜ), so heißt p unerfüllbar in ℜ, wenn für alle ω∈ENV gilt I(ω,p)=F.

§  Beachte quantorgebundene vs. freie Variablen!


ASSIGNMENTSPRACHEN

26


Besonderheiten

§  Zuordnungen v := t §  d.h. Variablen werden Termen zugeordnet,

die deren Wert verändern §  Variablenenvironment kann sich mit der

Interpretation jeder Zeile ändern §  IAL: ENV×AL → ENV

§  weitere neue syntaktische Elemente: §  Blöcke begin a1;a2 end §  Schleifen while B do a1

27


Semantikfunktion

§  Bereits definiert für §  Prädikatenlogischen Ausdrücke

§  IPL : ENV×PL(ℜ) → {T,F}

§  Terme §  IT: ENV×T(ℜ) → A

§  Erweiterungen (beispielhaft): §  IAL(ω,v := t) = ω‘

mit ω‘(v)=IT(ω,t) und ω‘(w)= ω(w) für w≠v §  IAL(ω, begin a1;a2 end ) = IAL(IAL(ω,a1),a2)

28


LOGISCHE PROGRAMME

29


Sprache LP

§  Syntaktische Elemente §  Atomformeln: p(t1,..,tn) §  Fakten: p(t1,..,tn) := . §  Regeln: A := A1,..,Ak.

§  Programm = Reihe von Fakten und Regeln

§  Berechnung = Beweis einer Anfrage := A1,..,Ak.

30


Grundlagen

§  Transformationen: §  A1 ∧ .. ∧ Ak → A |= ¬A1 ∨ .. ∨ ¬Ak ∨ A §  A1 ∧ .. ∧ Ak → ⊥ |= ¬A1 ∨ .. ∨ ¬Ak

§  Aufbau aus Hornklauseln: §  Disjunktionen von Literalen (Klauseln) §  mit maximal einem positiven Literal

§  Anwendung der Resolution §  Widerspruchsbeweis

31


DANKE!

32

Documents

SWP: Zusammenfassung · 2019-07-25 · Anwendung der Ableitung bis das gesuchte Wort gefunden wird ! hohe Zeit- und Speicherkomplexität ! terminiert nicht, wenn Satz ∉ Grammatik