Syntax von Programmiersprachen

• ein Programmtext repräsentiert eine Hierarchie (einen Baum) von Teilprogrammen

• Die Semantik des Programmes wird durch Induktion über diesen Baum definiert.

• In den Knoten des Baums stehen Token,
• jedes Token hat einen Typ und einen Inhalt (eine Zeichenkette).

• diese Prinzip kommt aus der Mathematik (arithmetische Ausdrücke, logische Formeln)

Token-Typen sind üblicherweise

• reservierte Wörter (if, while, class, ...)
• Bezeichner (foo, bar, ...)
• Literale für ganze Zahlen, Gleitkommazahlen, Strings, Zeichen
• Trennzeichen (Komma, Semikolon)
• Klammern (runde: paren(these)s, eckige: brackets, geschweifte: braces, spitze: angle brackets)
• Operatoren (=, +, &&, ...)
• Leerzeichen, Kommentare (whitespace)

alle Token eines Typs bilden eine formale Sprache

• ein Alphabet ist eine Menge von Zeichen,
• ein Wort ist eine Folge von Zeichen,
• eine formale Sprache ist eine Menge von Wörtern.

Beispiele:

• Alphabet Σ = {a, b} ,
• Wort w = ababaaab ,
• Sprache L = Menge aller Wörter über Σ gerader Länge.
• Sprache (Menge) aller Gleitkomma-Konstanten in C.

man kann eine formale Sprache beschreiben durch:

• algebraisch (Sprach-Operationen)

  Bsp: reguläre Ausdrücke

• Generieren (Grammatik), Bsp: kontextfreie Grammatik,
• Akzeptanz (Automat), Bsp: Kellerautomat,
• logisch (Eigenschaften), $\left\{\vphantom{ w\mid \forall p,r: \left(\begin{array}{ll} & (p<r \wedge w[... ...ghtarrow & \exists q: (p<q \wedge q<r\wedge w[q]=b) \end{array}\right) }\right.$w | ∀p, r : $\left(\vphantom{\begin{array}{ll} & (p<r \wedge w[p]=a \wedge w[r]=c) \\ \Rightarrow & \exists q: (p<q \wedge q<r\wedge w[q]=b) \end{array}}\right.$$\begin{array}{ll} & (p<r \wedge w[p]=a \wedge w[r]=c) \\ \Rightarrow & \exists q: (p<q \wedge q<r\wedge w[q]=b) \end{array}$$\left.\vphantom{\begin{array}{ll} & (p<r \wedge w[p]=a \wedge w[r]=c) \\ \Rightarrow & \exists q: (p<q \wedge q<r\wedge w[q]=b) \end{array}}\right)$$\left.\vphantom{ w\mid \forall p,r: \left(\begin{array}{ll} & (p<r \wedge w[p... ...htarrow & \exists q: (p<q \wedge q<r\wedge w[q]=b) \end{array}\right) }\right\}$

Aus Sprachen L₁, L₂ konstruiere:

• Mengenoperationen
  • Vereinigung L₁∪L₂ ,
  • Durchschnitt L₁∩L₂ , Differenz L₁ $\setminus$ L₂ ;
• Verkettung L₁⋅L₂  = {w₁⋅w₂ | w₁∈L₁, w₂∈L₂}
• Stern (iterierte Verkettung) L₁^*  = $\bigcup_{{k\ge 0}}^{}$L₁^k

Def: Sprache regulär : $\iff$ kann durch diese Operationen aus endlichen Sprachen konstruiert werden.

Satz: Durchschnitt und Differenz braucht man dabei nicht.

Die Menge E(Σ) der regulären Ausdrücke
über einem Alphabet (Buchstabenmenge) Σ
ist die kleinste Menge E , für die gilt:

• für jeden Buchstaben x∈Σ : x∈E

  (autotool: Ziffern oder Kleinbuchstaben)

• das leere Wort ε∈E (autotool: Eps)
• die leere Menge ∅∈E (autotool: Empty)
• wenn A, B∈E , dann
  • (Verkettung) A⋅B∈E (autotool: * oder weglassen)
  • (Vereinigung) A + B∈E (autotool: +)
  • (Stern, Hülle) A^*∈E (autotool: ^*)

Jeder solche Ausdruck beschreibt eine reguläre Sprache.

Wir fixieren das Alphabet Σ = {a, b} .

• alle Wörter, die mit a beginnen und mit b enden: aΣ^*b .
• alle Wörter, die wenigstens drei a enthalten Σ^*aΣ^*aΣ^*aΣ^*
• alle Wörter mit gerade vielen a und beliebig vielen b ?
• Alle Wörter, die ein aa oder ein bb enthalten: Σ^*(aa∪bb)Σ^*
• (Wie lautet das Komplement dieser Sprache?)

1. zusätzliche Operatoren (Durchschnitt, Differenz, Potenz),

   die trotzdem nur reguläre Sprachen erzeugen

   Beispiel: Σ^* $\setminus$ (Σ^*abΣ^*)²

2. zusätzliche nicht-reguläre Operatoren

   Beispiel: exakte Wiederholungen L^$\fbox{$k$}$ : = {w^k | w∈L}

   beachte Unterschied zu L^k

3. Markierung von Teilwörtern, definiert (evtl. nicht-reguläre) Menge von Wörtern mit Positionen darin

wenn nicht-reguläre Sprachen entstehen können, ist keine effiziente Verarbeitung (mit endlichen Automaten) möglich.

auch reguläre Operatoren werden gern schlecht implementiert (http://swtch.com/~rsc/regexp/regexp1.html)

Wie beweist man w∈L(X) ?

(Wort w gehört zur Sprache eines regulären Ausdrucks X )

• wenn X = X₁ + X₂ :

  beweise w∈L(X₁) oder beweise w∈L(X₂)

• wenn X = X₁⋅X₂ :

  zerlege w = w₁⋅w₂ und beweise w₁∈L(X₁) und beweise w₂∈L(X₂) .

• wenn X = X₁^* :

  wähle einen Exponenten k∈$\mathbb {N}$ und beweise w∈L(X₁^k) (nach vorigem Schema)

Beispiel: w = abba, X = (ab^*)^* .

w = abb⋅a = ab²⋅ab⁰∈ab^*⋅ab^*⊆(ab^*)²⊆(ab^*)^* .

• (Σ^*,⋅, ε) ist Monoid

• ...aber keine Gruppe, weil man im Allgemeinen nicht dividieren kann. Welche Relation ergibt sich als „Teilbarkeit``: u | w : = ∃v : u⋅v = w

• Zeichne Hasse-Diagramme der Teilbarkeitsrelation
  • auf natürlichen Zahlen {0, 1,..., 10} ,
  • auf Wörtern {a, b}^≤2

• (Pow(Σ^*),∪,⋅,...,...) ist Halbring.

  Beispiel für Distributivgesetz?

  Welches sind jeweils die neutralen Elemente der Operationen?

  (vgl. oben) Welche Relation auf Sprachen (Mengen) ergibt sich als „Teilbarkeit`` bzgl. ∪ ?

• Damit a^b+c = a^b⋅a^c immer gilt, muß man a⁰ wie definieren?

• Block-Kommentare und weitere autotool-Aufgaben

• reguläre Ausdrücke für Tokenklassen in der Standard-Pascal-Definition http://www.standardpascal.org/iso7185.html#6.1 Lexical tokens

  Welche Notation wird für unsere Operatoren + und Stern benutzt? Was bedeuten die eckigen Klammern?

Id

Berechnungs-Modell (Markov-Algorithmen)

• Zustand (Speicherinhalt): Zeichenfolge (Wort)
• Schritt: Ersetzung eines Teilwortes

Regelmenge R⊆Σ^*×Σ^*

Regel-Anwendung: u→_Rv$\iff$∃x, z∈Σ^*,(l, r)∈R : u = x⋅l⋅z∧x⋅r⋅z = v .

Beispiel: Bubble-Sort: {ba→ab, ca→ac, cb→bc}

Beispiel: Potenzieren: ab→bba

Aufgaben: gibt es unendlich lange Rechnungen für: R₁ = {1000→0001110}, R₂ = {aabb→bbbaaa} ?

Id

Grammatik G besteht aus:

• Terminal-Alphabet Σ

  (üblich: Kleinbuchst., Ziffern)

• Variablen-Alphabet V

  (üblich: Großbuchstaben)

• Startsymbol S∈V
• Regelmenge
  (Wort-Ersetzungs-System)

  R⊆(Σ∪V)^*×(Σ∪V)^*

Grammatik
  { terminale 
       = mkSet "abc"
  , variablen
       = mkSet "SA"
  , start = 'S'
  , regeln = mkSet
       [ ("S", "abc")
       , ("ab", "aabbA")
       , ("Ab", "bA")
       , ("Ac", "cc")
       ]
  }

von G erzeugte Sprache: L(G) = {w | S→_R^*w∧w∈Σ^*} .

• (Typ 0) aufzählbare Sprachen (beliebige Grammatiken, Turingmaschinen)
• (Typ 1) kontextsensitive Sprachen (monotone Grammatiken, linear beschränkte Automaten)
• (Typ 2) kontextfreie Sprachen (kontextfreie Grammatiken, Kellerautomaten)
• (Typ 3) reguläre Sprachen (rechtslineare Grammatiken, reguläre Ausdrücke, endliche Automaten)

Tokenklassen sind meist reguläre Sprachen.

Programmiersprachen werden kontextfrei beschrieben (mit Zusatzbedingungen).

(= rechtslineare Grammatiken)

jede Regel hat die Form

• Variable → Terminal Variable
• Variable → Terminal
• Variable →ε

(vgl. lineares Gleichungssystem)

Beispiele

• G₁ = ({a, b},{S, T}, S,{S→ε, S→aT, T→bS})
• G₂ = ({a, b},{S, T}, S,{S→ε, S→aS, S→bT, T→aT, T→bS})

Für jede Sprache L sind die folgenden Aussagen äquivalent:

• es gibt einen regulären Ausdruck X mit L = L(X) ,
• es gibt eine Typ-3-Grammatik G mit L = L(G) ,
• es gibt einen endlichen Automaten A mit L = L(A) .

Beweispläne:

• Grammatik ↔ Automat (Variable = Zustand)
• Ausdruck → Automat (Teilbaum = Zustand)
• Automat → Ausdruck (dynamische Programmierung)

  L_A(p, q, r) = alle Pfade von p nach r über Zustände ≤q .

Id

Def (Wdhlg): G ist kontextfrei (Typ-2), falls ∀(l, r)∈R(G) : l∈V .

geeignet zur Beschreibung von Sprachen mit hierarchischer Struktur.

Anweisung -> Bezeichner = Ausdruck
    | if Ausdruck then Anweisung else Anweisung
Ausdruck -> Bezeichner | Literal
    | Ausdruck Operator Ausdruck

Bsp: korrekt geklammerte Ausdrücke: G = ({a, b},{S}, S,{S→aSbS, S→ε}) .

Bsp: Palindrome: G = ({a, b},{S}, S,{S→aSa, S→bSb, S→ε) .

Bsp: alle Wörter w über Σ = {a, b} mit | w|_a = | w|_b

Abstraktion von vollständig geklammerten Ausdrücke mit zweistelligen Operatoren

(4*(5+6)-(7+8)) ⇒ (()()) ⇒aababb

Höhendifferenz: h : {a, b}^*→$\mathbb {Z}$ : w $\mapsto$ | w|_a - | w|_b

Präfix-Relation: u≤w : $\iff$∃v : u⋅v = w

Dyck-Sprache: D = {w | h(w) = 0∧∀u≤w : h(u)≥0}

CF-Grammatik: G = ({a, b},{S}, S,{S→ε, S→aSbS})

Satz: L(G) = D . Beweis (Plan):

L(G)⊆D Induktion über Länge der Ableitung

D⊆L(G) Induktion über Wortlänge

• Beispiele Wort-Ersetzung (ab→baa , usw.)
• Dyck-Sprache: Beweis L(G)⊆D

  (Induktionsbehauptung? Induktionsschritt?)

• Dyck-Sprache: Beweis D⊆L(G)

• CF-Grammatik für {w | w∈{a, b}^*,| w|_a = | w|_b}

• CF-Grammatik für {w | w∈{a, b}^*, 2⋅| w|_a = | w|_b}

• Noam Chomsky: Struktur natürlicher Sprachen (1956)
• John Backus, Peter Naur: Definition der Syntax von Algol (1958)

Backus-Naur-Form (BNF) $\approx$ kontextfreie Grammatik

<assignment> -> <variable> = <expression>
<number> -> <digit> <number> | <digit>

Erweiterte BNF

• Wiederholungen (Stern, Plus) <digit>^+
• Auslassungen

  if <expr> then <stmt> [ else <stmt> ]
  

kann in BNF übersetzt werden

• Regexp wie hier (in der „Theorie``)
• „Perl-kompatible`` Regexp usw. usf.

merke:

• Regexp kann man dort sinnvoll anwenden, wo es um reguläre Sprachen geht.
• Klammersprachen sind nicht regulär.
• Wenn Regexp erweitert werden, um nicht-reguläre Sprachen zu erzeugen, dann gibt es keine effiziente Implementierung mehr
• ...das verhindert oft schon die effiziente Behandlung regulärer Sprachen

Cox 2007 http://swtch.com/~rsc/regexp/regexp1.html

Id

Def: ein geordneter Baum T mit Markierung m : T→Σ∪{ε}∪V ist Ableitungsbaum für eine CF-Grammatik G , wenn:

• für jeden inneren Knoten k von T gilt m(k)∈V
• für jedes Blatt b von T gilt m(b)∈Σ∪{ε}
• für die Wurzel w von T gilt m(w) = S(G) (Startsymbol)
• für jeden inneren Knoten k von T mit Kindern k₁, k₂,…, k_n gilt (m(k), m(k₁)m(k₂)…m(k_n))∈R(G) (d. h. jedes m(k_i)∈V∪Σ )
• für jeden inneren Knoten k von T mit einzigem Kind k₁ = ε gilt (m(k), ε)∈R(G) .

Def: der Rand eines geordneten, markierten Baumes (T, m) ist die Folge aller Blatt-Markierungen (von links nach rechts).

Beachte: die Blatt-Markierungen sind ∈{ε}∪Σ , d. h. Terminalwörter der Länge 0 oder 1.

Für Blätter: rand(b) = m(b) , für innere Knoten: rand(k) = rand(k₁)rand(k₂)…rand(k_n)

Satz: w∈L(G)$\iff$ existiert Ableitungsbaum (T, m) für G mit rand(T, m) = w .

Id

Def: G heißt eindeutig, falls ∀w∈L(G) genau ein Ableitungsbaum (T, m) existiert.

Bsp: ist {S→aSb| SS| ε} eindeutig?

(beachte: mehrere Ableitungen S→_R^*w sind erlaubt, und wg. Kontextfreiheit auch gar nicht zu vermeiden.)

Die naheliegende Grammatik für arith. Ausdr.

expr -> number | expr + expr | expr * expr

ist mehrdeutig (aus zwei Gründen!)

Auswege:

• Transformation zu eindeutiger Grammatik (benutzt zusätzliche Variablen)
• Operator-Assoziativitäten und -Präzedenzen

• Definition: Operation ist assoziativ
• Bsp: Plus ist nicht assoziativ (für Gleitkommazahlen) (Ü)
• für nicht assoziativen Operator $\odot$ muß man festlegen,
  was x $\odot$ y $\odot$ z bedeuten soll:
  

  $$\;\stackrel{{?}}{{=}}\; \;\stackrel{{?}}{{=}}\;$$

  $$\;\stackrel{{?}}{{=}}\; \;\stackrel{{?}}{{=}}\;$$

  $$\;\stackrel{{?}}{{=}}\; \;\stackrel{{?}}{{=}}\;$$

  
  
• ...und dann die Grammatik entsprechend einrichten

X1 + X2 + X3 auffassen als (X1 + X2) + X3

Grammatik-Regeln

Ausdruck -> Zahl | Ausdruck + Ausdruck

ersetzen durch

Ausdruck -> Summe 
Summe    -> Summand | Summe + Summand
Summand  -> Zahl

(3 + 2)*4$$\;\stackrel{{?}}{{=}}\;$$3 + 2*4$$\;\stackrel{{?}}{{=}}\;$$3 + (2*4)

Grammatik-Regel

summand -> zahl

erweitern zu

summand -> zahl | produkt
produkt -> ...

(Assoziativität beachten)

Ziele:

• Klammern einsparen
• trotzdem eindeutig bestimmter Syntaxbaum

Festlegung:

• Assoziativität:
  bei Kombination eines Operators mit sich
• Präzedenz:
  bei Kombination verschiedener Operatoren

Realisierung in CFG:

• Links/Rechts-Assoziativität ⇒ Links/Rechts-Rekursion
• verschiedene Präzedenzen ⇒ verschiedene Variablen

Übung:

• Verhältnis von plus zu minus, mal zu durch?
• Klammern?
• unäre Operatoren (Präfix/Postfix)?

naheliegende EBNF-Regel für Verzweigungen:

<statement> -> if <expression> 
    then <statement> [ else <statement> ]

führt zu einer mehrdeutigen Grammatik.

Dieser Satz hat zwei Ableitungsbäume:

if X1 then if X2 then S1 else S2

• Festlegung: das „in der Luft hängende`` (dangling) else
  gehört immer zum letzten verfügbaren then.
• Realisierung durch Grammatik mit (Hilfs-)Variablen

  <statement>, <statement-no-short-if>