Was sind kontextfreie Grammatiken?

Haben Sie jemals bemerkt, dass beim Schreiben von Code in einem Texteditor wie VS-Code Dinge wie nicht übereinstimmende Klammern erkannt werden? Und es warnt Sie manchmal auch mit einem irritierenden roten Highlight vor der falschen Syntax, die Sie geschrieben haben?

Wenn nicht, dann denke darüber nach. Das ist doch ein Stück Code. Wie können Sie Code für eine solche Aufgabe schreiben? Was wäre die zugrunde liegende Logik dahinter?

Dies sind die Fragen, mit denen Sie konfrontiert werden, wenn Sie einen Compiler für eine Programmiersprache schreiben müssen. Das Schreiben eines Compilers ist keine leichte Aufgabe. Es ist ein sperriger Job, der viel Zeit und Mühe erfordert.

In diesem Artikel werden wir nicht darüber sprechen, wie Compiler erstellt werden. Wir werden jedoch über ein Konzept sprechen, das eine Kernkomponente des Compilers darstellt: kontextfreie Grammatiken.

Einführung

Alle Fragen, die wir zuvor gestellt haben, stellen ein Problem dar, das für das Compiler-Design von Bedeutung ist und als Syntaxanalyse bezeichnet wird. Wie der Name schon sagt, besteht die Herausforderung darin, die Syntax zu analysieren und festzustellen, ob sie korrekt ist oder nicht. Hier verwenden wir kontextfreie Grammatiken. Eine kontextfreie Grammatik ist ein Satz von Regeln, die eine Sprache definieren.

Hier möchte ich zwischen kontextfreien Grammatiken und Grammatiken für natürliche Sprachen wie Englisch unterscheiden.

Kontextfreie Grammatiken oder CFGs definieren eine formale Sprache. Formale Sprachen arbeiten streng nach den definierten Regeln und ihre Sätze werden nicht vom Kontext beeinflusst. Und hier wird der Namenskontext frei .

Sprachen wie Englisch fallen unter die Kategorie der informellen Sprachen, da sie vom Kontext betroffen sind. Sie haben viele andere Merkmale, die ein CFG nicht beschreiben kann.

Obwohl CFGs den Kontext in den natürlichen Sprachen nicht beschreiben können, können sie dennoch die Syntax und Struktur von Sätzen in diesen Sprachen definieren. Dies ist der Grund, warum die CFGs überhaupt erst eingeführt wurden.

In diesem Artikel werden wir versuchen, englische Sätze mit CFGs zu generieren. Wir werden lernen, wie man die Satzstruktur beschreibt und Regeln dafür schreibt. Zu diesem Zweck verwenden wir eine JavaScript-Bibliothek namens Tracery, die Sätze auf der Grundlage von Regeln generiert, die wir für unsere Grammatik definiert haben.

Bevor wir uns mit dem Code befassen und die Regeln für die Grammatik schreiben, wollen wir nur einige grundlegende Begriffe diskutieren, die wir in unserer CFG verwenden werden.

Terminals : Dies sind die Zeichen, aus denen der eigentliche Inhalt des letzten Satzes besteht. Diese können Wörter oder Buchstaben enthalten, je nachdem, welche davon als Grundbaustein eines Satzes verwendet werden.

In unserem Fall werden wir Wörter als Grundbausteine ​​unserer Sätze verwenden. Unsere Terminals werden also Wörter wie "bis", "von", "das", "Auto", "Raumschiff", "Kätzchen" usw. enthalten.

Nicht-Terminals : Diese werden auch als Variablen bezeichnet. Diese fungieren als Subsprache innerhalb der durch die Grammatik definierten Sprache. Nicht-Terminals sind Platzhalter für die Terminals. Wir können Nicht-Terminals verwenden, um verschiedene Muster von Terminalsymbolen zu erzeugen.

In unserem Fall werden wir diese Nicht-Terminals verwenden, um Nominalphrasen, Verbalphrasen, verschiedene Substantive, Adjektive, Verben usw. zu generieren.

Start Symbol : ein Startsymbol ist ein spezieller nicht - Terminal , das die ursprüngliche Zeichenfolge darstellt , die durch die Grammatik generiert werden.

Nachdem wir die Terminologie kennen, lernen wir die grammatikalischen Regeln kennen.

Beim Schreiben von Grammatikregeln definieren wir zunächst die Terminals und einen Startstatus. Wie wir zuvor erfahren haben, ist dieses Startsymbol kein Terminal. Dies bedeutet, dass es zu den Nicht-Terminals gehört.

T: ("Monkey", "banana", "ate", "the") S: Start state. 

Und die Regeln sind:

S --> nounPhrase verbPhrase nounPhrase --> adj nounPhrase | adj noun verbPhrase --> verb nounPhrase adjective --> the noun --> Monkey | banana verb --> ate

Die obigen grammatikalischen Regeln mögen zunächst etwas kryptisch erscheinen. Wenn wir jedoch genau hinschauen, können wir ein Muster erkennen, das aus diesen Regeln generiert wird.

Eine bessere Möglichkeit, über die oben genannten Regeln nachzudenken, besteht darin, sie in Form einer Baumstruktur zu visualisieren. In diesem Baum können wir S in die Wurzel einfügen und nounPhrase und verbPhrase können als untergeordnete Elemente der Wurzel hinzugefügt werden. Genauso können wir auch mit nounPhrase und verbPhrase vorgehen . Der Baum hat Terminals als Blattknoten, da wir hier diese Ableitungen beenden.

Im obigen Bild können wir sehen, dass S (ein Nichtterminal) zwei Nichtterminals NP ( nounPhrase ) und VP ( verbPhrase ) ableitet . Im Fall von NP wurden zwei Nicht-Terminals abgeleitet, Adj und Noun .

Wenn Sie sich die Grammatik ansehen, hätte NP auch Adj und nounPhrase wählen können . Beim Generieren von Text werden diese Auswahlmöglichkeiten zufällig getroffen.

Und schließlich haben die Blattknoten Terminals, die fett gedruckt sind. Wenn Sie sich also von links nach rechts bewegen, können Sie sehen, dass ein Satz gebildet wird.

Der häufig für diesen Baum verwendete Begriff ist ein Analysebaum. Auf ähnliche Weise können wir einen weiteren Analysebaum für einen anderen Satz erstellen, der von dieser Grammatik generiert wird.

Fahren wir nun mit dem Code fort. Wie bereits erwähnt, verwenden wir eine JavaScript-Bibliothek namens Tracery zur Textgenerierung mit CFGs. Wir werden auch Code in HTML und CSS für den Front-End-Teil schreiben.

Der Code

Beginnen wir damit, zuerst die Maßbibliothek zu erhalten. Sie können die Bibliothek hier von GitHub klonen. Ich habe auch den Link zum GitHub-Repository von galaxykate am Ende des Artikels hinterlassen.

Bevor wir die Bibliothek benutzen, müssen wir sie importieren. Wir können dies einfach in einer HTML-Datei wie dieser tun.

Ich habe die geklonte Maßwerkdatei als Skript in meinen HTML-Code eingefügt. Wir müssen auch JQuery zu unserem Code hinzufügen, da das Maßwerk von JQuery abhängt. Schließlich habe ich app.js hinzugefügt , die Datei, in der ich Regeln für die Grammatik hinzufügen werde.

Erstellen Sie anschließend eine JavaScript-Datei, in der wir unsere Grammatikregeln definieren.

var rules = { "start": ["#NP# #VP#."], "NP": ["#Det# #N#", "#Det# #N# that #VP#", "#Det# #Adj# #N#"], "VP": ["#Vtrans# #NP#", "#Vintr#"], "Det": ["The", "This", "That"], "N": ["John Keating", "Bob Harris", "Bruce Wayne", "John Constantine", "Tony Stark", "John Wick", "Sherlock Holmes", "King Leonidas"], "Adj": ["cool", "lazy", "amazed", "sweet"], "Vtrans": ["computes", "examines", "helps", "prefers", "sends", "plays with", "messes up with"], "Vintr": ["coughs", "daydreams", "whines", "slobbers", "appears", "disappears", "exists", "cries", "laughs"] } 

Hier werden Sie feststellen, dass sich die Syntax zum Definieren von Regeln nicht wesentlich von der Definition unserer Grammatik unterscheidet. Es gibt sehr kleine Unterschiede, wie z. B. die Art und Weise, wie Nicht-Terminals zwischen den Hash-Symbolen definiert werden. Und auch die Art und Weise, wie verschiedene Ableitungen geschrieben werden. Anstatt das "|" Symbol für ihre Trennung, hier werden wir alle verschiedenen Ableitungen als verschiedene Elemente eines Arrays setzen. Ansonsten verwenden wir die Semikolons anstelle der Pfeile, um den Übergang darzustellen.

Diese neue Grammatik ist etwas komplizierter als die zuvor definierte. Dieser enthält viele andere Dinge wie Determinatoren, transitive Verben und intransitive Verben. Wir tun dies, um den generierten Text natürlicher aussehen zu lassen.

Rufen wir nun die Maßwerkfunktion "createGrammar" auf, um die soeben definierte Grammatik zu erstellen.

let grammar = tracery.createGrammar(rules);

This function will take the rules object and generate a grammar on the basis of these rules. After creating the grammar, we now want to generate some end result from it. To do that we will use a function called "flatten".

let expansion = grammar.flatten('#start#');

It will generate a random sentence based on the rules that we defined earlier. But let's not stop there. Let's also build a user interface for it. There's not much we will have to do for that part – we just need a button and some basic styles for the interface.

In the same HTML file where we added the libraries we will add some elements.

  Weird Sentences          

Weird Sentences

Give me a Sentence!

And finally we will add some styles to it.

body { text-align: center; margin: 0; font-family: 'Harmattan', sans-serif; } #h1 { font-family: 'UnifrakturMaguntia', cursive; font-size: 4em; background-color: rgb(37, 146, 235); color: white; padding: .5em; box-shadow: 1px 1px 1px 1px rgb(206, 204, 204); } #generate { font-family: 'Harmattan', sans-serif; font-size: 2em; font-weight: bold; padding: .5em; margin: .5em; box-shadow: 1px 1px 1px 1px rgb(206, 204, 204); background-color: rgb(255, 0, 64); color: white; border: none; border-radius: 2px; outline: none; } #sentences p { box-shadow: 1px 1px 1px 1px rgb(206, 204, 204); margin: 2em; margin-left: 15em; margin-right: 15em; padding: 2em; border-radius: 2px; font-size: 1.5em; }

We will also have to add some more JavaScript to manipulate the interface.

let sentences = [] function generate() { var data = { "start": ["#NP# #VP#."], "NP": ["#Det# #N#", "#Det# #N# that #VP#", "#Det# #Adj# #N#"], "VP": ["#Vtrans# #NP#", "#Vintr#"], "Det": ["The", "This", "That"], "N": ["John Keating", "Bob Harris", "Bruce Wayne", "John Constantine", "Tony Stark", "John Wick", "Sherlock Holmes", "King Leonidas"], "Adj": ["cool", "lazy", "amazed", "sweet"], "Vtrans": ["computes", "examines", "helps", "prefers", "sends", "plays with", "messes up with"], "Vintr": ["coughs", "daydreams", "whines", "slobbers", "appears", "disappears", "exists", "cries", "laughs"] } let grammar = tracery.createGrammar(data); let expansion = grammar.flatten('#start#'); sentences.push(expansion); printSentences(sentences); } function printSentences(sentences) { let textBox = document.getElementById("sentences"); textBox.innerHTML = ""; for(let i=sentences.length-1; i>=0; i--) { textBox.innerHTML += "

"+sentences[i]+"

" } }

Once you have finished writing the code, run your HTML file. It should look something like this.

Every time you click the red button it will generate a sentence. Some of these sentences might not make any sense. This is because, as I said earlier, CFGs cannot describe the context and some other features that natural languages possess. It is used only to define the syntax and structure of the sentences.

You can check out the live version of this here.

Conclusion

If you have made it this far, I highly appreciate your resilience. It might be a new concept for some of you, and others might have learnt about it in their college courses. But still, Context Free Grammars have interesting applications that range widely from Computer Science to Linguistics.

I have tried my best to present the main ideas of CFGs here, but there is a lot more that you can learn about them. Here I have left links to some great resources:

  • Context Free Grammars by Daniel Shiffman.
  • Context Free Grammars Examples by Fullstack Academy
  • Tracery by Galaxykate