Was ist im Begriff kontextfreie Grammatik wirklich kontextfrei gemeint?

Ich habe eine Weile Compiler studiert und gesucht, was unter "Kontext" in der Grammatik zu verstehen ist und was es bedeutet, dass die Grammatik "kontextfrei" ist, aber ohne Ergebnis.

Kann mir jemand dabei helfen?

terminology context-free formal-grammars Shady Atef
quelle

Was meinst du mit "wirklich"? Welche Erklärungen hast du gelesen und was verstehst du nicht? IIRC, jedes halbwegs anständige Lehrbuch in dieser Angelegenheit wird erklären, was sie bedeuten.

Raphael

Hier ist ein zuordenbares Beispiel. Betrachten Sie das Wort "lesen". Es ist ein einziges Wort, das zwei völlig unterschiedliche Bedeutungen hat. Eine ist die Gegenwart "zu lesen", die andere ist die Vergangenheitsform "ich lese". Wenn Sie das Wort "gelesen" in einem Textstück gesehen haben, können Sie nicht unterscheiden, für welche der beiden Bedeutungen es steht, ohne den Kontext zu betrachten. Englisch ist daher kontextsensitiv, da Sie nicht jedes Token (Wort) analysieren können, ohne es im Kontext zu berücksichtigen. Eine kontextsensitive Grammatik ist eine, bei der die Bedeutung jedes Tokens eindeutig von dem einzelnen Token abgeleitet werden kann, das es darstellt.

Alexander - Wiedereinsetzung von Monica

Antworten:

Der Kontext kann im Hinblick auf die Produktionsregeln erklärt werden, die für verschiedene Grammatiken in der Chomsky-Hierarchie zulässig sind.

Wenn Sie kontextfreie Grammatiken berücksichtigen, haben deren Produktionsregeln die folgende Form:

EIN \to α

$A \rightarrow \alpha$

Sie können also feststellen, dass der linke Teil dieser Art von Regeln nur aus einem nicht-terminalen Symbol besteht. somit findet die Ersetzung des nicht-terminalen Symbols statt, ohne seinen "Kontext" zu berücksichtigen, dh die anderen Symbole, von denen es umgeben ist.

Wenn Sie andererseits Produktionsregeln für kontextsensitive Grammatiken berücksichtigen, haben diese die folgende Form:

β EIN γ \to β α γ

$\beta A \gamma \rightarrow \beta \alpha \gamma$

wobei ein Nicht-Terminal und ist , , sind Sequenzen von Nicht-Terminals und Terminals. $A$ $\alpha$ $\beta$ $\gamma$

In diesem Fall beeinflusst der "Kontext" (dh und ) des zu ersetzenden nicht-terminalen Symbols die Wirkung der Ersetzung und ist Teil der Regel selbst. $\beta$ $\gamma$

Weitere Details finden Sie in dieser Antwort zur Mathematik und in dieser Antwort zur Softwareentwicklung.

PieCot
quelle

Danke für die Antwort. Aber das Merkwürdige für mich ist, dass in der Mathematik SE eine ähnliche Frage gestellt wurde.

Shady Atef

Beachten Sie, dass

und

nicht Teil des Produktionsergebnisses sein müssen. Sie hätten auch durch eine andere Sequenz ersetzt werden können, wie in der Antwort von @David Richerby zu sehen ist.

β

$\beta$

γ

$\gamma$

Frozn

@Frozn AFAIK die hier angegebene ist die Standarddefinition gemäß der Chmosky-Hierarchie. Sicher, es gibt leistungsfähigere Grammatiken als kontextsensitive, die jede Art von Produktion ermöglichen, aber die kontextsensitiven Standardgrammatiken nicht.

Bakuriu

@Frozn: Bakariu hat recht, hier geht es um Grammatiken, die nach der Chomsky-Hierarchie definiert sind, die auf immer restriktiveren Bedingungen für die Produktionsregeln basiert. Insbesondere sind kontextfreie Grammatiken Grammatiken vom Typ 2, während kontextsensitive Grammatiken vom Typ 1 sind. Typ-0-Grammatiken haben jedoch Produktionsregeln, die nicht durch irgendeine Einschränkung beschränkt sind und daher als uneingeschränkte Umschreibungssysteme bezeichnet werden. Hier finden Sie eine kurze Beschreibung der Chomsky-Hierarchie mit einigen Beispielen.

PieCot

β A γ \to δ

$\beta A\gamma \rightarrow \delta$

| β A γ | \leq | δ |

$|\beta A\gamma| \leq |\delta|$

$A\to\text{things}$ $\text{stuff}\,A\,\text{more-stuff}\to\text{things}$ $\mathrm{Expr}$ x:=y+zf(y+z)return y+z

David Richerby
quelle

Im Allgemeinen können sogar reguläre Sprachen Kontextabhängigkeiten aufweisen. Dies bedeutet, dass Sie in gewissem Maße festlegen können, wie Symbole in der Nähe anderer Symbole in einer Zeichenfolge, die zu dieser Sprache gehört, angezeigt werden.

Was für kontextfreie Grammatiken spezifisch ist, ist, dass die Wahl der anzuwendenden Regel niemals von wem abhängt, wenn es mehrere Möglichkeiten gibt, ein Nicht-Terminal-Symbol durch Anwenden verschiedener Regeln mit demselben Nicht-Terminal auf der rechten Seite zu ersetzen wird während des Ableitungsprozesses um dieses Symbol herum ausgeführt.

Sie können sie sich als kontextfreie Ableitungssprachen vorstellen, kurz kontextfreie Sprachen.

André Souza Lemos
quelle