1
Grundlagen der Programmierung 2(Comp-B)
Prof. Dr. Manfred Schmidt-Schauÿ
Künstliche Intelligenz und Softwaretechnologie
17. Juni 2008
Programmiersprache: Syntax
Grundlagen der Programmierung 2 (Comp-B) - 1 -
Fragestellung:
Mit welchem Mechanismus beschreibt man
gultige Programme einer Programmiersprache S?
Programmiersprache: Syntax
Grundlagen der Programmierung 2 (Comp-B) - 2 -
Akzeptiertes (und erfolgreiches) Vorgehen der Informatik:
• gultige S-Programme (als Text) sind Worte einer formalen Sprache LS
• Beschreibung einer Obermenge L(G) der formalen Sprache LSmittels einer kontextfreien Grammatik (CFG) Gmit eindeutigen Syntaxbaumen
• Weitere Einschrankung von L(G) (durch Bedingungen) ergibt LS.
Leider:
die operationale Semantik wird meist weniger formal beschrieben
Kontextfreie Grammatik (CFG)
Grundlagen der Programmierung 2 (Comp-B) - 3 -
4-Tupel G = (N, T, P, σ) mit
1 N : endliche Menge von Hilfszeichen (Nonterminals)2 T endliche Menge von Terminalzeichen (Terminals),
wobei N ∩ T = ∅.3 P ⊆ N × (N ∪ T )∗ endliche Menge von Regeln (Produktionen)4 σ ∈ N ist Startzeichen
Regeln schreibt man auch A → w oder A ::= w.
Erzeugte Sprache L(G) = erreichbare Worte uber T .
= {w ∈ T ∗ | σ∗−→G w}
Allgemeine Grammatiken
Grundlagen der Programmierung 2 (Comp-B) - 4 -
erlauben beliebige Strings in (N ∪ T )∗ als linke Seite von Regeln.
• unbeschrankte Grammatik bzw. Semi-Thue-Systeme
• kontextsensitiv, wenn fur alle Regeln:a → w nur wenn |a| ≤ |w|
Zwei Beispiel-CFGs fur “Ausdruck“
Grundlagen der Programmierung 2 (Comp-B) - 5 -
Die AZ-Grammatik
A ::= A + Z | A - Z | Z
Z ::= 0| . . . |9
Die AA-Grammatik:
A ::= A+AA ::= A - AA ::= 0 | . . . | 9
fur sehr einfache arithmetische Ausdrucke: z.B. 9 + 2− 5 + 3
Herleitungen
Grundlagen der Programmierung 2 (Comp-B) - 6 -
Definition
Sei (G = N, T, P, σ) gegeben
• v → v′ (direkt hergeleitet)
gdw.
v = αAβ und v′ = αwβ, und A ::= w eine Regel in G ist.
• v1 →∗ vn (vn ist aus v1 herleitbar)
gdw.
∃v2, . . . , vn−1 ∈ (T ∪N)∗, so dass
v1 → v2 → . . . → vn−1 → vn
Herleitungen; Sprache zu G
Grundlagen der Programmierung 2 (Comp-B) - 7 -
Die erzeugte Sprache L(G) zur Grammatik G
ist die Menge der Strings w aus Terminalsymbolen,
die aus dem Startsymbol σ hergeleitet werden konnen:
L(G) := {w ∈ T ∗ | σ →∗ w}
Beispiel: AZ-Grammatik zu Ausdruck
Grundlagen der Programmierung 2 (Comp-B) - 8 -
A ::= A+Z | A-Z | ZZ ::= 0| . . . |9
Startsymbol: A,Nichtterminalsymbole: A, ZTerminalsymbole: {0, . . . ,9,+,−}.
Eine Beispiel-Herleitung:
A → A+Z → Z+Z → 1+Z → 1+2.
Somit gilt:
A →∗ 1+2
Also:”1+2“ ∈ L(G)
Rechts- und Linksherleitungen
Grundlagen der Programmierung 2 (Comp-B) - 9 -
Linksherleitung: Ersetze stets das linkeste Nichtterminal
Rechtsherleitung: Ersetze stets das rechteste Nichtterminal
Die AA-Grammatik:
A ::= A+AA ::= A - AA ::= 0 | . . . | 9
Linksherleitung: A → A+A → 1+A → 1+2
Rechtsherleitung: A → A+A → A+2 → 1+2
Herleitungsbaum, Parse-Baum
Grundlagen der Programmierung 2 (Comp-B) - 10 -
Zur textfreien Grammatik G = (N, T, P, σ)
Kann man Herleitungen mittels
Herleitungsbaumen, bzw. Parse-Baumen darstellen.
Herleitungsbaume
Grundlagen der Programmierung 2 (Comp-B) - 11 -
Beispiel zu AA-Grammatik
A ::= A+AA ::= A - AA ::= 0 | . . . | 9
Zwei verschiedene Herleitungsbaume fur “1 - 2 + 3“ sind:
A
}}}}
}}}
BBBB
BBBB
A − A
}}}}
}}}}
AAAA
AAAA
1 A + A
2 3
A
}}}}
}}}}
AAAA
AAAA
A
~~~~
~~~~
AAAA
AAAA
+ A
A − A 3
1 2
• Wurzel des Baumes ≡ Startsymbol• Knoten ≡ Grammatik-Regel• Rand des Baumes ≡ hergeleitetes Wort
Eigenschaften von Herleitungsbaumen
Grundlagen der Programmierung 2 (Comp-B) - 12 -
• pro Herleitungsbaum gibt es
genau eine Rechtsherleitung
und genau eine Linksherleitung
(und umgekehrt auch)
• Die Bedeutung eines Programms wird festgelegt
anhand des Herleitungsbaumes
Eindeutigkeit einer CFG
Grundlagen der Programmierung 2 (Comp-B) - 13 -
Definition
Eine kontextfreie Grammatik G heißt eindeutig, wenn fur alle w ∈ L(G)
genau ein Herleitungsbaum existiert.
Andernfalls heißt die Grammatik mehrdeutig.
Wenn G eindeutig ist,
Dann gibt es fur jedes Wort in L(G)
genau einen Herleitungsbaum
und genau eine Rechts-Herleitung
und genau eine Links-Herleitung
Beispiel zu aquivalenten Grammatiken
Grundlagen der Programmierung 2 (Comp-B) - 14 -
AZ-Grammatik AA-GrammatikA ::= A + Z | A - Z | ZZ ::= 0| . . . |9 A ::= A+A | A-A | 0 | . . . | 9
Die AA-Grammatik ist (sprach-)aquivalent zur AZ-Grammatik:
Die Sprachen L(GAA) = L(GAZ ) enthalten genau
die Worte: z1 op1 z2 . . . opn zn+1
mit zi ∈ {1,2,3,4,5,6,7,8,9,0}und opi ∈ {+, -}
Aber: haben verschiedene Herleitungsbaume.
Eindeutige CFG zu A
Grundlagen der Programmierung 2 (Comp-B) - 15 -
A ::= A+ZA ::= A-ZA ::= ZZ ::= 0 | . . . | 9
Der einzige (d.h eindeutige) AZ-Herleitungsbaum fur 1− 2 + 3 ist:
und ein Syntaxbaum dazu
A
}}}}
}}}}
AAAA
AAAA
A
~~~~
~~~~
AAAA
AAAA
+ Z
A − Z 3
Z 2
1
+
}}}}
}}}
@@@@
@@@@
−}}
}}}}
}
BBBB
BBBB
Z
Z Z 3
1 2
Eindeutige CFG zu Ausdruck
Grundlagen der Programmierung 2 (Comp-B) - 16 -
A
}}}}
}}}}
AAAA
AAAA
A
~~~~
~~~~
AAAA
AAAA
+ Z
A − Z 3
Z 2
1
+
}}}}
}}}
@@@@
@@@@
−}}
}}}}
}
BBBB
BBBB
Z
Z Z 3
1 2
Die (eindeutige) Links-Herleitung kann man am Syntaxbaum ablesen:
A → A+Z → A-Z+Z → Z-Z+Z → 1-Z+Z → 1-2+Z → 1-2+3
Syntaxbaume statt Herleitungsbaume
Grundlagen der Programmierung 2 (Comp-B) - 17 -
Beispiele:
Herleitungsbaum Syntaxbaum
·ppppppppppppppp
NNNNNNNNNNNNNNN
1 + 2
+
qqqqqqqqqqqqqq
MMMMMMMMMMMMMM
1 2
·
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
lllllllllllllllllllllllllllll
zzzz
zzzz
zzzz
zzz
CCCC
CCCC
CCCC
CC
QQQQQQQQQQQQQQQQQQQQQQQQQQQ
IF a THEN b ELSE c
IfThenElse
oooooooooooooooooooooo
OOOOOOOOOOOOOOOOOOOOOO
a b c
Semantikfestlegung
Grundlagen der Programmierung 2 (Comp-B) - 18 -
Semantik eines Wortes wird festgelegt
mittels Parsebaum / Syntaxbaum
Mehrdeutige Grammatik entspricht i.a.
mehrdeutiger (d.h. undefinierter) Semantik
Reparatur: Erzeuge aquivalente eindeutige Grammatik
Grammatiken aquivalent bzgl L(.) reicht nicht aus fur aquivalente Se-
mantik
Grammatiktransformation
Grundlagen der Programmierung 2 (Comp-B) - 19 -
Grammatiktransformation G1 → G2 mit L(G1) = L(G2)
sollte die operationale Semantik der Programme gleich lassen:
Deshalb muss gelten:
Operation1 (Parsebaum1(w)) ≡ Operation2( Parsebaum2(w))