CSI XIV: Lenguajes y gramáticas (i II)
Es obligatorio leer el post anterior...
Nos habíamos quedado en una pregunta: ¿Cómo se relaciona las gramáticas formales con los lenguajes de programación de alto nivel? Pues verán, los lenguajes de programación están especificados mediante una gramática que determina la secuencia de palabras aceptable en un programa. Y nosotros, los humanos, hacemos algo parecido cuando queremos entendernos. Si yo les digo "rosa un pasea perro tranquilamente" no estoy hablando español, por más que las palabras que gaste existan en la lengua española. Existe una gramática que debo cumplir.
Es importante notar una diferencia respecto al ejemplo anterior de las aes y las bes. Lo que antes eran letras que conformaban el alfabeto ahora se corresponden con palabras que integran el vocabulario. Las reglas de la gramática castellana se aplican a las palabras, las cuales reciben categorías gramaticales, como sustantivo, adjetivo, verbo, etc. En informática en vez de palabras hablamos de tokens. Tokens típicos son identificador, declaración, expresión...
Vamos a crear una sencilla gramática, que será una burda imitación de nuestro lenguaje. Los símbolos no terminales serán: ORACIÓN, SUJETO, PREDICADO, DETERMINANTE, SUSTANTIVO, VERBO, ADJETIVO y ADVERBIO. Los no terminales serán el conjunto {un, el, este, aquel, perro, gato, pastel, azul, pequeño, pasea, camina, garbosamente, rápidamente}.
En primer lugar estableceremos la relación entre los terminales y las categorías gramaticales representadas por símbolos no terminales. En nuestro caso esto es evidente y la representación se entenderá fácilmente:
SUSTANTIVO = {"perro", "gato", "pastel"}
VERBO = {"pasea", "camina"}
ADJETIVO = {"azul", "pequeño"}
ADVERBIO = {"garbosamente", "rápidamente"}
Si la secuencia de letras corresponde a una palabra con un no-terminal asociado viene determinado por el análisis léxico. Garvosamente no es un adverbio, por mucho que lo parezca: es una burrada. Decimos entonces que se trata de un error léxico.
Nuestra gramática relaciona los símbolos no terminales y tiene esta pinta, que seguro les sonará del cole:
SUJETO := DETERMINANTE SUSTANTIVO | DETERMINANTE SUSTANTIVO ADJETIVO
PREDICADO := VERBO | VERBO ADVERBIO
Tomando el no-terminal ORACIÓN como símbolo inicial, ya pueden dedicarse a averiguar si los siguientes secuencias de palabras caen dentro de nuestro pequeño lenguaje. Por ejemplo, son parte de nuestro lenguaje: este perro azul camina rápidamente, un gato pasea o Este pastel azul camina garbosamente. En el último caso la oración no tiene ningún sentido, pero es sintácticamente impecable. El último paso para dotar de sentido una oración en un lenguaje es realizar un análisis semántico. En las lenguas naturales éste depende del contexto y es posible que en cierto ámbito pudiera tener sentido que un pastel caminara y, además, lo hiciera con cierto estilo.
Nuestra especificación de un lenguaje deja mucho que desear, por supuesto y sólo recuerda vagamente a los idiomas que hablamos. Los lenguajes que usamos los humanos son lenguajes naturales y la mayoría de las gramáticas que emplean son ambiguas, esto es, para una secuencia de entrada admiten distintas interpretaciones. Los lenguajes informáticos tratan de eliminar toda posible ambigüedad mediante reglas expresas en el tratamiento de la entrada, reglas de precedencia... sin embargo hay ocasiones en los que el comportamiento del compilador, que es quien debe leerse el programa y determinar su validez, se deja sin determinar.
Y en este punto ha aparecido un concepto nuevo: el compilador. El compilador es un programa que, tomando un conjunto de archivos con un lenguaje que podemos entender, genera un archivo ejecutable: una imagen en memoria que se puede ejecutar. Un programa, vamos. Y para entender lo que pone en el fichero, el compilador tiene que realizar las mismas acciones que acabamos de describir.
Es decir, que el compilador primero lee letra a letra el archivo y crea una secuencia de tokens. En nuestra analogía, si el compilador tomara como entrada una frase como Un pastel pasea azul, la salida del análisis léxico sería la secuencia: DETERMINANTE SUSTANTIVO VERBO ADJETIVO. El compilador a veces duda: si lee una p tras un espacio no sabe si corresponde a un SUSTANTIVO (pastel, perro) a un VERBO (pasea) o a un ADJETIVO (pequeño). Y a veces el programador piensa que el compilador va a entender una cosa y entiende otra. (Estoy en condiciones de poner ejemplos a petición de los informáticos).
Con la secuencia de tokens formada, el compilador toma el símbolo inicial de la gramática y juega a validar esa secuencia con las reglas de la misma (análisis sintáctico). De este modo decide si un programa es correcto. Que un programa sea sintácticamente correcto no significa que funcione como el programador espera, del mismo modo que nuestro ejemplo del pastel paseante funcionaba sintácticamente sin tener sentido. A veces las frases sin sentido nos hacen gracia, pero un programa sin sentido no hace ni puta gracia.
En serio.
Precisamente leí hace poco que el primer compilador fue desarrollado por una mujer, Grace Hopper, una de las pioneras de la informática. Programó los computadores más importantes de la época (años 50 y 60) y partici´po en el desarrollo de los lenguajes COBOL y FORTRAN, dos de los lenguajes con más arraigo entre los matemáticos y físicos y que son tan buenos que hoy en día, más de 40 años después, se siguen empleando
En resumen, quizá hayan visto ustedes el código de algún programa y les haya parecido complicadísimo (sin contar que hay gente que escribe código fatal). Desengáñense. Ese lenguaje hay un conjunto relativamente reducido de tokens y su gramática es tremendamente más sencilla y restrictiva que todo aquello que les enseñaron en el cole, con sus excepciones y dialectismos.
¡Los programadores estamos, definitivamente, sobrevalorados!
En la wikipedia podemos ver un diagrama sencillo de cómo actúa un compilador.
Posts relacionados
0 cosillas:
Publicar un comentario