Chomsky-Hierarchie

Die Chomsky-Hierarchie geht zurück auf den Sprachwissenschaftler Noam Chomsky, der diese 1956 begründete. Dabei definierte Chomsky eine Hierarchie von vier Typen formaler Grammatiken, die formale Sprachen erzeugen. Der ursprüngliche Aspekt von Chomsky für diese Arbeit war es, eine mathematische Beschreibungsform für die natürliche Sprache zu finden.


Das Wesentliche der Chomsky-Hierarchie ist es, dass ausgehend von einer nicht eingeschränkten grundlegenden Grammatik (der Typ-0-Grammatik) Einschränkungen hinsichtlich der für den Typ zu verwendenden Produktionsregeln gemacht werden. Die Typ-1-Grammatik ist damit eine Untermenge der Typ-0-Grammatik, die Typ-2-Grammatik eine Untermenge der Typ-1-Grammatik und letztendlich die Typ-3-Grammatik ein Spezialfall der Typ-2-Grammatik. In der Informatik werden vor allem Typ-1- und Typ-2-Sprachen u.a. im Compilerbau verwendet.

Auf der Grundlage der Definition der Äquivalenz von Grammatiken und der Hierarchie der Chomsky-Grammatiken ist somit eine Systematisierung der formalen Sprachen möglich. Eine Grammatik ist ein endliches System von Regeln. Es gestattet, die im Allgemeinen unendliche Menge von Sätzen einer formalen Sprache zu erzeugen (generative Grammatik) und zu erkennen (analysierende Grammatik). Weiterhin wird durch dieses System grammatikalischer Regeln für die Sätze der Sprache eine syntaktische Struktur festgelegt, die benötigt wird, um in geeigneter Weise eine Zuordnung zwischen Syntax und Semantik während der Programmübersetzung aufzubauen. Das grundlegende Grammatik-Modell geht auf Noam Chomsky zurück, der es ursprünglich benutzte, um syntaktische Eigenschaften der natürlichen Sprache zu beschreiben.

Das Chomsky-Modell

Es zeigte sich, dass Programmiersprachen besser einer theoretischen, formalisierten Behandlung zu unterziehen sind als die natürlichen Sprachen, da die die strukturellen Eigenschaften der Programmiersprachen wesentlich einfacher sind. Das Chomsky-Modell hat sich in der Theorie der Programmier-sprachen als grundlegendes Modell bewährt. Es gibt eine große Zahl von Veröffentlichungen zu den Grammatiken. Das ursprüngliche Grammatik-Modell wurde nach den verschiedensten Gesichtspunkten verfeinert und erweitert, zum Beispiel zu zweistufigen Grammatiken. Neben ihrer theoretischen Bedeutung sind die Modelle der Chomsky-Grammatiken wichtige praktische Werkzeuge zur Definition von Programmier-sprachen und eine Grundlage der Entwicklungen im Compilerbau, da die Eigenschaften der verwendeten Grammatiken wesentlichen Einfluss auf den Aufbau des Syntaxanalyse-Teils und die Ankopplung der Semantik haben.

Formal ausgedrückt lässt sich dafür folgender Satz festschreiben:

Eine Sprache L heißt vom Chomsky-Typ i (i=0,1,2,3), wenn es mindestens eine Grammatik G(i) vom Chomsky-Typ i gibt, die L erzeugt. Die Chomsky-Hierarchie klassifiziert die Grammatiken in vier Typen :

Typ-0-Grammatik stellt den allgemeinsten Fall dar. Die Regeln unterliegen keinen weiteren Einschränkungen. Dieses Modell ist so allgemein, dass es nicht als sinnvolles Beschreibungsmittel für Programmiersprachen dienen kann.

Typ-1-Grammatik wird als kontextsensitive Grammatik bezeichnet. Grammatiken vom Chomsky-Typ-1 erzeugen Sprachen, für die in endlicher Zeit entschieden werden kann, ob eine beliebige Zeichenreihe Satz der Sprache ist oder nicht.

Typ-2-Grammatik wird als kontextfreie Grammatik bezeichnet. Programmiersprachen können in wesentlichen syntaktischen Eigenschaften durch kontextfreie Grammatiken beschrieben werden.

Typ-3-Grammatik wird als reguläre Grammatik bezeichnet und legt die stärksten Einschränkungen für den Aufbau der Regeln fest. Jede Typ-3-Grammatik erzeugt eine reguläre Sprache. Alle regulären Sprachen sind zugleich kontextabhängige Sprachen. Jede Ableitung einer Produktionsregel wird nur durch die unmittelbar vorausgegangene bedingt. Der Zusammenhang zur Arbeitsweise endlicher, abstrakter Automaten ist offenkundig, so dass Typ-3-Grammatiken häufig zur Definition der lexikalischen Struktur von Programmiersprachen genutzt werden.

Mit zunehmender Höhe der Typnummer werden die Strukturen der entsprechenden Sprachen ärmer. Die Typeinteilung ist nicht nur von technischem Belang, sondern stellt auch eine Abstufung in der Komplexität der Sprachen dar. Auf Typ-2-Sprachen basieren die Backus-Naur-Form und die Syntaxdiagramme zur Definition von Programmiersprachen.

Informationen zum Artikel
Deutsch: Chomsky-Hierarchie
Englisch:
Veröffentlicht: 29.10.2013
Wörter: 597
Tags: #Entwicklung, Codierung
Links: Äquivalenz, Aspekt, BNF (Backus-Naur-Form), Compilerbau, Formale Sprache