Hvad er kontekstfri grammatikker?

Har du nogensinde bemærket, at når du skriver kode i en teksteditor som VS-kode, genkender den ting som umatchede seler? Og det advarer dig undertiden også med en irriterende rød fremhævning om den forkerte syntaks, du har skrevet?

Hvis ikke, så tænk over det. Det er trods alt et stykke kode. Hvordan kan du skrive kode til en sådan opgave? Hvad ville være den bagvedliggende logik bag den?

Dette er de slags spørgsmål, som du vil stå over for, hvis du skal skrive en kompilator til et programmeringssprog. At skrive en kompilator er ikke en let opgave. Det er klodsede job, der kræver en betydelig mængde tid og kræfter.

I denne artikel vil vi ikke tale om, hvordan man bygger kompilatorer. Men vi vil tale om et koncept, der er en kernekomponent i compileren: Context Free Grammars.

Introduktion

Alle de spørgsmål, vi stillede tidligere, repræsenterer et problem, der er vigtigt for kompilerdesign kaldet syntaksanalyse. Som navnet antyder, er udfordringen at analysere syntaksen og se, om den er korrekt eller ej. Det er her, vi bruger kontekstfrie grammatikker. En kontekstfri grammatik er et sæt regler, der definerer et sprog.

Her vil jeg gerne skelne mellem kontekstfri grammatik og grammatik for naturlige sprog som engelsk.

Kontekstfri grammatik eller CFG definerer et formelt sprog. Formelle sprog fungerer strengt under de definerede regler, og deres sætninger påvirkes ikke af sammenhængen. Og det er her, det får navnet kontekst gratis .

Sprog som engelsk falder ind under kategorien uformelle sprog, da de påvirkes af kontekst. De har mange andre funktioner, som en CFG ikke kan beskrive.

Selvom CFG'er ikke kan beskrive konteksten på de naturlige sprog, kan de stadig definere syntaks og struktur af sætninger på disse sprog. Faktisk er det grunden til, at CFG'erne først blev introduceret.

I denne artikel vil vi forsøge at generere engelske sætninger ved hjælp af CFG'er. Vi lærer at beskrive sætningsstrukturen og skrive regler for den. For at gøre dette bruger vi et JavaScript-bibliotek kaldet Tracery, der genererer sætninger på basis af regler, vi definerede for vores grammatik.

Før vi dykker ned i koden og begynder at skrive reglerne for grammatikken, lad os bare diskutere nogle grundlæggende udtryk, som vi vil bruge i vores CFG.

Terminaler : Dette er de tegn, der udgør det faktiske indhold af den sidste sætning. Disse kan omfatte ord eller bogstaver afhængigt af hvilken af ​​disse der bruges som den grundlæggende byggesten i en sætning.

I vores tilfælde bruger vi ord som de grundlæggende byggesten i vores sætninger. Så vores terminaler inkluderer ord som "til", "fra", "den", "bil", "rumskib", "killinger" og så videre.

Ikke terminaler : Disse kaldes også variabler. Disse fungerer som et undersprog inden for det sprog, der er defineret af grammatikken. Ikke-terminaler er pladsholdere for terminalerne. Vi kan bruge ikke-terminaler til at generere forskellige mønstre af terminalsymboler.

I vores tilfælde bruger vi disse ikke-terminaler til at generere substantivudsætninger, verbsætninger, forskellige substantiver, adjektiver, verb og så videre.

Start-symbol : et startsymbol er en særlig ikke-terminal, der repræsenterer den indledende streng, der genereres af grammatikken.

Nu hvor vi kender terminologien, lad os begynde at lære om de grammatiske regler.

Mens vi skriver grammatikregler, starter vi med at definere sæt terminaler og en starttilstand. Som vi lærte før, er startsymbolet et ikke-terminal. Dette betyder, at det vil tilhøre sættet af ikke-terminaler.

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

Og reglerne er:

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

Ovenstående grammatiske regler kan i første omgang virke noget kryptiske. Men hvis vi ser nøje, kan vi se et mønster, der genereres ud af disse regler.

En bedre måde at tænke på ovenstående regler er at visualisere dem i form af en træstruktur. I det træ kan vi sætte S i roden og substantivPhase og verbPhrase kan tilføjes som børn af roden. Vi kan fortsætte på samme måde med substantivPhrase og verbPhrase også. Træet har terminaler som bladnoder, fordi det er her, vi afslutter disse afledninger.

I ovenstående billede kan vi se, at S (en ikke-terminal) stammer fra to ikke-terminaler NP ( nounPhrase ) og VP ( verbPhrase ). I tilfælde af NP har den afledt to ikke-terminaler, Adj og Substantiv .

Hvis du ser på grammatikken, kunne NP også have valgt Adj og nounPhrase . Mens der genereres tekst, foretages disse valg tilfældigt.

Og til sidst har bladknudepunkterne terminaler, der er skrevet med fed skrift. Så hvis du bevæger dig fra venstre mod højre, kan du se, at der dannes en sætning.

Udtrykket, der ofte bruges til dette træ, er et parse-træ. Vi kan oprette et andet parse-træ til en anden sætning genereret af denne grammatik på en lignende måde.

Lad os nu gå videre til koden. Som jeg nævnte tidligere, bruger vi et JavaScript-bibliotek kaldet Tracery til tekstgenerering ved hjælp af CFG'er. Vi vil også skrive noget kode i HTML og CSS til frontend-delen.

Koden

Lad os starte med først at få tracery-biblioteket. Du kan klone biblioteket fra GitHub her. Jeg har også forladt linket til GitHub-arkivet med galaxykate i slutningen af ​​artiklen.

Før vi bruger biblioteket, bliver vi nødt til at importere det. Vi kan gøre dette simpelthen i en HTML-fil som denne.

Jeg har tilføjet den klonede tracery-fil som et script i min HTML-kode. Vi bliver også nødt til at tilføje JQuery til vores kode, fordi tracery afhænger af JQuery. Endelig har jeg tilføjet app.js, som er den fil, hvor jeg vil tilføje regler for grammatikken.

Når det er gjort, skal du oprette en JavaScript-fil, hvor vi definerer vores grammatikregler.

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"] } 

Her vil du bemærke, at syntaksen for at definere regler ikke er meget forskellig fra, hvordan vi definerede vores grammatik tidligere. Der er meget mindre forskelle, såsom den måde, hvorpå ikke-terminaler defineres mellem hash-symbolerne. Og også den måde, hvorpå forskellige afledninger skrives. I stedet for at bruge "|" symbol for at adskille dem, her sætter vi alle de forskellige afledninger som forskellige elementer i en matrix. Bortset fra det, bruger vi semikolonerne i stedet for pilene til at repræsentere overgangen.

Denne nye grammatik er lidt mere kompliceret end den, vi definerede tidligere. Denne indeholder mange andre ting, såsom Determiners, Transitive Verbs og Intransitive Verbs. Vi gør dette for at få den genererede tekst til at se mere naturlig ud.

Lad os nu kalde tracery-funktionen "createGrammar" for at oprette den grammatik, vi lige har defineret.

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 af Daniel Shiffman.
  • Eksempler på kontekstfri grammatik af Fullstack Academy
  • Tracery af Galaxykate