Anwendung der kontextfreien Grammatiken in den Compilern und Programmiersprachen


Präsentation, 2012

9 Seiten, Note: 1,3


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

Details

Titel
Anwendung der kontextfreien Grammatiken in den Compilern und Programmiersprachen
Note
1,3
Autor
Jahr
2012
Seiten
9
Katalognummer
V424126
ISBN (eBook)
9783668700376
Dateigröße
779 KB
Sprache
Deutsch
Schlagworte
anwendung, grammatiken, compilern, programmiersprachen
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

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Anwendung der kontextfreien Grammatiken in den Compilern und Programmiersprachen



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden