¿Alguna vez ha notado que, cuando escribe código en un editor de texto como el código VS, reconoce cosas como llaves inigualables? ¿Y a veces también te advierte, con un irritante resaltado en rojo, sobre la sintaxis incorrecta que has escrito?

Si no es así, piénselo. Después de todo, es un fragmento de código. ¿Cómo puedes escribir código para tal tarea? ¿Cuál sería la lógica subyacente detrás de esto?

Estos son los tipos de preguntas a las que se enfrentará si tiene que escribir un compilador para un lenguaje de programación. Escribir un compilador no es tarea fácil. Es un trabajo voluminoso que requiere una cantidad significativa de tiempo y esfuerzo.

En este artículo, no vamos a hablar sobre cómo construir compiladores. Pero hablaremos de un concepto que es un componente central del compilador: Gramáticas libres de contexto.

Introducción

Todas las preguntas que hicimos anteriormente representan un problema importante para el diseño del compilador llamado Análisis de sintaxis. Como sugiere el nombre, el desafío es analizar la sintaxis y ver si es correcta o no. Aquí es donde usamos Gramáticas libres de contexto. Una gramática libre de contexto es un conjunto de reglas que definen un idioma.

Aquí, me gustaría hacer una distinción entre gramáticas libres de contexto y gramáticas para lenguajes naturales como el inglés.

Las gramáticas libres de contexto o CFG definen un lenguaje formal. Los lenguajes formales funcionan estrictamente bajo las reglas definidas y sus oraciones no están influenciadas por el contexto. Y ahí es donde se libera el contexto del nombre .

Idiomas como el inglés se incluyen en la categoría de idiomas informales ya que se ven afectados por el contexto. Tienen muchas otras características que un CFG no puede describir.

Aunque los CFG no pueden describir el contexto en los lenguajes naturales, aún pueden definir la sintaxis y la estructura de las oraciones en estos lenguajes. De hecho, esa es la razón por la que se introdujeron los CFG en primer lugar.

En este artículo intentaremos generar oraciones en inglés usando CFG. Aprenderemos a describir la estructura de la oración y a escribir reglas para ella. Para hacer esto, usaremos una biblioteca de JavaScript llamada Tracery que generará oraciones en base a las reglas que definimos para nuestra gramática.

Antes de sumergirnos en el código y comenzar a escribir las reglas de la gramática, analicemos algunos términos básicos que usaremos en nuestro CFG.

Terminales : son los personajes que componen el contenido real de la oración final. Estos pueden incluir palabras o letras, según cuál de ellos se utilice como componente básico de una oración.

En nuestro caso, usaremos palabras como bloques de construcción básicos de nuestras oraciones. Así que nuestros terminales incluirán palabras como "para", "de", "el", "coche", "nave espacial", "gatitos", etc.

No terminales : también se denominan variables. Estos actúan como un sub-lenguaje dentro del lenguaje definido por la gramática. Los no terminales son marcadores de posición para los terminales. Podemos usar no terminales para generar diferentes patrones de símbolos terminales.

En nuestro caso usaremos estos Non terminales para generar frases nominales, frases verbales, diferentes sustantivos, adjetivos, verbos, etc.

Símbolo de inicio : un símbolo de inicio es un no terminal especial que representa la cadena inicial que será generada por la gramática.

Ahora que conocemos la terminología, comencemos a aprender sobre las reglas gramaticales.

Mientras escribimos reglas gramaticales, comenzaremos por definir el conjunto de terminales y un estado de inicio. Como aprendimos antes, ese símbolo de inicio no es terminal. Esto significa que pertenecerá al conjunto de no terminales.

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

Y las reglas son:

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

Las reglas gramaticales anteriores pueden parecer algo crípticas al principio. Pero si miramos con atención, podemos ver un patrón que se genera a partir de estas reglas.

Una mejor manera de pensar en las reglas anteriores es visualizarlas en forma de estructura de árbol. En ese árbol podemos poner S en la raíz y nounPhrase y verbPhrase pueden agregarse como hijos de la raíz. Podemos proceder de la misma manera con nounPhrase y verbPhrase también. El árbol tendrá terminales como sus nodos hoja porque ahí es donde terminamos estas derivaciones.

En la imagen de arriba podemos ver que S (un no terminal) deriva dos no terminales NP ( sustantivoPhrase ) y VP ( verbPhrase ). En el caso de NP , ha derivado dos no terminales, Adj y Noun .

Si nos fijamos en la gramática, NP también podría haber elegido Adj y SustantPhrase . Al generar texto, estas elecciones se realizan de forma aleatoria.

Y, finalmente, los nodos hoja tienen terminales que están escritos en negrita. Entonces, si se mueve de izquierda a derecha, puede ver que se forma una oración.

El término que se utiliza a menudo para este árbol es un árbol de análisis. Podemos crear otro árbol de análisis sintáctico para una oración diferente generada por esta gramática de manera similar.

Ahora continuemos con el código. Como mencioné anteriormente, usaremos una biblioteca de JavaScript llamada Tracery para la generación de texto usando CFG. También escribiremos código en HTML y CSS para la parte del front-end.

El código

Comencemos por obtener primero la biblioteca de tracería. Puede clonar la biblioteca de GitHub aquí. También dejé el enlace al repositorio de GitHub de galaxykate al final del artículo.

Antes de usar la biblioteca tendremos que importarla. Podemos hacer esto simplemente en un archivo HTML como este.

He agregado el archivo de tracería clonado como un script en mi código HTML. También tendremos que agregar JQuery a nuestro código porque la tracería depende de JQuery. Finalmente, agregué app.js, que es el archivo donde agregaré reglas para la gramática.

Una vez hecho esto, cree un archivo JavaScript donde definiremos nuestras reglas gramaticales.

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

Aquí notará que la sintaxis para definir reglas no es muy diferente de cómo definimos nuestra gramática anteriormente. Hay diferencias muy pequeñas, como la forma en que se definen los no terminales entre los símbolos de almohadilla. Y también la forma en que se escriben las diferentes derivaciones. En lugar de utilizar el "|" símbolo para separarlos, aquí colocaremos todas las diferentes derivaciones como diferentes elementos de una matriz. Aparte de eso, usaremos el punto y coma en lugar de flechas para representar la transición.

Esta nueva gramática es un poco más complicada que la que definimos anteriormente. Éste incluye muchas otras cosas como determinantes, verbos transitivos y verbos intransitivos. Hacemos esto para que el texto generado se vea más natural.

Llamemos ahora a la función de tracería "createGrammar" para crear la gramática que acabamos de definir.

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