Informatikmaterialien 
von Tino Hempel

Startseite | Informatik | Physik | Mathematik | Sonstiges |


Richard-Wossidlo-Gymnasium Ribnitz-Damgarten
Fachbereich Informatik


Grammatiken


Formale Sprachen können im allgemeinen unendlich viele Objekte enthalten. Um sie zu erfassen/erzeugen benötigt man eine endliche Beschreibungsmöglichkeit. Akzeptoren dienen der Prüfung, Grammatiken der Erzeugung von Sprachen. 

Grammatiken einfacher deutscher Sätze

Durch die Aneinanderreihung von Wörtern ist es möglich, Sätze zu bilden. Diese Satzbildung hat, je nach eingesetzter natürlicher Sprache bestimmte Regeln. 

Beispiel:
1. Wortfolge – kein Satz: Meine am ihren Frau bringt Jungen zu den Samstag Eltern.
2. Wortfolge – ein Satz: Meine Frau bringt den Jungen am Samstag zu ihren Eltern.

Die deutsche Grammatik legt fest, was als Satz zu verstehen ist und zwar wie folgt 
(man lese den Pfeil als "besteht aus" und "|" als "oder"):

<Satz>

   

<Subjekt> <Prädikat> <Objekt>

<Subjekt>

   

<Eigenname> | <Substantivgruppe>

<Substantivgruppe>

   

<Artikel> <Substantiv>

<Prädikat>

   

<Verb>

<Objekt>

   

<Akkusativergänzung>

<Akkusativergänzung>

   

<Substantivgruppe>

Beispiel:
Es wird festgelegt, dass

<Verb>

   

kauft | liebt | liest

<Artikel>

   

die | das | ein

<Substantiv> 

   

Buch | Mädchen | Kartoffeln

<Eigenname>    

   

Peter

Nun lassen sich Sätze bilden, deren Grammatik korrekt ist, wenn auch die Semantik/Pragmatik nicht verständlich .

Beispiele:
die Buch liest die Mädchen.
Peter  liebt das Mädchen 

Analyse der Satzbildung:
In obigen Beispiel wurde nacheinander entsprechend der Grammatik ersetzt und zwar: 

<Satz>

<Subjekt> <Prädikat> <Objekt>

<Substantivgruppe> <Prädikat> <Objekt>

<Artikel> <Substantiv> <Prädikat> <Objekt>

die <Substantiv> <Prädikat> <Objekt>

die Buch <Prädikat> <Objekt>
die Buch <Verb> <Objekt>
die Buch liest <Objekt>
die Buch liest <Akkusativergänzung>
die Buch liest <Substantivgruppe>
die Buch liest <Artikel> <Substantiv>
die Buch liest die <Substantiv>
die Buch liest die Mädchen

Grammatikprüfung in PROLOG

% Quelle: Zimmermann, H.-U.: "Die Implementation kontextfreier Grammatiken in PROLOG".
% In LOG IN 21 (2001) Heft 5/6 S. 68ff.
% Lesehinweise:
% --> besteht aus
% , und
% | oder
% in eckige Klammern immer das konkrete Wort eintragen
% Bezeichner stets mit ''

% Anfrage z. B.: phrase('Satz',[der, hund, jagt, die, katze]).

'Satz' --> 'Subjekt','Praedikat','Objekt'.
'Subjekt' --> 'Artikel','Attribut','Substantiv'.
'Artikel' --> []|[der]|[die]|[das].
'Attribut' --> []|'Adjektiv'|'Adjektiv','Attribut'.
'Adjektiv' --> [kleine]|[bissige]|[grosse].
'Substantiv' --> [hund]|[katze].
'Praedikat' --> [jagt].
'Objekt' --> []|'Artikel','Attribut','Substantiv'.

Grammatiken

Aus den Beispielen folgt, dass man folgendes für eine Grammatik benötigt:

  1. Variable, wie <Satz>, <Substantiv> ... 

  2. Terminale, wie  "die", "Buch", "liebt" ...

  3. Ableitungsregeln der Form linke Seite rechte Seite

  4. Startvariable

Eine Grammatik ist ein 4-Tupel G = (V, T, R, S), das folgende Bedingungen erfüllt:

  • V ist eine endliche Menge, die Menge der Variablen

  • T ist eine endliche Menge, die Menge der Terminale, wobei es keine gemeinsamen Elemente in V und T gibt

  • R ist eine endliche Menge von Ersetzungsregeln (u v), wobei u und v aus beliebig vielen Variablen und Terminalen bestehen und u wenigstens aus einer Variable bestehen muss

  • S V ist eine Startvariable

Beispiel:

G =  (V, T, R, S) mit 
V = {S, B}
T = {ha, !}
R = {S haB, B haB, B !}

Es gilt beispielsweise: S haB hahaB hahahaB hahaha!

Somit erzeugt diese Grammatik die bereits besprochene Lachsprache L = { (ha)n! | n > 0}.

Es sei G = (V, T, R, S) eine beliebige Grammatik. 
Dann ist L(G) = {w T*} die von G durch Anwendung der Regeln R aus der Startvariablen S abgeleiten Wörter w.

Beispiel: 
Gesucht ist eine Grammatik, die für die Klammersetzung genutzt werden kann, 
d. h., die Sprache L = {ab,aabb, aaabbb, ...} = {anbn | n > 0} erzeugt, wobei für a das Symbol "(" und für b das Symbol ")" verwendet werden kann.

G =  (V, T, R, S) mit 
V = {S}
T = {ab}
R = { S ab, S aSb}

Es gilt beispielsweise: S aSb aaSbb aaaSbbb aaaabbbb

Zur Veranschaulichung der Entstehung von Wörtern, benutzt man 

 

Übungen

  1. Man gebe den Ableitungsbaum und Syntax-Graph für die Lachgrammatik und die Grammatik der deutschen Sprache an.

  2. Man entwickle eine Grammatik, die die Sprache L = {a bn c | n > 0} erzeugt.

  3. Man entwickle eine Grammatik, die die Sprache L = {anbncn | n > 0} erzeugt.



zur Startseite
© Tino Hempel 1997 - 2007
Im Web vertreten seit 1994.
Eine Internet-Seite aus dem Angebot von Tino Hempel