Syntax von Programmiersprachen

Token-Typen sind üblicherweise

alle Token eines Typs bilden eine formale Sprache

Beispiele:

man kann eine formale Sprache beschreiben durch:

Aus Sprachen L1, L2 konstruiere:

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:

Jeder solche Ausdruck beschreibt eine reguläre Sprache.

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

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

    die trotzdem nur reguläre Sprachen erzeugen

    Beispiel: Σ* $ \setminus$ (Σ*abΣ*)2

  2. zusätzliche nicht-reguläre Operatoren

    Beispiel: exakte Wiederholungen L$\scriptstyle \fbox{$k$}$ : = {wk | wL}

    beachte Unterschied zu Lk

  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 )

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

w = abba = ab2ab0ab*ab*⊆(ab*)2⊆(ab*)* .

Id

Berechnungs-Modell (Markov-Algorithmen)

Regelmenge RΣ*×Σ*

Regel-Anwendung: uRv$ \iff$x, zΣ*,(l, r)∈R : u = xlzxrz = v .

Beispiel: Bubble-Sort: {baab, caac, cbbc}

Beispiel: Potenzieren: abbba

Aufgaben: gibt es unendlich lange Rechnungen für: R1 = {1000→0001110}, R2 = {aabbbbbaaa} ?

Id

Grammatik G besteht aus:
  • Terminal-Alphabet Σ

    (üblich: Kleinbuchst., Ziffern)

  • Variablen-Alphabet V

    (üblich: Großbuchstaben)

  • Startsymbol SV
  • 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 | SR*wwΣ*} .

Tokenklassen sind meist reguläre Sprachen.

Programmiersprachen werden kontextfrei beschrieben (mit Zusatzbedingungen).

(= rechtslineare Grammatiken)

jede Regel hat die Form

(vgl. lineares Gleichungssystem)

Beispiele

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

Beweispläne:

Id

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

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,{SaSbS, Sε}) .

Bsp: Palindrome: G = ({a, b},{S}, S,{SaSa, SbSb, 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: uw : $ \iff$v : uv = w

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

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

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

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

DL(G) Induktion über Wortlänge

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

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

Erweiterte BNF

kann in BNF übersetzt werden

merke:

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:

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(k1)rand(k2)…rand(kn)

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

Id

Def: G heißt eindeutig, falls wL(G) genau ein Ableitungsbaum (T, m) existiert.

Bsp: ist {SaSb| SS| ε} eindeutig?

(beachte: mehrere Ableitungen SR*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:

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$\displaystyle \;\stackrel{{?}}{{=}}\;$3 + 2*4$\displaystyle \;\stackrel{{?}}{{=}}\;$3 + (2*4)

Grammatik-Regel

summand -> zahl
erweitern zu
summand -> zahl | produkt
produkt -> ...
(Assoziativität beachten)

Ziele:

Festlegung: Realisierung in CFG:

Übung:

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

2015-08-17