Mis on kontekstivabad grammatikad?

Kas olete kunagi märganud, et kui kirjutate koodi tekstiredaktorisse nagu VS-kood, tunneb see ära näiteks tasakaalustamata traksid? Ja see hoiatab teid mõnikord ka ärritava punase esiletõstmisega teie kirjutatud vale süntaksi eest?

Kui ei, siis mõelge selle üle. See on ju jupp koodi. Kuidas saate sellise ülesande jaoks koodi kirjutada? Milline oleks selle taga olev loogika?

Need on sellised küsimused, mis teil tekivad, kui peate programmeerimiskeele jaoks kompilaatori kirjutama. Kompilaatori kirjutamine pole lihtne ülesanne. See on mahukas töö, mis nõuab märkimisväärselt palju aega ja vaeva.

Selles artiklis me ei hakka rääkima sellest, kuidas kompilaatoreid ehitada. Kuid me räägime kontseptsioonist, mis on kompilaatori põhikomponent: kontekstivabad grammatikad.

Sissejuhatus

Kõik küsimused, mida me varem esitasime, on probleem, mis on oluline kompilaatori kujunduse jaoks, mida nimetatakse süntaksianalüüsiks. Nagu nimigi ütleb, on väljakutse analüüsida süntaksit ja vaadata, kas see on õige või mitte. Siin kasutame kontekstivabu grammatikaid. Kontekstivaba grammatika on reeglite kogum, mis määrab keele.

Siinkohal tahaksin teha vahet kontekstivabade grammatikate ja selliste looduslike keelte nagu inglise keele grammatikate vahel.

Kontekstivabad grammatikad või CFG-d määratlevad ametliku keele. Ametlikud keeled töötavad rangelt määratletud reeglite järgi ja kontekst ei mõjuta nende lauseid. Ja seal saab see nime konteksti tasuta .

Sellised keeled nagu inglise keel kuuluvad mitteametlike keelte kategooriasse, kuna neid mõjutab kontekst. Neil on palju muid funktsioone, mida CFG ei suuda kirjeldada.

Kuigi CFG-d ei suuda kirjeldada konteksti loomulikes keeltes, saavad nad siiski määratleda nendes keeltes lausete süntaks ja struktuuri. Tegelikult on see põhjus, miks CFG-d esitleti.

Selles artiklis proovime luua CFG-de abil ingliskeelseid lauseid. Õpime, kuidas kirjeldada lauseehitust ja kirjutada sellele reegleid. Selleks kasutame JavaScripti teeki nimega Tracery, mis genereerib laused reeglite alusel, mille oleme oma grammatikale määratlenud.

Enne kui sukeldume koodi ja hakkame kirjutama grammatika reegleid, arutame vaid mõningaid põhitermineid, mida oma CFG-s kasutame.

Terminalid : need on märgid, mis moodustavad viimase lause tegeliku sisu. Need võivad sisaldada sõnu või tähti sõltuvalt sellest, millist neist kasutatakse lause põhielementidena.

Meie puhul kasutame oma lausete põhielementidena sõnu. Nii et meie terminalides on sellised sõnad nagu "kuni", "alates", "the", "auto", "kosmoselaev", "kassipojad" ja nii edasi.

Mitteterminalid : neid nimetatakse ka muutujateks. Need toimivad alakeelena grammatikas määratletud keeles. Mitte-terminalid on terminalide kohahoidjad. Terminalisümbolite erinevate mustrite genereerimiseks saame kasutada mitteterminaale.

Meie puhul kasutame neid Non-terminaale nimisõnade, verbifraaside, erinevate nimisõnade, omadussõnade, tegusõnade ja nii edasi genereerimiseks.

Start-sümbol : stardisümbol on spetsiaalne mitteterminal, mis tähistab grammatika genereeritavat algset stringi.

Nüüd, kui teame terminoloogiat, alustame grammatiliste reeglite tundmaõppimist.

Grammatikareeglite kirjutamise ajal alustame terminalide komplekti ja algseisundi määratlemisega. Nagu me varem teada saime, on see stardisümbol mitte-terminal. See tähendab, et see kuulub mitteterminalide hulka.

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

Ja reeglid on järgmised:

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

Eespool toodud grammatikareeglid võivad esialgu tunduda mõnevõrra krüptilised. Kuid hoolega uurides näeme mustrit, mis nendest reeglitest välja luuakse.

Parem viis ülaltoodud reeglite üle mõtlemiseks on nende visualiseerimine puustruktuuri kujul. Sellesse puusse võime panna S juure ja nimisõnaPhrase ja verbPhrase saab lisada juure lastena. Samamoodi saame jätkata ka nimisõnagaPhrase ja verbPhrase . Puu lehesõlmedeks on terminalid, sest seal me need tuletised lõpetame.

Ülaltoodud pildil näeme, et S (mitteterminaal) tuletab kaks mitteterminali NP ( nimisõnafraas ) ja VP ( verbifraas ). Juhul NP , ta on tuletatud kahest suitsetamine terminalide Adj ja lehekülge .

Kui vaadata grammatikat, oleks NP võinud valida ka Adj ja nimisõnaPhrase . Teksti genereerimisel tehakse need valikud juhuslikult.

Ja lõpuks on lehesõlmedel terminalid, mis on kirjutatud rasvases kirjas. Nii et kui liigute vasakult paremale, näete, et lause on moodustatud.

Selle puu puhul kasutatakse sageli mõistet Parse Tree. Selle grammatika genereeritud erineva lause jaoks saame sarnaselt luua veel ühe sõelumispuu.

Nüüd jätkame koodi juurde. Nagu ma varem mainisin, kasutame CFG-de abil teksti genereerimiseks JavaScripti teeki nimega Tracery. Kirjutame esiosa jaoks ka koodi HTML-is ja CSS-is.

Kood

Alustame kõigepealt märgistusraamatukogu hankimisest. GitHubi kaudu saate teeki kloonida siin. Samuti olen artikli lõppu jätnud galaxykate'i linki GitHubi hoidla juurde.

Enne raamatukogu kasutamist peame selle importima. Saame seda teha lihtsalt sellises HTML-failis.

Olen oma HTML-koodi lisanud kloonitud jäljendifaili skriptina. Samuti peame oma koodi lisama JQuery, kuna märgistus sõltub JQueryst. Lõpuks olen lisanud app.js, mis on fail, kuhu lisan reeglid grammatika jaoks.

Kui see on tehtud, looge JavaScripti fail, kus määratleme oma grammatikareeglid.

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

Siin märkate, et reeglite määratlemise süntaks ei erine palju sellest, kuidas me oma grammatikat varem defineerisime. On väga väikseid erinevusi, näiteks rida sümbolite vahelise mitteterminalide määratlemise viis. Ja ka viis, kuidas erinevaid tuletisi kirjutatakse. Selle asemel, et kasutada "|" nende eraldamise sümbol, paneme siin kõik erinevad tuletised massiivi erinevateks elementideks. Peale selle kasutame ülemineku tähistamiseks noolte asemel semikoole.

See uus grammatika on veidi keerulisem kui see, mille me varem defineerisime. See sisaldab paljusid muid asju, nagu määravad, transitiivsed ja intransitiivsed verbid. Teeme seda selleks, et loodud tekst näeks välja loomulikum.

Nimetagem nüüd märgistusfunktsiooni "createGrammar", et luua just määratletud grammatika.

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:

  • Kontekstivabad grammatikad, autor Daniel Shiffman.
  • Kontekstivaba grammatika näited Fullstack Academy poolt
  • Galaxykate'i jälg