Leseprobe
2
Allgemeines und Geschichte
Allgemeines und Geschichte
Die vier Grammatiktypen im Überblick in Form einer Tabelle
Die vier Grammatiktypen im Überblick in Form einer Tabelle
Grammatik
Typ-0
Beliebige formale Grammatik
Regeln
V* \ *, V*
Sprachen
Rekursiv aufzählbar
Entscheidbarkeit
-
Allgemeines und Geschichte
Allgemeines und Geschichte
Grammatik
Typ-1
kontextsensitive Grammatik
Regeln
A
A N; , V*; V
+
S ist erlaubt, wenn es keine
Regel S in P gibt
Sprachen
kontextsensitiv
Entscheidbarkeit
Wortproblem
3
Allgemeines und Geschichte
Allgemeines und Geschichte
Grammatik
Typ-2
kontextsensitive Grammatik
Regeln
A
A N; V*
Sprachen
kontextfrei
Entscheidbarkeit
Wortproblem, Leerheitsproblem
Allgemeines und Geschichte
Allgemeines und Geschichte
Grammatik
Typ-3
Reguläre Grammatik
Regeln
S
A B (rechtsregulär) oder
A B (linksregulär)
A
A
A,B N;
Sprachen
regulär
Entscheidbarkeit
Wortproblem, Leerheitsproblem,
Äquivalenzproblem,
Mehrdeutigkeitsproblem
4
Allgemeines und Geschichte
Allgemeines und Geschichte
Die kontextfreien Grammatiken (kfG)
Die kontextfreien Grammatiken (kfG)
sind eine Teilklasse der Chomsky-Grammatiken, die Noam
Chomsky in den 1950er Jahren ursprünglich zur Beschreibung
natürlicher Sprachen eingeführt hat
sind eine Teilklasse der Chomsky-Grammatiken, die Noam
Chomsky in den 1950er Jahren ursprünglich zur Beschreibung
natürlicher Sprachen eingeführt hat
formalisieren die Syntax von Programmier- und Markup-Sprachen
(wie z.B. Java, C, HTML)
formalisieren die Syntax von Programmier- und Markup-Sprachen
(wie z.B. Java, C, HTML)
dienen als Eingabe für Parsergeneratoren (z.B. Yacc oder JavaCC)
dienen als Eingabe für Parsergeneratoren (z.B. Yacc oder JavaCC)
beschreiben den strukturellen Aufbau von Dokumenten
beschreiben den strukturellen Aufbau von Dokumenten
Definition der kontextfreien Grammatiken
Definition der kontextfreien Grammatiken
Die kfG sind solche Grammatiken, deren Produktionsregeln der
Form Xu sind
Die kfG sind solche Grammatiken, deren Produktionsregeln der
Form Xu sind
identisch mit den Typ-2-Grammatiken der Chomsky-Hierarchie
identisch mit den Typ-2-Grammatiken der Chomsky-Hierarchie
Eine kontextfreie Grammatik G ist ein 4-Tupel (N,T,P,S)
Eine kontextfreie Grammatik G ist ein 4-Tupel (N,T,P,S)
N-Menge der Nichtterminale
T-Menge der Terminale, /N und T endliche disjunkte Mengen/
P-Menge der Produktionen, wobei P N×(N T)
*
S-Startsymbol, wobei S N
N-Menge der Nichtterminale
T-Menge der Terminale, /N und T endliche disjunkte Mengen/
P-Menge der Produktionen, wobei P N×(N T)
*
S-Startsymbol, wobei S N
Eine Regel (a,b) P wird in der Form ab notiert
Eine Regel (a,b) P wird in der Form ab notiert
Die kontextfreien Grammatiken erzeugen genau die kontextfreien
Sprachen
Die kontextfreien Grammatiken erzeugen genau die kontextfreien
Sprachen
5
Beispiel
Beispiel
Sei G = (N,T,P,S) eine kontextfreie Grammatik mit:
T = {x,y,z}
N = {S,A,B}
P enthält 4 Produktionen bzw. Produktionsregeln:
S A
A xAy
A xBy
B z
Sei G = (N,T,P,S) eine kontextfreie Grammatik mit:
T = {x,y,z}
N = {S,A,B}
P enthält 4 Produktionen bzw. Produktionsregeln:
S A
A xAy
A xBy
B z
Praktische Anwendung der kfG
Praktische Anwendung der kfG
Zur Beschreibung von Programmiersprachen
Zur Beschreibung von Programmiersprachen
im Compilerbau
im Compilerbau
Extensible Markup Language (XML) und
Dokumenttypdefinitionen (DTD)
Extensible Markup Language (XML) und
Dokumenttypdefinitionen (DTD)
Ende der Leseprobe aus 9 Seiten
- Arbeit zitieren
- M.Sc. Radoslav Yankov (Autor), 2012, Anwendung der kontextfreien Grammatiken in den Compilern und Programmiersprachen, München, GRIN Verlag, https://www.grin.com/document/424126
Ähnliche Arbeiten
Kostenlos Autor werden
Kommentare