Észrevetted már, hogy amikor olyan kódszerkesztőbe írsz kódot, mint a VS-kód, az olyan dolgokat ismer fel, mint a páratlan zárójelek? És néha egy-egy irritáló vörös kiemeléssel figyelmezteti Önt is a helytelen szintaxisra, amelyet írt?
Ha nem, akkor gondold át. Végül is egy darab kód. Hogyan írhat kódot egy ilyen feladathoz? Mi lenne a mögöttes logika?
Ezekkel a kérdésekkel fogsz szembesülni, ha fordítót kell írnod egy programozási nyelvhez. A fordító írása nem könnyű feladat. A terjedelmes munka jelentős időt és erőfeszítést igényel.
Ebben a cikkben nem fogunk beszélni a fordítók felépítéséről. De beszélni fogunk egy olyan koncepcióról, amely a fordító alapvető eleme: a Context Free Grammars.
Bevezetés
Az összes korábban feltett kérdés olyan problémát jelent, amely a Syntax Analysis nevű fordítóterv szempontjából jelentős. Ahogy a neve is sugallja, a kihívás a szintaxis elemzése, és annak kiderítése, hogy helyes-e vagy sem. Itt használjuk a Context Free Nyelvtanokat. A kontextus nélküli nyelvtan egy olyan szabályhalmaz, amely meghatározza a nyelvet.
Itt szeretnék különbséget tenni a kontextusmentes nyelvtanok és a természetes nyelvek, például az angol nyelvtanai között.
A kontextus nélküli nyelvtanok vagy CFG-k hivatalos nyelvet határoznak meg. A hivatalos nyelvek szigorúan a meghatározott szabályok szerint működnek, és mondataikat a kontextus nem befolyásolja. És itt szabaddá válik a névkörnyezet .
Az olyan nyelvek, mint az angol, az informális nyelvek kategóriájába tartoznak, mivel a kontextus érinti őket. Sok más olyan tulajdonságuk van, amelyeket a CFG nem tud leírni.
Annak ellenére, hogy a CFG-k nem írják le a kontextust a természetes nyelveken, mégis meghatározhatják ezeken a nyelveken a mondatok szintaxisát és felépítését. Valójában ez az oka annak, hogy a CFG-ket először is bevezették.
Ebben a cikkben megpróbálunk angol mondatokat előállítani CFG-k segítségével. Megtanuljuk, hogyan kell leírni a mondatszerkezetet, és írni rá szabályokat. Ehhez egy Tracery nevű JavaScript könyvtárat fogunk használni, amely mondatokat állít elő a nyelvtanunkra meghatározott szabályok alapján.
Mielőtt belevetnénk magunkat a kódba és elkezdjük írni a nyelvtan szabályait, beszéljünk néhány alapvető kifejezésről, amelyeket a CFG-ben fogunk használni.
Terminálok : Ezek a karakterek alkotják az utolsó mondat tényleges tartalmát. Ezek tartalmazhatnak szavakat vagy betűket attól függően, hogy melyiket használják a mondat alapvető építőelemeként.
Esetünkben a szavakat fogjuk használni mondataink alapvető építőelemeként. Tehát a termináljaink olyan szavakat fognak tartalmazni, mint "ide", "honnan", "az", "autó", "űrhajó", "cica" és így tovább.
Nem terminálok : Ezeket változónak is nevezzük. Ezek alnyelvként működnek a nyelvtan által meghatározott nyelven belül. A nem terminálok a terminálok helyőrzői. Használhatunk nem terminálokat a terminálszimbólumok különböző mintáinak előállításához.
Esetünkben ezeket a Non terminálokat fogjuk használni főnévi kifejezések, igei kifejezések, különböző főnevek, melléknevek, igék stb. Előállításához.
Start szimbólum : a start szimbólum egy speciális nem terminál, amely a kezdő karakterláncot képviseli, amelyet a nyelvtan generál.
Most, hogy ismerjük a terminológiát, kezdjük el megismerni a nyelvtani szabályokat.
A nyelvtani szabályok írása közben a terminálkészlet és a kezdőállapot meghatározásával kezdjük. Mint korábban megtudtuk, ez a kezdő szimbólum nem terminális. Ez azt jelenti, hogy a nem terminálok készletéhez fog tartozni.
T: ("Monkey", "banana", "ate", "the") S: Start state. És a szabályok a következők:
S --> nounPhrase verbPhrase nounPhrase --> adj nounPhrase | adj noun verbPhrase --> verb nounPhrase adjective --> the noun --> Monkey | banana verb --> ateA fenti nyelvtani szabályok elsőre kissé rejtélyesnek tűnhetnek. De ha alaposan megnézzük, láthatunk egy mintát, amely ezekből a szabályokból jön létre.
Jobb módszer a fenti szabályokra gondolni, ha fa szerkezet formájában vizualizáljuk őket. Abban a fában S- t adhatunk a gyökérbe, és a főnév és aPrase és a verbPhrase a gyökér gyermekeiként adhatók hozzá. Ugyanígy járhatunk el a nounPhrase és a verbPhrase használatával is. A fa levélcsomópontjai terminálok lesznek, mert itt vesszük véget ezeknek a levezetéseknek.
A fenti képen láthatjuk, hogy S (egy nem terminális) két nem terminált NP ( nounPhrase ) és VP ( verbPhrase ) származtat . Az NP esetében két nem terminált, Adj-t és Noun-ot származtatott .
Ha megnézzük a nyelvtant, az NP választhatta az Adj és a főnévPhrase szót is . A szöveg létrehozása közben ezek a döntések véletlenszerűen történnek.
És végül a levélcsomópontoknak vannak termináljai, amelyeket félkövér szöveggel írnak. Tehát ha balról jobbra halad, láthatja, hogy egy mondat képződik.
A fára gyakran használt kifejezés egy elemző fa. Hozhatunk létre egy másik elemzőfát egy másik mondathoz, amelyet ez a nyelvtan generál hasonló módon.
Most térjünk tovább a kódra. Mint korábban említettem, a Tracery nevű JavaScript könyvtárat fogjuk használni a CFG-k használatával történő szöveggeneráláshoz. Ezenkívül HTML-ben és CSS-ben is írunk néhány kódot az elülső részhez.
A kód
Kezdjük azzal, hogy először beszerezzük az áttört könyvtárat. A könyvtárat itt klónozhatja a GitHub-ból. A cikk végén meghagytam a galaxykate által a GitHub tárházhoz vezető linket is.
A könyvtár használata előtt importálnunk kell. Ezt egyszerűen megtehetjük egy ilyen HTML fájlban.
A klónozott nyomkövetési fájlt szkriptként adtam hozzá a HTML-kódomhoz. A JQuery-t hozzá kell adnunk a kódunkhoz is, mert a nyomkövetés a JQuery-től függ. Végül hozzáadtam az app.js fájlt, amely a fájl, ahová szabályokat adok a nyelvtanhoz.
Ha ez megtörtént, hozzon létre egy JavaScript fájlt, ahol meghatározzuk a nyelvtani szabályokat.
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"] } Itt észreveheti, hogy a szabályok meghatározásának szintaxisa nem sokban különbözik attól, ahogyan korábban meghatároztuk a nyelvtanunkat. Nagyon kisebb különbségek vannak, mint például a nem terminálok meghatározása a hash szimbólumok között. És a különböző levezetések megírásának módja is. A "|" helyett szimbólum a szétválasztásukra, itt az összes különböző levezetést egy tömb különböző elemeként fogjuk elhelyezni. Ezen kívül nyilak helyett a pontosvesszőket használjuk az átmenet ábrázolására.
Ez az új nyelvtan egy kicsit bonyolultabb, mint amit korábban definiáltunk. Ez sok más dolgot tartalmaz, például a meghatározókat, a transzitív igéket és az intransitív igéket. Ezt azért tesszük, hogy a létrehozott szöveg természetesebb legyen.
Most nevezzük a nyomkövetési függvényt "createGrammar" -nak az imént definiált nyelvtan létrehozásához.
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