Apakah Tatabahasa Bebas Konteks?

Pernahkah anda perhatikan bahawa, semasa anda menulis kod dalam penyunting teks seperti kod VS, ia mengenali perkara seperti pendakap yang tidak dapat ditandingi? Dan kadang-kadang juga memberi amaran kepada anda, dengan sorotan merah yang menjengkelkan, mengenai sintaksis yang tidak betul yang anda tulis?

Sekiranya tidak, maka fikirkanlah. Itu adalah sekeping kod. Bagaimana anda boleh menulis kod untuk tugas seperti itu? Apakah logik yang mendasari di belakangnya?

Ini adalah jenis soalan yang akan anda hadapi jika anda perlu menulis penyusun untuk bahasa pengaturcaraan. Menulis penyusun bukanlah tugas yang mudah. Ini adalah pekerjaan besar yang memerlukan banyak masa dan usaha.

Dalam artikel ini, kita tidak akan membincangkan bagaimana membina penyusun. Tetapi kita akan membincangkan konsep yang merupakan komponen teras penyusun: Tatabahasa Bebas Konteks.

Pengenalan

Semua soalan yang kami ajukan sebelumnya mewakili masalah yang penting bagi reka bentuk penyusun yang dipanggil Syntax Analysis. Seperti namanya, cabarannya adalah untuk menganalisis sintaks dan melihat apakah betul atau tidak. Di sinilah kami menggunakan Tatabahasa Bebas Konteks. Tatabahasa Bebas Konteks adalah sekumpulan peraturan yang menentukan bahasa.

Di sini, saya ingin membuat perbezaan antara Tatabahasa Bebas Konteks dan tatabahasa untuk bahasa semula jadi seperti Bahasa Inggeris.

Tatabahasa Bebas Konteks atau CFG menentukan bahasa formal. Bahasa formal berfungsi dengan tegas di bawah peraturan yang ditentukan dan ayatnya tidak dipengaruhi oleh konteksnya. Dan di situlah mendapat konteks nama percuma .

Bahasa seperti Bahasa Inggeris tergolong dalam kategori Bahasa Tidak formal kerana dipengaruhi oleh konteks. Mereka mempunyai banyak ciri lain yang tidak dapat dijelaskan oleh CFG.

Walaupun CFG tidak dapat menggambarkan konteks dalam bahasa semula jadi, mereka masih dapat menentukan sintaksis dan struktur ayat dalam bahasa-bahasa ini. Sebenarnya, itulah sebab mengapa CFG diperkenalkan di tempat pertama.

Dalam artikel ini kita akan berusaha menghasilkan ayat bahasa Inggeris menggunakan CFG. Kami akan belajar bagaimana menerangkan struktur ayat dan menulis peraturan untuknya. Untuk melakukan ini, kami akan menggunakan perpustakaan JavaScript yang disebut Tracery yang akan menghasilkan ayat berdasarkan peraturan yang kami tetapkan untuk tatabahasa kami.

Sebelum kita mempelajari kod dan mula menulis peraturan untuk tatabahasa, mari kita bincangkan beberapa istilah asas yang akan kita gunakan dalam CFG kita.

Terminal : Ini adalah watak-watak yang membentuk kandungan sebenar dari ayat terakhir. Ini boleh merangkumi perkataan atau huruf bergantung pada mana yang digunakan sebagai asas penyusun ayat.

Dalam kes kami, kami akan menggunakan kata-kata sebagai asas penyusun ayat kami. Jadi terminal kami akan merangkumi kata-kata seperti "to", "from", "the", "car", "kapal angkasa", "anak kucing" dan sebagainya.

Bukan Terminal : Ini juga disebut pemboleh ubah. Ini bertindak sebagai sub bahasa dalam bahasa yang ditentukan oleh tatabahasa. Bukan terminal adalah tempat letak terminal. Kita boleh menggunakan bukan terminal untuk menghasilkan corak simbol terminal yang berbeza.

Dalam kes kami, kami akan menggunakan terminal Non ini untuk menghasilkan frasa nama, frasa kerja, kata nama yang berbeza, kata sifat, kata kerja dan sebagainya.

Simbol Mula : simbol permulaan adalah terminal bukan khas yang mewakili rentetan awal yang akan dihasilkan oleh tatabahasa.

Setelah kita mengetahui terminologi, mari kita mulai belajar mengenai peraturan tatabahasa.

Semasa menulis peraturan tatabahasa, kita akan memulakan dengan menentukan set terminal dan keadaan permulaan. Seperti yang kita pelajari sebelumnya, simbol permulaan adalah bukan terminal. Ini bermaksud ia akan tergolong dalam kumpulan bukan terminal.

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

Dan peraturannya adalah:

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

Peraturan tatabahasa di atas mungkin kelihatan agak samar pada mulanya. Tetapi jika kita melihat dengan teliti, kita dapat melihat corak yang dihasilkan dari peraturan ini.

Kaedah yang lebih baik untuk memikirkan peraturan di atas adalah dengan memvisualisasikannya dalam bentuk struktur pokok. Di pokok itu kita dapat meletakkan S di akar dan kata nama dan Frasa kata kerja dapat ditambahkan sebagai anak akar. Kita boleh meneruskan dengan cara yang sama dengan kata nama dan kata kerja juga. Pokok akan mempunyai terminal sebagai simpul daunnya kerana di situlah kita mengakhiri turunan ini.

Dalam gambar di atas kita dapat melihat bahawa S (bukan terminal) menghasilkan dua terminal NP (kata nama ) dan VP (kata kerja Frasa ). Dalam kes NP , ia menghasilkan dua terminal bukan, Adj dan Noun .

Sekiranya anda melihat tatabahasa, NP juga boleh memilih Frasa Adj dan kata nama . Semasa menghasilkan teks, pilihan ini dibuat secara rawak.

Dan akhirnya simpul daun mempunyai terminal yang ditulis dalam teks tebal. Oleh itu, jika anda bergerak dari kiri ke kanan, anda dapat melihat bahawa ayat terbentuk.

Istilah yang sering digunakan untuk pokok ini ialah Parse Tree. Kita boleh membuat pokok parse lain untuk ayat yang berbeza yang dihasilkan oleh tatabahasa ini dengan cara yang serupa.

Sekarang mari kita lanjutkan kodnya. Seperti yang saya sebutkan sebelumnya, kami akan menggunakan perpustakaan JavaScript yang disebut Tracery untuk penghasilan teks menggunakan CFG. Kami juga akan menulis beberapa kod dalam HTML dan CSS untuk bahagian depan.

Kod tersebut

Mari mulakan dengan mendapatkan perpustakaan tracery terlebih dahulu. Anda boleh mengklon perpustakaan dari GitHub di sini. Saya juga telah meninggalkan pautan ke repositori GitHub oleh galaxykate pada akhir artikel.

Sebelum menggunakan perpustakaan, kita mesti mengimportnya. Kita boleh melakukannya hanya dalam fail HTML seperti ini.

Saya telah menambahkan fail tracery yang diklon sebagai skrip dalam kod HTML saya. Kita juga harus menambahkan JQuery ke kod kita kerana tracery bergantung pada JQuery. Akhirnya, saya telah menambahkan app.js yang merupakan fail di mana saya akan menambahkan peraturan untuk tatabahasa.

Setelah selesai, buat fail JavaScript di mana kami akan menentukan peraturan tatabahasa kami.

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

Di sini anda akan melihat bahawa sintaks untuk menentukan peraturan tidak jauh berbeza dengan cara kita menentukan tatabahasa kita sebelumnya. Terdapat perbezaan yang sangat kecil seperti cara definisi bukan terminal antara simbol hash. Dan juga cara penulisan terbitan yang berbeza. Daripada menggunakan "|" simbol untuk memisahkannya, di sini kita akan meletakkan semua derivasi yang berlainan sebagai unsur yang berlainan dari suatu array. Selain itu, kita akan menggunakan titik koma dan bukan anak panah untuk mewakili peralihan.

Tatabahasa baru ini sedikit lebih rumit daripada yang kita tentukan sebelumnya. Yang ini merangkumi banyak perkara lain seperti Penentu, Kata Kerja Transitif dan Kata Kerja Tak Transitif. Kami melakukan ini untuk menjadikan teks yang dihasilkan kelihatan lebih semula jadi.

Sekarang mari kita panggil fungsi tracery "createGrammar" untuk membuat tatabahasa yang baru kita tentukan.

let grammar = tracery.createGrammar(rules);

Fungsi ini akan mengambil objek peraturan dan menghasilkan tatabahasa berdasarkan peraturan ini. Setelah membuat tatabahasa, kami sekarang ingin menghasilkan beberapa hasil akhir daripadanya. Untuk melakukan itu kita akan menggunakan fungsi yang disebut "meratakan".

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

Ini akan menghasilkan ayat secara rawak berdasarkan peraturan yang kita tentukan sebelumnya. Tetapi jangan berhenti di situ. Mari juga bina antara muka pengguna untuknya. Tidak banyak yang perlu kita lakukan untuk bahagian itu - kita hanya memerlukan butang dan beberapa gaya asas untuk antara muka.

Dalam fail HTML yang sama di mana kami menambahkan perpustakaan, kami akan menambahkan beberapa elemen.

  Weird Sentences          

Weird Sentences

Give me a Sentence!

Dan akhirnya kita akan menambahkan beberapa gaya padanya.

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

Kita juga perlu menambahkan lebih banyak JavaScript untuk memanipulasi antara muka.

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

" } }

Setelah selesai menulis kod, jalankan fail HTML anda. Ia mesti kelihatan seperti ini.

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