CSI XIV: Lenguajes y gramáticas (I)
Éste post pretende ser, no exactamente una continuación, sino un complemento a éste post acerca del lenguaje de las máquinas. Recordando un poco de qué iba, vimos cómo en principio las instrucciones recibidas por máquinas y computadores eran de tipo mecánico. Con el tiempo se pudo almacenar estas instrucciones en forma de memorias magnéticas donde series de niveles de tensión determinaban el comportamiento de los componentes del procesador.
Se desarrollaron luego distintos niveles de abstracción sobre el lenguaje en el que se expresaban estas instrucciones (programas). El lenguaje ensamblador consistía en una serie secuencial de códigos que representaban directamente las instrucciones que podía ejecutar un procesador. Era completamente dependiente del mismo. Sin embargo, por encima del ensamblador surgieron lenguajes con un nivel mayor de abstracción, independientes de la máquina en el lenguaje que emplean. Se les llama lenguajes de alto nivel. Los lenguajes más empleados hoy en día son de este tipo, aunque hay muchas diferencias entre ellos.
En el post de hoy generalizaremos la representación de un lenguaje de alto nivel y veremos en qué medida sus conceptos son tomados de la lingüística y se basan en la teoría de grupos.
Empezaremos desde abajo: llamamos alfabeto a un conjunto finito de símbolos (que llamaremos letras). Una palabra es una secuencia de finita de letras de un alfabeto. Hasta ahí todo normal, ¿no?. Venga un ejemplo: Δ es un alfabeto compuesto por las letras a y b. No nos liemos con más. Algunas palabras posibles sobre ese alfabeto son aaaab o baaba. Al conjunto de todas las palabras que se pueden formar con este alfabeto se le denomina el lenguaje universal sobre el alfabeto Δ, siempre que incluyamos en el mismo la palabra vacía λ (lambda). La palabra vacía tiene longitud 0.
Dado que el lenguaje es un conjunto, se pueden realizar operaciones sobre el mismo y, dependiendo de las propiedades que cumpla, le daremos un nombre u otro. Eso se lo dejaremos a los matemáticos.
Los lenguajes universales, pese a ser fascinantes por sus propiedades (digo yo) de poco nos sirven en la práctica. Volviendo a un plano más cercano a la vida real, los seres humanos no sólo empleamos un conjunto finito de palabras, sino que además empleamos un orden determinado entre ellas. A este orden se le denomina sintaxis. Y la gramática determina las reglas en las que se deben combinar las palabras.
En informática (y matemáticas) una gramática tiene una definición formal: consta de un conjunto de terminales, un conjunto de no-terminales (o símbolos auxiliares), un símbolo no-terminal inicial y un conjunto de las reglas de producción. Las reglas de producción determinan la generación de las palabras del lenguaje. Con un ejemplo esto queda clarísimo.
Nuestro alfabeto Δ = {a,b,&lambda} podría ser el conjunto de terminales. S será el símbolo no terminal inicial y A es el otro no terminal. Las reglas de producción podrían ser estas (enseguida las explico):
A := aS | bA
S -> bS -> bλ: b forma parte del lenguaje.
S -> bS -> baA -> babA -> babaS -> babaλ : baba forma parte del lenguaje.
¿Por qué no prueban a jugar siguiendo las reglas? Verán que todas las palabras tienen 0 o un número par de aes.
Y ahora es el momento de cambiar de post, porque si no, esto queda muy largo. Vayamos al siguiente para ver qué tiene esto que ver con los lenguajes de programación...
Posts relacionados
0 cosillas:
Publicar un comentario