Kann jemand ein einfaches aber nicht-Spielzeug Beispiel für eine kontextsensitive Grammatik geben?

Question

Ich versuche, kontextsensitive Grammatiken zu verstehen, und ich verstehe, warum Sprachen wie

1. {ww | w ist eine Zeichenfolge}
2. {a n b ⁿ c n | a, b, c sind Symbole}

nicht kontextfrei sind, aber was ich möchte wissen, ob eine Sprache ähnlich das nicht typisierten Lambda-Kalkül kontextsensitiv ist. Ich würde gerne ein Beispiel für eine einfache, aber nicht-Spielzeug (ich betrachte die oben genannten Spielzeug-Beispiele), Beispiel einer kontextsensitiven Grammatik, die, für einige Produktionsregel, z. B. sagen, ob eine Reihe von Symbolen ist derzeit im Umfang (z. B. bei der Herstellung des Körpers einer Funktion). Sind kontextsensitive Grammatiken leistungsfähig genug, um nicht definierte/nicht deklarierte/nicht gebundene Variablen zu syntaktischen (und nicht semantischen) Fehlern zu machen?

Answer 1

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

Ein echtes Beispiel für eine kontextsensitive Sprache ist die C-Programmiersprache. Ein Feature wie deklarieren Variablen zuerst und dann verwenden Sie sie später machen C-Sprache eine context-sensitive language (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 CFG (und nur seinen Parsing-Algorithmus) zur Syntaxprüfung, da wir effiziente Algorithmen zum Parsen von CFG kennen (wenn es sich um eine eingeschränkte Form handelt). Compiler analysieren zuerst eine kontextfreie Funktion und behandeln dann später kontextsensitive Funktionen auf problematische Weise (zum Beispiel werden alle verwendeten Variablen in der Symboltabelle überprüft, wenn sie definiert sind. Andernfalls wird ein Fehler generiert).

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

ich es mit einem albern aber einfaches Beispiel zu erklären versuchen (es ist nur eine Idee, können Sie es verfeinern):

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

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

nun diese Grammatik verwenden, können wir einige richtige Aussagen zu generieren, aber einige sind auch falsch. Zum Beispiel

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

Aber

   Grijesh am  working  [wrong statement] 

Grund: der Wert von < TENSE> hängt von Wert < Nomen> (zB I <TENSE> --> I am) und damit ist die Grammatik nicht korrekte Angaben in der Erzeugung Englische Sprache.

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

_{Sie haben vielleicht bemerkt, dass ein natürlichsprachiger Übersetzer oder Grammatikprüfer nicht richtig funktioniert (versuchen Sie es mit langen Anweisungen).Weil dieses Problem unter den kontextsensitiven Analysealgorithmus fällt.}

---

BEZUG: Sie können Dr. Arun Kumar's lectures beobachten. _{In einigen Vortrag erklärt er genau, was Sie interessiert sind.}