Que sont les grammaires sans contexte?

Avez-vous déjà remarqué que, lorsque vous écrivez du code dans un éditeur de texte comme le code VS, il reconnaît des choses comme des accolades sans correspondance? Et il vous avertit aussi parfois, avec une surbrillance rouge irritante, de la syntaxe incorrecte que vous avez écrite?

Sinon, pensez-y. C'est après tout un morceau de code. Comment pouvez-vous écrire du code pour une telle tâche? Quelle en serait la logique sous-jacente?

Voilà le genre de questions auxquelles vous serez confronté si vous devez écrire un compilateur pour un langage de programmation. Ecrire un compilateur n'est pas une tâche facile. C'est un travail volumineux qui demande beaucoup de temps et d'efforts.

Dans cet article, nous n'allons pas parler de la façon de créer des compilateurs. Mais nous parlerons d'un concept qui est un composant central du compilateur: Grammaires sans contexte.

introduction

Toutes les questions que nous avons posées précédemment représentent un problème important pour la conception du compilateur appelé Analyse de la syntaxe. Comme son nom l'indique, le défi consiste à analyser la syntaxe et à voir si elle est correcte ou non. C'est là que nous utilisons les grammaires sans contexte. Une grammaire sans contexte est un ensemble de règles qui définissent une langue.

Ici, je voudrais faire une distinction entre les grammaires sans contexte et les grammaires pour les langues naturelles comme l'anglais.

Les grammaires ou CFG sans contexte définissent un langage formel. Les langues formelles fonctionnent strictement selon les règles définies et leurs phrases ne sont pas influencées par le contexte. Et c'est là que le nom est sans contexte .

Des langues comme l'anglais entrent dans la catégorie des langues informelles puisqu'elles sont affectées par le contexte. Ils ont de nombreuses autres caractéristiques qu'un CFG ne peut pas décrire.

Même si les CFG ne peuvent pas décrire le contexte dans les langues naturelles, ils peuvent toujours définir la syntaxe et la structure des phrases dans ces langues. En fait, c'est la raison pour laquelle les CFG ont été introduits en premier lieu.

Dans cet article, nous tenterons de générer des phrases en anglais à l'aide de CFG. Nous apprendrons à décrire la structure de la phrase et à écrire des règles pour celle-ci. Pour ce faire, nous utiliserons une bibliothèque JavaScript appelée Tracery qui générera des phrases sur la base des règles que nous avons définies pour notre grammaire.

Avant de plonger dans le code et de commencer à écrire les règles de la grammaire, discutons simplement de quelques termes de base que nous utiliserons dans notre CFG.

Terminaux : ce sont les caractères qui composent le contenu réel de la phrase finale. Ceux-ci peuvent inclure des mots ou des lettres selon lequel de ceux-ci est utilisé comme élément de base d'une phrase.

Dans notre cas, nous utiliserons les mots comme éléments de base de nos phrases. Ainsi, nos terminaux incluront des mots tels que "à", "de", "la", "voiture", "vaisseau spatial", "chatons" et ainsi de suite.

Non terminaux : ils sont également appelés variables. Ceux-ci agissent comme une sous-langue dans la langue définie par la grammaire. Les non terminaux sont des espaces réservés pour les terminaux. Nous pouvons utiliser des non terminaux pour générer différents modèles de symboles terminaux.

Dans notre cas, nous utiliserons ces terminaux Non pour générer des phrases nominales, des phrases verbales, différents noms, adjectifs, verbes, etc.

Symbole de début : un symbole de début est un non terminal spécial qui représente la chaîne initiale qui sera générée par la grammaire.

Maintenant que nous connaissons la terminologie, commençons à apprendre les règles grammaticales.

Lors de l'écriture des règles de grammaire, nous commencerons par définir l'ensemble des terminaux et un état de départ. Comme nous l'avons appris auparavant, ce symbole de départ est un non-terminal. Cela signifie qu'il appartiendra à l'ensemble des non-terminaux.

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

Et les règles sont:

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

Les règles grammaticales ci-dessus peuvent sembler quelque peu cryptiques au début. Mais si nous regardons attentivement, nous pouvons voir un modèle qui est généré à partir de ces règles.

Une meilleure façon de penser aux règles ci-dessus est de les visualiser sous la forme d'une structure arborescente. Dans cet arbre, nous pouvons mettre S dans la racine et nounPhrase et verbPhrase peuvent être ajoutés en tant qu'enfants de la racine. On peut procéder de la même manière avec nounPhrase et verbPhrase aussi. L'arbre aura des terminaux comme nœuds feuilles car c'est là que nous terminons ces dérivations.

Dans l'image ci-dessus, nous pouvons voir que S (un non terminal) dérive deux non terminaux NP ( nounPhrase ) et VP ( verbPhrase ). Dans le cas de NP , il a dérivé deux non terminaux, Adj et Noun .

Si vous regardez la grammaire, NP aurait également pu choisir Adj et nounPhrase . Lors de la génération du texte, ces choix sont effectués de manière aléatoire.

Et enfin les nœuds feuilles ont des terminaux qui sont écrits en gras. Donc, si vous vous déplacez de gauche à droite, vous pouvez voir qu'une phrase est formée.

Le terme souvent utilisé pour cet arbre est un arbre d'analyse. Nous pouvons créer un autre arbre d'analyse pour une phrase différente générée par cette grammaire de la même manière.

Passons maintenant au code. Comme je l'ai mentionné précédemment, nous utiliserons une bibliothèque JavaScript appelée Tracery pour la génération de texte à l'aide de CFG. Nous écrirons également du code en HTML et CSS pour la partie frontale.

Le code

Commençons par obtenir la bibliothèque d'entrelacs. Vous pouvez cloner la bibliothèque depuis GitHub ici. J'ai également laissé le lien vers le référentiel GitHub par galaxykate à la fin de l'article.

Avant d'utiliser la bibliothèque, nous devrons l'importer. Nous pouvons le faire simplement dans un fichier HTML comme celui-ci.

J'ai ajouté le fichier d'entrelacs cloné en tant que script dans mon code HTML. Nous devrons également ajouter JQuery à notre code car le tracery dépend de JQuery. Enfin, j'ai ajouté app.js qui est le fichier où j'ajouterai des règles pour la grammaire.

Une fois cela fait, créez un fichier JavaScript dans lequel nous définirons nos règles de grammaire.

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

Ici, vous remarquerez que la syntaxe pour définir les règles n'est pas très différente de la façon dont nous avons défini notre grammaire précédemment. Il existe des différences très mineures telles que la façon dont les non-terminaux sont définis entre les symboles de hachage. Et aussi la manière dont les différentes dérivations sont écrites. Au lieu d'utiliser le "|" symbole pour les séparer, nous mettrons ici toutes les différentes dérivations comme différents éléments d'un tableau. En dehors de cela, nous utiliserons les points-virgules au lieu des flèches pour représenter la transition.

Cette nouvelle grammaire est un peu plus compliquée que celle que nous avons définie précédemment. Celui-ci comprend de nombreuses autres choses telles que les déterminants, les verbes transitifs et les verbes intransitifs. Nous faisons cela pour rendre le texte généré plus naturel.

Appelons maintenant la fonction d'entrelacs "createGrammar" pour créer la grammaire que nous venons de définir.

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