Conceptos básicos para diseño de lenguajes

 Desde que uno ingresa a la carrera de Ciencias de la computación o Ingeniería en sistemas, siempre se ha tachado que todo lo referente a compiladores es lo más difícil. Es por ello que mediante este espacio se querrán dejar claros conceptos básicos referentes a esta asignatura.

¿Qué es un símbolo?

Símbolo es un carácter o una figura que significa algo, por ejemplo, la "S" o en la antigüedad maya el 0 era representado por una especie de concha. Fácil de entender, ¿no?

¿Qué es un alfabeto?

Un alfabeto es un conjunto de símbolos. El alfabeto que utilizamos {a, b, c, d..., z} es un conjunto de símbolos que nos ayudan a representar algo. También explica por qué este {π, ε,σ...µ} es otro alfabeto.

¿Qué es una cadena?

Básicamente, una cadena es una sucesión de símbolos. Por ejemplo, “arcoíris” es una palabra compuesta por una sucesión de símbolos: {a, r, c, o, í, r, i, s}.

¿Qué es una gramática?

Una gramática es el conjunto de reglas y principios que definen un lenguaje, básicamente, es como representar un lenguaje de forma simplificada. La gramática se compone de los siguientes puntos:

• Un conjunto de símbolos no terminales que son los símbolos intermedios utilizados para describir la estructura de los enunciados del lenguaje. Es decir, estos son símbolos que no son auto conclusivos por sí mismos, dado que estos llevan otros símbolos para poder generar un enunciado del lenguaje.
• Un conjunto de símbolos llamados terminales que en realidad son símbolos para formar enunciados en el lenguaje. Estos, a diferencia de los símbolos no terminales, sí son auto conclusivos por sí mismos.
• La producciones son reglas gramaticales que especifican cómo se construyen los enunciados en el lenguaje. Básicamente, estas reglas son las que estructuran cómo está compuesto el lenguaje en cuestión. 
• Un símbolo inicial que es un no terminal empieza cualquier enunciado del lenguaje. 
  
  

Realmente puede que este sea un tema complejo si no se tiene un ejemplo apropiado, entonces, definamos un ejemplo de una gramática:

• Símbolos no terminales: {O, FN, FV, SUST, VERBO, ART, SUST}
• Símbolos terminales: {Juan Pérez, usa, tiene, una, un, El, sombrero, pluma}
• Producciones (el símbolo "|" denota un or como en la programación):
  {
• O ->FN FV
• FN -> SUST | ART SUST
• FV -> VERBO FN
• FN -> ART SUST
• ART -> un | la | el
• SUST ->  Juan Pérez | sombrero
• VERBO -> tiene | usa
  }
• Símbolo inicial: {O}

Esto un ejemplo de una gramática, donde precisamente FN y FV denotan las dos partes básicas de una oración, frase nominal (sujeto) y frase verbal (predicado), SUST significa sustantivo, ART un artículo, y VERBO un verbo. Ahora hagamos una derivación (construcción de un enunciado del lenguaje a partir de las producciones).

Tal como se observó en la gramática definida se tenía que empezar con el símbolo inicial "O" y este tenía una regla, o una producción, que definió una frase nominal y una frase verbal. Así mismo, se empezó a derivar para que la parte de la frase nominal derivara a la producción que dictaba que podía ser sustantivo. Este sustantivo se derivó a un terminal que es auto conclusivo, significando que ya no se podía derivar más. 
Por otra parte, del lado del predicado se llevó a una separación entre verbo y otra fase nominal. El verbo terminó siendo un terminal, la fase nominal un artículo y loa sustantivos fueron derivados a dos terminales.

¿Qué es un autómata?

Un autómata es una máquina que se utiliza para reconocer lenguajes. Para lograrlo, éste realiza procedimientos sobre una entrada para obtener una salida y así determinar si cierta entrada pertenece o no a un lenguaje. En otras palabras, es un chequeador de lenguajes. Se compone de un conjunto de estados: un estado inicial, un conjunto de caracteres de entrada, conjunto de caracteres de salida y una función de transición que permite moverse a través de la máquina así mismo. Esto puede ser representado por un grafo. 

Existen muchos tipos de autómatas, realmente los que se necesitan entender bien son los AFD's y los AFN's:

• Autómata Finito No Determinista (AFN en español, NFA en inglés): son autómatas que permiten estar en dos estados al mismo tiempo al aceptar transiciones épsilon (ε) o transiciones vacías. De esta manera, existe más de una transición por cada símbolo en un estado. En el autómata de abajo en el estado inicial se encuentra al mismo tiempo en el estado inicial en los estados B y C, dado que esas transiciones épsilon permiten esto.
  
  
  
  
  
• Autómata Finito Determinista (AFD en español, FA en inglés): A diferencia del autómata finito no determinista, este permite que exista solo una transición por cada símbolo en un estado. Por esto, no existen transiciones épsilon, y se debe denotar que existe un autómata finito determinista que represente cada lenguaje representado por un autómata finito no determinista. Por ejemplo, el autómata de abajo representa el autómata generado arriba.
  
  
  
  Otra cosa que se debe destacar es el hecho de que existen algoritmos que permiten convertir un autómata finito no determinista a uno determinista. Así, éste autómata finito determinista se puede simplificar a su forma más básica.
  
  Realmente, estos son los conceptos más básicos para poder empezar a comprender y a dejarle de tener miedo a este curso llamado diseño de lenguajes.