Praktische Informatik 1

2.2 Sprachen, Grammatiken, Syntaxdiagramme

Die obigen Darstellungsformen sind geeignet zur Repräsentation einzelner Objekte. Häufig steht man vor dem Problem, Mengen von gleichartigen Objekten repräsentieren zu müssen. Für endliche Mengen kann dies durch die Folge der Elemente geschehen; für unendliche Mengen geht das im Allgemeinen nicht. Daher muss man sich andere (symbolische) Darstellungsformen überlegen.

Darstellung von Sprachen

Ein besonders wichtiger Fall ist die Darstellung von unendlichen Mengen von Wörtern, die einem bestimmten Bildungsgesetz unterliegen; zum Beispiel die Menge der syntaktisch korrekten Eingaben in einem Eingabefeld, oder die Menge der Programme einer Programmiersprache.

Eine Sprache ist eine Menge von Wörtern über einem Alphabet A.

• 
  z.B. {a, aab, aac}
  
• 
  z.B. Menge der grammatisch korrekten Sätze der dt. Sprache
  
• 
  z.B. Menge der Groovy-Programme
  

Man unterscheidet zwischen natürlichen Sprachen wie z.B. deutsch und englisch und formalen Sprachen wie z.B. Java, Groovy, C++ oder der Menge der Primzahlen in Hexadezimaldarstellung. Da Leerzeichen in der Lehre von den formalen Sprachen genau wie andere Zeichen behandelt werden, gibt es hier keinen Unterschied zwischen Wörtern und Sätzen.
Unter Syntax versteht man die Lehre von der Struktur einer Sprache

• 
  Welche Wörter gehören zur Sprache?
  
• 
  Wie sind sie intern strukturiert?
  

z.B. Attribut, Prädikatverbund, Adverbialkonstruktion

Unter Semantik versteht man die Lehre von der Bedeutung der Sätze

• 
  Welche Information transportiert ein Wort der Sprache?
  

In der Linguistik betrachtet man manchmal noch den Begriff Pragmatik, darunter versteht man die Lehre von der Absicht von sprachlichen Äußerungen

• 
  Welchen Zweck verfolgt der Sprecher mit einem Wort?
  

Berühmtes Beispiel für den Unterschied zwischen Semantik und Pragmatik ist die Beifahrer-Aussage „Die Ampel ist grün“.
Grammatiken

Grammatiken sind Werkzeuge zur Beschreibung der Syntax einer Sprache. Eine Grammatik

stellt bereit

• 
  A : Alphabet oder „Terminalzeichen“
  
• 
  H : Hilfssymbole = syntaktische Einheiten (,..) oder „Nonterminalzeichen“
  

Aus A und H bildet man Satzformen (Schemata korrekter Sätze)
z.B. “
”, “ Heute
< Subjekt> “

• 
  R: Ableitungsregeln – erlaubte Transformationen auf Satzformen
  
• 
  s: Ein ausgezeichnetes Hilfssymbol („Gesamtsatz”, „Axiom“)
  

Formal ist eine Grammatik ein Tupel G = [A, H, R, s], wobei

• 
  A und H Alphabete sind mit A  H = Ø
  
• 
  R  (A  H)⁺  (A  H)^*
  
• 
  s  H
  

Die Relation R wird meist mit dem Symbol  oder ::= (in Infixschreibweise) notiert.

Zwischen Satzformen definieren wir eine Relation –> (direkte Ableitungsrelation)

w–>w’, falls w = w_1°u_°w₂, w’ = w_1°v_°w₂ und (u,v)  R

Die Ableitungsrelation => ist die reflexiv-transitive Hülle der direkten Ableitungsrelation:

w=>w’, falls w=w’ oder es gibt ein v  (A  H)* mit w–>v und v=>w’

Die von der Grammatik G beschriebene Sprache L_G ist definiert durch

L_G = { w | s => w und w  A* }
Beispiel

A={“große“, “gute“, “jagen“, “lieben”, “Katzen”, “Mäuse”}

H={,,
,,,,}

s=

R: 
“.”





“gute”

“große”

“Katzen”

“Mäuse”



“lieben”

“jagen”




Beispiel für Generierung:

–>
“.”

–> “.”

–> “gute” “Katzen” “jagen” “Mäuse” “.”

Beispiel für Akzeptierung:

“Katzen lieben große Mäuse .”

<– “.”

<– “.”

<–
“.”

<–
Noch ein Beispiel



 “+”



 “•”



 “-”

 “x”

 “0”

 “1”

 “(“ “)”
Ableitung aus dem Beispiel: => “1•(1+x)+0•-1”

–> “+”

–> “+” “•”

–> “•” “+”“ •” “-”

–> “•” “+” “•” “-” “1”

–> “•” “ (“ “)” “+” “0” “•” “-” “1”

–> “1” “•” “(“ “+” “)” “+” “0” “•” “-” “1”

–> “1” “•” “(“ “+” “)” “+” “0” “•” “-” “1”

–> “1” “•” “(“ “+” “)” “+” “0” “•” “-” “1”

–> “1” “•” “(“ “+” “x” “)” “+” “0” “•” “-” “1”

–> “1” “•” “(“ “1” “+” “x” “)” “+” “0” “•” “-” “1”

Grammatiktypen – Die Chomsky-Hierarchie

Die Lehre von den Grammatiken wurde vom amerikanischen Linguisten Noam Chomsky (geb. 1928, http://web.mit.edu/linguistics/people/faculty/chomsky/index.html) („America's most prominent political dissident“, http://www.zcommunications.org/chomsky/index.cfm) in den späten 1950-ern entwickelt. Chomsky unterscheidet vier Typen von Grammatiken:

• 
  Typ 0 - beliebige Grammatiken
  
• 
  Typ 1 - kontextsensitive Grammatiken
  
  • 
    Ersetzt wird ein einziges Hilfssymbol, nichtverkürzend
    
  • 
    Alle Regeln haben die Form u+h+w  u+v+w mit h  H
    
  • 
    u , w heißen linker bzw. rechter Kontext
    
  • 
    Sonderregel für das leere Wort
    
• 
  Typ 2 – kontextfreie Grammatiken
  
  • 
    Ersetzt wird ein einziges Hilfssymbol, egal in welchem Kontext
    
  • 
    Alle Regeln haben die Form h  v mit h  H
    
• 
  Typ 3 – reguläre Grammatiken
  
  • 
    Wie Typ 2, in v kommt aber max. ein neues Hilfssymbol vor, und zwar ganz rechts
    

Abhängig vom Typ spricht man auch von einer Chomsky-i-Grammatik.

Beispiele (A={a, b, c}, H={s, x, y, z, …}):

Chomsky-0-Regeln sind z.B. die folgenden: xyz ::= zyx, abc ::= x, axby ::= abbxy

Eine Chomsky-0-Grammatik für {aⁿbⁿcⁿ | n>0} erhält man durch folgende Regeln:

s::= xs’z; s’ ::= s’s’; s’ ::= abc; ba ::= ab; ca ::= ac; cb ::= bc;

xa ::= ax; x ::= y; yb ::= by; y ::= z; zc ::= cz; zz ::=

xyz ::= xyxyz (Chomsky-1-Regel) Anwendung: axyzxa -> axyxyza -> axyxyxyza -> …

y ::= yxy (Chomsky-2-Regel)

x::= ax; x::= b (Chomsky-3-Sprache a^*b )

Eine Sprache heißt Chomsky-i-Sprache, wenn es eine Chomski-i-Grammatik für sie gibt, aber keine Chomsky-(i-1)-Grammatik. Die vier Typen bilden eine echte Hierarchie, d.h., für i=0,1,2 kann man jeweils eine Sprache finden, die durch eine Chomsky-i-Grammatik, nicht aber durch eine Chomsky-i+1-Grammatik beschreibbar ist. Es gilt:

• 
  Mit beliebigen Grammatiken lassen sich alle Sprachen beschreiben, die überhaupt berechenbar sind
  
• 
  Kontextsensitive Grammatiken sind algorithmisch beherrschbar
  
• 
  Für die meisten Programmiersprachen wird die Syntax in Form kontextfreier Grammatiken angegeben.
  
• 
  Einfache Konstrukte innerhalb von Programmiersprachen (z.B. Namen, Zahlen) werden durch reguläre Grammatiken beschrieben.
  

Aufschreibkonventionen für kontextfreie Grammatiken

Backus-Naur-Form (BNF) verwendet u ::= v | w als Abkürzung für {u ::= v, u ::= w}
Beispiel:

::= | +

::= | •

::= | -

::= x | 0 | 1 | ( )
Erweiterte Backus-Naur-Form (EBNF) löst direkte Rekursion durch beliebigmalige Wiederholungsklammern {} auf
Beispiel:

S = Expression { “+” Expression }

Expression = Term { “•” Term }

Term = [ “-” ] Factor

Factor = “x” | “0” | “1” | “(” S “)”
Manchmal verwendet man auch zählende Wiederholungen mit der Bedeutung „…mindestens i und höchstens j mal“, wobei j auch durch einen Stern ersetzt werden kann (für „beliebig mal“). Es gilt und .
Beispiele:

; [a]₂^* = {aa, aaa, aaaa, …}
Syntaxdiagramme

Syntaxdiagramme werden zur anschaulichen Notation von Programmiersprachen verwendet.

Reguläre Ausdrücke

Für reguläre Sprachen gibt es die Möglichkeit, sie durch reguläre Ausdrücke aufzuschreiben. Das sind Ausdrücke, die gebildet sind aus

• 
  der leeren Sprache, die keine Wörter enthält
  
• 
  den Sprachen bestehend aus einem Wort bestehend aus einem Zeichen des Alphabets
  
• 
  der Vereinigung von Sprachen (gekennzeichnet durch +)
  
• 
  Konkatenation (gekennzeichnet durch Hintereinanderschreibung,  oder ;)
  
• 
  beliebiger Wiederholung (gekennzeichnet durch *)
  

Beispiele:

(aa)* (gerade Anzahl von a)

aa* (mindestens ein a, auch a⁺ geschrieben)

((a + b)b)* (jedes zweite Zeichen ist b)

Reguläre Ausdrücke werden z.B. in Editoren verwendet, um bestimmte zu suchende Zeichenreihenmengen zu repräsentieren. Beispiel für eine Suche ist: „Suche eine Zeichenreihe, die mit c beginnt und mit c endet und dazwischen eine gerade Anzahl von a enthält.“

In Groovy sind reguläre Ausdrücke („patterns“) ein fester Bestandteil der Sprache. Sie werden in / … / eingeschlossen, und es gibt vielfältige Operatoren:

==~ prüft ob eine Zeichenreihe in einem regulären Ausdruck enthalten ist

=~ gibt ein Matcher-Objekt

Beispiele:

"aaaa" ==~ /(aa)+/

"abbbab" ==~ /(.b)*/

"..." ==~ /\.*/

"Hallo Welt" ==~ /\w+\s\w+/

["Hut", "Rot", "Rat"].each {assert it ==~ /(H|R)[aeiou]t/}

["cc", "caac", "cabac"].each {assert it ==~ /c[^a]*(a[^a]*a)*[^a]*c/}
Endliche Automaten sind Syntaxdiagramme ohne Abkürzungen, d.h. es gibt keine „Kästchen“. Ein endlicher Automat hat genau einen Eingang und mehrere mögliche Ausgänge.
Beispiele:

Üblicherweise werden bei Automaten die Kreuzungen als Kreise gemalt und Zustände (states) genannt, die Zustände werden mit Pfeilen verbunden (sogenannten Transitionen, transitions), die mit Terminalsymbolen beschriftet sind.

Ein fundamentaler Satz der Theorie der formalen Sprachen besagt, dass mit regulären Ausdrücken genau die durch reguläre Grammatiken definierbaren Sprachen beschrieben werden können, welches wiederum genau die Sprachen sind, die durch endliche Automaten beschrieben werden können.