Що таке контекстуальні вільні граматики?

Ви коли-небудь помічали, що коли ви пишете код у текстовому редакторі, як код VS, він розпізнає такі речі, як неперевершені дужки? І це також іноді попереджає вас, дратуючи червоним виділенням, про неправильний синтаксис, який ви написали?

Якщо ні, то подумайте. Це все-таки шматок коду. Як можна написати код для такого завдання? У чому полягала б логіка?

З такими видами запитань ви зіткнетесь, якщо вам доведеться написати компілятор для мови програмування. Написання компілятора - завдання непросте. Це громіздка робота, яка вимагає значної кількості часу та зусиль.

У цій статті ми не будемо говорити про те, як будувати компілятори. Але ми поговоримо про концепцію, яка є основною складовою компілятора: Безкоштовні граматики.

Вступ

Всі питання, які ми задавали раніше, представляють проблему, яка є важливою для дизайну компілятора, яка називається Syntax Analysis. Як випливає з назви, завдання полягає в аналізі синтаксису та перевірці, чи він правильний чи ні. Тут ми використовуємо Безконтекстні граматики. Безкоштовна граматика - це набір правил, що визначають мову.

Тут я хотів би провести різницю між граматиками без контексту та граматиками для природних мов, таких як англійська.

Безкоштовні граматики або CFG визначають офіційну мову. Формальні мови працюють суворо за визначеними правилами, і контекст на них не впливає. І саме тут воно отримує назву безкоштовно контекстною .

Такі мови, як англійська, підпадають під категорію неформальних мов, оскільки на них впливає контекст. Вони мають багато інших особливостей, які CFG не може описати.

Незважаючи на те, що CFG не можуть описати контекст природними мовами, вони все одно можуть визначити синтаксис та структуру речень у цих мовах. Насправді це причина, чому КФГ були введені в першу чергу.

У цій статті ми спробуємо створити англійські речення за допомогою CFG. Ми навчимось описувати структуру речення та писати правила для нього. Для цього ми будемо використовувати бібліотеку JavaScript під назвою Tracery, яка генеруватиме речення на основі правил, які ми визначили для нашої граматики.

Перш ніж заглибитися в код і почати писати правила граматики, давайте просто обговоримо деякі основні терміни, які ми будемо використовувати в нашій CFG.

Термінали : це символи, які складають фактичний зміст останнього речення. Сюди можуть входити слова чи букви, залежно від того, що з них використовується як основний будівельний блок речення.

У нашому випадку ми будемо використовувати слова як основні будівельні блоки наших речень. Тож наші термінали включатимуть такі слова, як "до", "від", "до", "машина", "космічний корабель", "кошенята" тощо.

Нетермінали : їх також називають змінними. Вони виступають як допоміжна мова в межах мови, визначеної граматикою. Нетермінали є заповнювачами для терміналів. Ми можемо використовувати нетермінали для генерації різних шаблонів символів терміналів.

У нашому випадку ми будемо використовувати ці нетермінали для генерування іменникових фраз, дієслівних фраз, різних іменників, прикметників, дієслів тощо.

Символ старту: символ старту - це спеціальний нетермінал, який представляє початковий рядок, який буде сформований граматикою.

Тепер, коли ми знаємо термінологію, давайте почнемо вивчати граматичні правила.

Під час написання граматичних правил ми почнемо з визначення набору терміналів та стартового стану. Як ми вже дізналися раніше, цей символ старту не є термінальним. Це означає, що він буде належати до набору нетерміналів.

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

І правила такі:

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

Наведені вище граматичні правила спочатку можуть здатися дещо загадковими. Але якщо ми уважно подивимось, ми зможемо побачити шаблон, який породжується цими правилами.

Кращий спосіб подумати про вищезазначені правила - це візуалізувати їх у вигляді деревної структури. У цьому дереві ми можемо поставити S у корінь, а іменникPhrase та verbPhrase можна додати як дочірні корінці. Ми можемо продовжувати так само з nounPhrase і verbPhrase . Дерево буде мати термінали як свої вузли листя, тому що на цьому ми закінчуємо ці виведення.

На наведеному вище зображенні ми бачимо, що S (нетермінал) походить від двох нетерміналів NP ( nounPhrase ) і VP ( verbPhrase ). У випадку з NP воно отримало два нетермінали, Adj та Noun .

Якщо поглянути на граматику, NP також міг би вибрати Adj та nounPhrase . Під час генерації тексту цей вибір робиться випадковим чином.

І нарешті, на листових вузлах є термінали, які написані жирним шрифтом. Отже, якщо рухатись зліва направо, можна побачити, що речення сформовано.

Термін, який часто використовують для цього дерева, - це Синтаксичний аналіз. Ми можемо створити інше дерево синтаксичного аналізу для іншого речення, породженого цією граматикою, подібним чином.

Тепер перейдемо до коду. Як я вже згадував раніше, ми будемо використовувати бібліотеку JavaScript під назвою Tracery для створення тексту за допомогою CFG. Ми також напишемо трохи коду в HTML та CSS для інтерфейсної частини.

Кодекс

Почнемо з того, що спочатку отримаємо бібліотеку ажурних матеріалів. Ви можете клонувати бібліотеку з GitHub тут. Я також залишив посилання на сховище GitHub від galaxykate в кінці статті.

Перш ніж використовувати бібліотеку, нам доведеться її імпортувати. Ми можемо зробити це просто у такому HTML-файлі.

Я додав клонований ажурний файл як сценарій у свій HTML-код. Нам також доведеться додати JQuery до нашого коду, оскільки ажурність залежить від JQuery. Нарешті, я додав app.js, який є файлом, куди я додаю правила для граматики.

Після цього створіть файл JavaScript, де ми визначимо наші правила граматики.

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

Тут ви помітите, що синтаксис визначення правил мало чим відрізняється від того, як ми визначали нашу граматику раніше. Існують дуже незначні відмінності, такі як спосіб визначення нетерміналів між хеш-символами. А також спосіб написання різних похідних. Замість того, щоб використовувати "|" символ для їх розділення, тут ми покладемо всі різні похідні як різні елементи масиву. Крім цього, ми будемо використовувати крапку з комою замість стрілок для позначення переходу.

Ця нова граматика дещо складніша, ніж та, яку ми визначили раніше. Цей включає багато інших речей, таких як Визначники, Перехідні дієслова та Неперехідні дієслова. Ми робимо це, щоб створений текст виглядав більш природно.

Давайте тепер назвемо функцію ажурного "createGrammar", щоб створити щойно визначену нами граматику.

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