Hva er kontekstfrie grammatikker?

Har du noen gang lagt merke til at når du skriver kode i en tekstredigerer som VS-kode, gjenkjenner den ting som uovertrufne bukseseler? Og det advarer også noen ganger, med et irriterende rødt høydepunkt, om den falske syntaksen du har skrevet?

Hvis ikke, så tenk på det. Det er tross alt et stykke kode. Hvordan kan du skrive kode for en slik oppgave? Hva ville være den underliggende logikken bak den?

Det er slike spørsmål du vil møte hvis du må skrive en kompilator for et programmeringsspråk. Å skrive en kompilator er ikke en enkel oppgave. Det er klumpete jobb som krever betydelig tid og krefter.

I denne artikkelen skal vi ikke snakke om hvordan man bygger kompilatorer. Men vi vil snakke om et konsept som er en kjernekomponent i kompilatoren: Context Free Grammars.

Introduksjon

Alle spørsmålene vi stilte tidligere representerer et problem som er viktig for kompilerdesign kalt Syntax Analysis. Som navnet antyder, er utfordringen å analysere syntaksen og se om den er riktig eller ikke. Det er her vi bruker Context Free Grammars. En kontekstfri grammatikk er et sett med regler som definerer et språk.

Her vil jeg trekke et skille mellom kontekstfri grammatikk og grammatikk for naturlige språk som engelsk.

Kontekstfri grammatikk eller CFG definerer et formelt språk. Formelle språk fungerer strengt under de definerte reglene, og setningene deres påvirkes ikke av konteksten. Og det er der det blir navnet sammenheng gratis .

Språk som engelsk faller inn under kategorien uformelle språk siden de påvirkes av kontekst. De har mange andre funksjoner som en CFG ikke kan beskrive.

Selv om CFG-er ikke kan beskrive konteksten på de naturlige språkene, kan de fremdeles definere syntaksen og strukturen til setninger på disse språkene. Det er faktisk grunnen til at CFG-er ble introdusert i utgangspunktet.

I denne artikkelen vil vi prøve å generere engelske setninger ved hjelp av CFG. Vi lærer hvordan vi kan beskrive setningsstrukturen og skrive regler for den. For å gjøre dette, vil vi bruke et JavaScript-bibliotek kalt Tracery som vil generere setninger på grunnlag av regler vi definerte for grammatikken vår.

Før vi dykker inn i koden og begynner å skrive reglene for grammatikken, la oss bare diskutere noen grunnleggende begreper som vi vil bruke i CFG.

Terminaler : Dette er tegnene som utgjør det faktiske innholdet i den siste setningen. Disse kan omfatte ord eller bokstaver, avhengig av hvilken av disse som brukes som grunnleggende byggestein i en setning.

I vårt tilfelle vil vi bruke ord som de grunnleggende byggesteinene i setningene våre. Så terminalene våre vil inneholde ord som "til", "fra", "the", "bil", "romskip", "kattunger" og så videre.

Ikke-terminaler : Disse kalles også variabler. Disse fungerer som et underspråk innenfor språket som er definert av grammatikken. Ikke-terminaler er plassholdere for terminalene. Vi kan bruke ikke-terminaler til å generere forskjellige mønstre av terminalsymboler.

I vårt tilfelle vil vi bruke disse ikke-terminalene til å generere substantivuttrykk, verbuttrykk, forskjellige substantiver, adjektiv, verb og så videre.

Startsymbol : et startsymbol er en spesiell ikke-terminal som representerer den første strengen som genereres av grammatikken.

Nå som vi kjenner terminologien, la oss begynne å lære om de grammatiske reglene.

Mens vi skriver grammatikkregler, begynner vi med å definere settet med terminaler og en starttilstand. Som vi lærte før, er startsymbolet et ikke-terminal. Dette betyr at den vil tilhøre settet med ikke-terminaler.

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

Og reglene er:

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

Ovennevnte grammatiske regler kan i utgangspunktet virke noe kryptiske. Men hvis vi ser nøye, kan vi se et mønster som genereres ut av disse reglene.

En bedre måte å tenke på ovennevnte regler er å visualisere dem i form av en trestruktur. I det treet kan vi sette S i roten og substantivFase og verbFase kan legges til som barn av roten. Vi kan fortsette på samme måte med substantivPhrase og verbPhrase også. Treet vil ha terminaler som bladnoder fordi det er der vi avslutter disse avledningene.

På bildet ovenfor kan vi se at S (en ikke-terminal) stammer fra to ikke-terminaler NP ( substantivPhrase ) og VP ( verbPhrase ). I tilfelle NP har den avledet to ikke-terminaler, Adj og Substantiv .

Hvis du ser på grammatikken, kunne NP også ha valgt Adj og substantivFase . Mens du genererer tekst, blir disse valgene gjort tilfeldig.

Og til slutt har bladnodene terminaler som er skrevet i fet skrift. Så hvis du beveger deg fra venstre til høyre, kan du se at det dannes en setning.

Begrepet som ofte brukes for dette treet er et Parse Tree. Vi kan lage et annet parse-tre for en annen setning generert av denne grammatikken på en lignende måte.

La oss nå gå videre til koden. Som jeg nevnte tidligere, vil vi bruke et JavaScript-bibliotek kalt Tracery for tekstgenerering ved hjelp av CFG-er. Vi vil også skrive litt kode i HTML og CSS for frontend-delen.

Koden

La oss starte med å først skaffe oss tracery-biblioteket. Du kan klone biblioteket fra GitHub her. Jeg har også forlatt lenken til GitHub-depotet av galaxykate på slutten av artikkelen.

Før vi bruker biblioteket, må vi importere det. Vi kan gjøre dette ganske enkelt i en HTML-fil som denne.

Jeg har lagt til den klonede tracery-filen som et skript i HTML-koden min. Vi må også legge til JQuery i koden vår fordi tracery er avhengig av JQuery. Til slutt har jeg lagt til app.js som er filen der jeg skal legge til regler for grammatikken.

Når det er gjort, oppretter du en JavaScript-fil der vi vil definere grammatikkreglene.

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 legge merke til at syntaksen for å definere regler ikke er mye forskjellig fra hvordan vi definerte vår grammatikk tidligere. Det er veldig små forskjeller, for eksempel måten ikke-terminaler er definert mellom hash-symbolene. Og også måten forskjellige avledninger er skrevet på. I stedet for å bruke "|" symbol for å skille dem, her vil vi sette alle forskjellige avledninger som forskjellige elementer i en matrise. Annet enn det, vil vi bruke semikolonene i stedet for pilene for å representere overgangen.

Denne nye grammatikken er litt mer komplisert enn den vi definerte tidligere. Denne inkluderer mange andre ting som bestemmere, transitive verb og intransitive verb. Vi gjør dette for å få den genererte teksten til å se mer naturlig ut.

La oss nå kalle tracery-funksjonen "createGrammar" for å lage grammatikken vi nettopp definerte.

let grammar = tracery.createGrammar(rules);

Denne funksjonen tar reglene objektet og genererer en grammatikk på grunnlag av disse reglene. Etter å ha opprettet grammatikken, vil vi nå generere noe sluttresultat av den. For å gjøre det vil vi bruke en funksjon kalt "flate".

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

Det vil generere en tilfeldig setning basert på reglene vi definerte tidligere. Men la oss ikke stoppe der. La oss også bygge et brukergrensesnitt for det. Det er ikke mye vi må gjøre for den delen - vi trenger bare en knapp og noen grunnleggende stiler for grensesnittet.

I den samme HTML-filen der vi la til bibliotekene, vil vi legge til noen elementer.

  Weird Sentences          

Weird Sentences

Give me a Sentence!

Og til slutt vil vi legge til noen stiler til det.

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; }

Vi må også legge til litt mer JavaScript for å manipulere grensesnittet.

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

" } }

Når du er ferdig med å skrive koden, kjører du HTML-filen. Det skal se ut som dette.

Hver gang du klikker på den røde knappen, vil den generere en setning. Noen av disse setningene gir kanskje ingen mening. Dette er fordi, som jeg sa tidligere, CFG-er ikke kan beskrive konteksten og noen andre funksjoner som naturlige språk har. Den brukes bare til å definere setningen og strukturen til setningene.

Du kan sjekke ut liveversjonen av dette her.

Konklusjon

Hvis du har kommet dit så langt, setter jeg stor pris på din motstandskraft. Det kan være et nytt konsept for noen av dere, og andre har kanskje lært om det på college-kursene sine. Men fortsatt har kontekstfrie grammatikker interessante applikasjoner som spenner vidt fra informatikk til lingvistikk.

Jeg har prøvd mitt beste for å presentere hovedideene til CFG-er her, men det er mye mer du kan lære om dem. Her har jeg lagt igjen lenker til noen gode ressurser:

  • Context Free Grammars av Daniel Shiffman.
  • Eksempler på kontekstfrie grammatikker av Fullstack Academy
  • Tracery av Galaxykate