Kontextfreie Sprachen und Kellerautomaten

Kontextfreie Grammatiken erzeugen Sprachen mit verschachtelter, rekursiver Struktur, und Kellerautomaten erkennen genau diese Sprachen, indem sie eine endliche Steuerung mit einem unbegrenzten Stack erweitern.

Definition

Eine kontextfreie Sprache wird durch eine Grammatik erzeugt, deren Regeln ein einzelnes nicht-terminales Symbol unabhängig vom Kontext umschreiben, und sie wird von einem Kellerautomaten erkannt, einem endlichen Automaten, der mit einem Stack ausgestattet ist, der einen Last-in-First-out-Speicher von unbegrenzter Tiefe bereitstellt.

Scope

Dieses Thema behandelt kontextfreie Grammatiken und Ableitungen, Ableitungsbäume und Ambiguität, die Äquivalenz von kontextfreien Grammatiken mit Kellerautomaten, Normalformen wie die Chomsky-Normalform, das Pumping-Lemma für kontextfreie Sprachen sowie die Abschluss- und Entscheidungseigenschaften, die diese Klasse von den regulären Sprachen unterscheiden.

Core questions

• Welche Arten von verschachtelten oder rekursiven Mustern erfordern einen Stack anstelle eines endlichen Speichers?
• Warum sind kontextfreie Grammatiken und Kellerautomaten in ihrer Leistungsfähigkeit äquivalent?
• Wann ist eine Grammatik mehrdeutig, und warum ist Mehrdeutigkeit für das Parsen relevant?
• Welche Entscheidungsprobleme für kontextfreie Sprachen sind lösbar und welche nicht?

Key theories

Grammatik-Automat-Äquivalenz

Eine Sprache ist genau dann kontextfrei, wenn sie von einem Kellerautomaten akzeptiert wird, sodass die Sichtweise der generativen Grammatik und die Sichtweise der Stack-Maschine dieselbe Sprachklasse beschreiben.

Chomsky-Normalform

Jede kontextfreie Grammatik kann so umgeschrieben werden, dass jede Regel entweder zwei Nicht-Terminale oder ein einzelnes Terminal erzeugt, eine Normalform, die Parsing-Algorithmen und induktiven Beweisen über die Klasse zugrunde liegt.

Pumping-Lemma für kontextfreie Sprachen

Jede ausreichend lange Zeichenkette in einer kontextfreien Sprache kann so aufgeteilt werden, dass zwei ihrer Teile zusammen „gepumpt“ werden können, eine Eigenschaft, die für Sprachen, die mehr als Stack-Speicher benötigen, nicht zutrifft und diese somit als nicht-kontextfrei erweist.

Clinical relevance

Kontextfreie Grammatiken spezifizieren die Syntax nahezu jeder Programmiersprache und vieler Datenformate, und Parsing-Algorithmen im Kellerautomaten-Stil verwandeln diese Grammatiken in die syntaktischen Analysatoren, die das Herzstück von Compilern und Interpretern bilden, wodurch dieses Thema die theoretische Grundlage der Programmiersprachenverarbeitung darstellt.

History

Chomsky führte kontextfreie Grammatiken in den späten 1950er Jahren als Teil seiner Hierarchie ein, und sie wurden unabhängig voneinander von Backus und Naur verwendet, um die Syntax der Programmiersprache ALGOL zu definieren. Die Äquivalenz mit Kellerautomaten und die strukturelle Theorie der Klasse wurden in den 1960er Jahren ausgearbeitet.

Key figures

• Noam Chomsky
• John Backus
• Seymour Ginsburg
• Sheila Greibach

Seminal works

• sipser2013
• hopcroft2006

Frequently asked questions

Warum benötigt das Parsen einer Programmiersprache einen Stack?

Programme enthalten verschachtelte Konstrukte wie Klammern, Blöcke und Funktionsaufrufe, deren Verschachtelungstiefe unbegrenzt ist. Ein Stack speichert jedes unvollendete Konstrukt und entfernt es, wenn es geschlossen wird, was genau die Speicherdisziplin ist, die ein Kellerautomat bietet und einem endlichen Automaten fehlt.

Was bedeutet es, wenn eine Grammatik mehrdeutig ist?

Eine Grammatik ist mehrdeutig, wenn eine Zeichenkette mehr als einen Ableitungsbaum hat, was bedeutet, dass sie mit tatsächlich unterschiedlichen Strukturen abgeleitet werden kann. Mehrdeutigkeit ist für Programmiersprachen unerwünscht, da sie die Bedeutung des Codes unklar lässt, daher streben Sprachdesigner eindeutige Grammatiken an oder fügen Regeln zur Mehrdeutigkeitsauflösung hinzu.