Kann jemand ein einfaches, aber nicht spielerisches Beispiel für eine kontextsensitive Grammatik geben?

12

Ich versuche, kontextsensitive Grammatiken zu verstehen.

Ich verstehe, warum Sprachen mögen

$\{ww \mid w \in A^*\}$

$\{a^n b^n c^n \mid n\in\mathbb{N}\}$

sind nicht kontextfrei, aber was würde ich gerne wissen, wenn eine Sprache, die der untypisierten Lambda-Rechnung ähnelt, kontextsensitiv ist?

Ich würde gerne ein Beispiel für ein einfaches, aber nicht-spielerisches Element sehen (ich betrachte die obigen spielerischen Beispiele), ein Beispiel für eine kontextsensitive Grammatik, die für einige Produktionsregeln, z befindet sich derzeit im Geltungsbereich (z. B. beim Erstellen des Hauptteils einer Funktion).

Sind kontextsensitive Grammatiken leistungsfähig genug, um undefinierte / nicht deklarierte / ungebundene Variablen zu einem syntaktischen (und nicht zu einem semantischen) Fehler zu machen?

formal-grammars programming-languages lambda-calculus context-sensitive BlueBomber
quelle

1

Fast alle realen Programmiersprachen sind kontextsensitiv (im allgemeinen Sinne, dh, sie verschmelzen sowohl Chomsky-Typ-0- als auch Typ-I-Grammatiken unter "kontextsensitiv"). Beispielsweise müssen Variablen deklariert werden, bevor sie verwendet werden. Bezeichner sollten eindeutig sein. Alle diese erfordern Kontext (st wird als semantischer Kontext bezeichnet, kann jedoch irreführend sein). Cs.purdue.edu/homes/hosking/502/notes/04-semantics.pdf

Nikos M .

Nun, "kontextsensitiv" ist der Standardbegriff für Typ-1-Grammatiken.

Reinierpost

8

Ja, ich würde dies für möglich halten, aber nein, ich bin nicht bereit, diese kontextsensitive Grammatik explizit zu konstruieren. Ich werde meine Antwort erklären, indem ich die Frage in zwei Teile aufteile.

(1) Was wäre das Nichtspielzeugbeispiel? Es sollte die Deklaration von Variablen widerspiegeln. Mein Vorschlag für eine solche Sprache, die von der realen Programmierung abstrahiert ist, wäre ungefähr so. Das Alphabet ist . $\{a,b,;,(,)\}$ Diese Sprache ist kontextsensitiv.

{w_{1}; w_{2}; \dots; w_{n} (x_{1}; x_{2}; \dots; x_{m}) ∣ w_{i}, x_{j} \in {a, b}^{*}, each x_{j} is equal to some w_{i}}

$\{ w_1;w_2;\dots;w_n(x_1;x_2;\dots;x_m) \mid w_i,x_j\in\{a,b\}^*, \mbox{ each }x_j\mbox{ is equal to some }w_i \}$

(2) Um es zu zeigen , tatsächlich ist kontextsensitive ich einen anderen Formalismus verwenden würde. Das einer Turingmaschine mit linearer Verwendung ihres Bandes: ein linear begrenzter Automat LBA. Ich kann es so programmieren, dass es das Pattern Matching ausführt. Ich würde jedes nacheinander betrachten und versuchen, es Buchstabe für Buchstabe mit einem richtigen abzugleichen. LBAs entsprechen kontextsensitiven Grammatiken, sind jedoch viel einfacher zu programmieren. $x_j$ $w_j$

Hendrik Jan
quelle

Danke für den Beitrag. Mit LBAs bin ich derzeit weniger vertraut, daher bin ich mit Punkt (2) weniger überzeugt. Ab Punkt (1) versuche ich zu sehen, wie Regeln erstellt werden, mit denen ein Variablenname als Ausdruck erwartet wird, nur eine der Variablen im aktuellen Bereich. Ich brauche keine ganze, formelle CSG, aber eine informelle Erklärung würde funktionieren. Ich kann mir nicht vorstellen, wie man das mit Variablennamen mit mehreren Symbolen macht, was eine andere Verwendung des Kontexts ist als z.

{w w ∣ w \dots}

$\{ ww \mid w\dots\}$

{w w | w . . .}

$\{ww | w ... \}$

3

{w w}

$\{ ww \}$

L R

$LR$

L w R w

$LwRw$

L

$L$

a

$a$

M_{a}

$M_a$

w

$w$

M_{a} b \to b M_{a}

$M_ab \to bM_a$

R

$R$

M_{a} R \to R a

$M_aR \to Ra$

13

$[n]$

Viele andere NP-harte Sprachen sind aus demselben Grund auch in CSL enthalten, wie z. B. CLIQUE.

Es gibt auch ziemlich natürliche Sprachen in CSL, die noch schwieriger sind.

Mir ist jedoch keine Möglichkeit bekannt, eine beliebige CSL als kontextsensitive Grammatik (CSG) auszudrücken, außer Landwebers Konstruktion in Satz 3 seines Aufsatzes zu verwenden. In dieser Konstruktion beschreibt die CSG die Umkehrung der Funktionsweise des linear begrenzten Automaten, der die CSL erkennt. Produktionen des CSG beschreiben, wie ein bestimmter Zustand der Maschine aus einer möglichen Bewegung resultiert. Eine solche CSG ist eine einfache Übersetzung des Automaten in eine Grammatik. Sie entspricht also nicht unbedingt Sprachmerkmalen wie der Möglichkeit, Variablen zu deklarieren, sondern wird durch die Details des Automaten blockiert.

Wenn Sie eher auf einer CSG als auf einer CSL bestehen und Ihre eigentliche Frage darin besteht, eine CSG für eine Sprache mit eingeschränktem Variablenumfang anzeigen zu wollen, ist die Antwort von Hendrik Jan anscheinend ein guter Anfang.

András Salamon
quelle

9

Ja, kontextsensitive Grammatiken (CSG) sind leistungsfähig genug, um undefinierte / nicht deklarierte / ungebundene Variablen zu überprüfen, aber leider kennen wir keinen effizienten Algorithmus zum Parsen von CSG-Zeichenfolgen.

Ein echtes Beispiel für eine kontextsensitive Sprache ist die Programmiersprache C. Eine Funktion wie zuerst Variablen deklarieren und später verwenden macht C-Sprache zu einer kontextsensitiven Sprache (CSL). ( Ich weiß nicht über untypisierte Lambda-Kalkül ).

Und weil wir keinen linearen Parsing-Algorithmus für CSL (oder CSG) kennen. Aus diesem Grund verwenden wir im Compiler-Design nur CFG (und dessen Parsing-Algorithmus) für die Syntaxprüfung, da wir effiziente Algorithmen zum Parsen von CFG kennen (wenn es in eingeschränkter Form vorliegt). Compiler analysieren zuerst ein kontextfreies Feature und behandeln dann später kontextsensitive Features auf problematische Weise (überprüfen Sie beispielsweise alle verwendeten Variablen in der Symboltabelle, falls sie definiert sind. Andernfalls wird ein Fehler generiert).

Auch die kontextsensitive Grammatik wird in der Verarbeitung natürlicher Sprache (NLP) verwendet. Und die meisten natürlichen Sprachen sind Beispiele für kontextsensitive Sprachen. (Ich bin nicht sicher für die Sanskrit- Sprache).

Ich werde versuchen, es mit einem albernen, aber einfachen Beispiel zu erklären (es ist nur eine Idee, Sie können es verfeinern):

NOUN     -->  { BlueBomber, Grijesh, I, We}
TENSE    -->  { am, was, is, were}
VERB     -->  { going, eating, working}

SENTENCE --> <NOUN> <TENSE> <VERB>

Mit dieser Grammatik können wir nun einige korrekte Aussagen erzeugen, aber einige sind auch falsch. Beispielsweise,

SENTENCE --> <NOUN>   <TENSE>   <VERB>
             Grijesh    is       working       [Correct statement]

Aber

             Grijesh    am       working       [wrong statement]

Grund: Der Wert von <TENSE> hängt (zum Beispiel I <TENNSE> --> I am) vom Wert <NOUN> ab, und daher generiert die Grammatik keine korrekten Aussagen in der englischen Sprache.

Eigentlich können wir keine kontextfreie Grammatik für komplettes Englisch schreiben!

_{Möglicherweise haben Sie bemerkt, dass ein Übersetzer oder eine Grammatikprüfung für natürliche Sprachen nicht ordnungsgemäß funktioniert (versuchen Sie es mit langen Anweisungen). Weil dieses Problem unter den kontextsensitiven Parsing-Algorithmus fällt.}

VERWEIS : Sie können die Vorträge von Dr. Arun Kumar ansehen . _{In einem Vortrag erklärt er genau, woran Sie interessiert sind.}

Grijesh Chauhan
quelle

Vielen Dank für die Informationen. Sie sind zweifellos hilfreich für andere, die sich für dasselbe Thema interessieren. Sie stehen jedoch nur teilweise im Zusammenhang mit den Fragen, die ich gestellt habe. Ich beschäftige mich nicht mit dem Parsen einer von einer CSG generierten Zeichenfolge, sondern mit einem einfachen - sogar albernen - Beispiel einer formalen CSG, die wohlgeformte Abstraktionen generiert (keine ungebundenen Variablen innerhalb des Funktionskörpers). Ich kann mir vorstellen, dass eine CSG korrekte "englische" Zeichenfolgen generiert, da ein einzelnes Symbol die Übereinstimmung zwischen Subjekt und Verb bestimmen kann, aber bei Abstraktionen bestehen Variablen normalerweise aus mehreren Symbolen.

1

@BlueBomber: dankeIch werde dir sicher antworten, Seine Nacht in Indien..N Frohes neues Jahr! :)

Grijesh Chauhan

Es scheint, dass ich das nur eine begrenzte Anzahl von Malen tun kann, und laut (this) [ meta.scicomp.stackexchange.com/questions/156/… sollte ich diese Frage löschen und an der angemesseneren Stelle erneut posten ...

@BlueBomber Ich habe markiert, um zu verschieben, können Sie auch tun.

Grijesh Chauhan

1

(Kommentare in Antwort erweitern)

Ich bin mir sowieso nicht sicher, ob dies ein Beispiel ist, das Sie gerne hätten.

Fast alle realen Programmiersprachen sind kontextsensitiv (im allgemeinen Sinne, conflating dh sowohl Chomsky Typ 0 und Typ-I - Grammatiken unter „kontextsensitive“, das stimmt natürlich ist seit uneingeschränkte Grammatiken sind noch kontextsensitiver als Kontext -sensitive Grammatiken).

Zum Beispiel "Variablen müssen deklariert werden, bevor sie verwendet werden", "Bezeichner müssen eindeutig sein", alle diese benötigen Kontext (manchmal als semantischer Kontext bezeichnet, was jedoch irreführend sein kann, da es sich ohnehin um syntaktische Funktionen handelt), siehe zum Beispiel https: // www .cs.purdue.edu / homes / hosking / 502 / notes / 04-semantics.pdf

Das Gefühl, dass die obigen Beispiele kontextsensitiv sind (sowohl im grammatikalischen / syntaktischen als auch im semantischen Sinne), besteht darin, dass sie über ihren Kontext sprechen (was vorhergeht oder danach kommt).

Eine "bereits definierte Variable" ist über den Kontext vor einer Variablenverwendung zu verstehen . Ein "eindeutiger Bezeichner" ist der Kontext zu dem, was vor oder nach einer Bezeichnerdeklaration steht, und so weiter.

Siehe auch Ist JavaScript eine kontextfreie Sprache? auf SO

Nikos M.
quelle

"Kontextsensitiv" bedeutet Typ 1.

Reinierpost

Kann jemand ein einfaches, aber nicht spielerisches Beispiel für eine kontextsensitive Grammatik geben?

Antworten: