Grin logo
Go to shop › Computer Science - Theory

Anwendung der kontextfreien Grammatiken in den Compilern und Programmiersprachen

Title: Anwendung der kontextfreien Grammatiken in den Compilern und Programmiersprachen

Presentation slides , 2012 , 9 Pages , Grade: 1,3

Autor:in: M.Sc. Radoslav Yankov (Author)

Computer Science - Theory
Excerpt & Details   Look inside the ebook

Die vorliegende Präsentation behandelt die kontextfreien Grammatiken in Bezug auf ihre Anwendbarkeit in Compilern und Programmiersprachen. Hierfür liefert sie zunächst allgemeine Informationen zu kontextfreien Grammatiken sowie eine Ein- und Abgrenzung dieser, bevor sie sich den Möglichkeiten ihrer praktischen Anwendung zur Beschreibung von Programmiersprachen, im Compilerbau und im Kontext XML/DTD zuwendet.

Excerpt


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)
Excerpt out of 9 pages  - scroll top

Details

Title
Anwendung der kontextfreien Grammatiken in den Compilern und Programmiersprachen
Grade
1,3
Author
Publication Year
2012
Pages
9
Catalog Number
V424126
ISBN (eBook)
9783668700376
ISBN (Book)
9783668700383
Language
German
Tags
anwendung grammatiken compilern programmiersprachen
Quote paper
M.Sc. Radoslav Yankov (Author), 2012, Anwendung der kontextfreien Grammatiken in den Compilern und Programmiersprachen, Munich, GRIN Verlag, https://www.grin.com/document/424126