Analisis Sintactico

DEPARTAMENTO DE MATEMATICAS
CUADERNO DIDACTICO Nº 61

ANALISIS SINTACTICO
EN
PROCESADORES DE LENGUAJE

Juan Manuel Cueva Lovelle
Catedrático de E.U. de Lenguajes y Sistemas Informáticos
Departamento de Matemáticas
Universidad de Oviedo
2ª Edición
Oviedo, Abril 1995

Análisis sintáctico en procesadores de lenguaje

1 INTRODUCCION
El análisis sintáctico (parser en lengua inglesa)toma los tokens que le envia el analizador léxico y comprueba si con
ellos se puede formar alguna sentencia válida del lenguaje. Recuérdese que se entiende por sintaxis como el conjunto de reglas
formales que especifican como se construyen las sentencias de un determinado lenguaje.
La sintaxis de los lenguajes de programación habitualmente se describe mediante gramáticas libres de contexto (ogramáticas tipo 2) utilizando algún tipo de notación. Por ejemplo las notaciones BNF y EBNF. Esta especificación ofrece
numerosas ventajas a los diseñadores de lenguajes y a los escritores de compiladores:
• Una gramática da una especificación sintáctica precisa, y fácil de comprender, de un lenguaje de programación.
• Para ciertas clases de gramáticas se puede construir automáticamente unanalizador sintáctico, que determina si un
programa está bien construido. Como beneficio adicional, el proceso de construcción del analizador sintáctico puede
revelar ambigüedades sintácticas y otras dificultades para la construcción del parser que de otra forma no serían
detectadas en la fase de diseño inicial de un lenguaje y que podrían se arrastradas a su compilador.
• Una gramática biendiseñada da una estructura al lenguaje de programación que se utiliza en la traducción del programa
fuente en código objeto correcto y para la detección de errores. Existen herramientas que a partir de la descripción de
la gramática se puede generar el código del analizador sintáctico.
• Los lenguajes de programación después de un periodo de tiempo, adquieren nuevas construcciones y llevan a cabotareas adicionales. Estas nuevas construcciones se pueden añadir más fácilmente al lenguaje cuando hay una
implementación basada en una descripción gramatical del lenguaje.
El papel del analizador sintáctico dentro de un procesador de lenguaje puede representarse según el esquema de la figura
1.
Manejo de errores

token
programa
fuente

Analizador
léxico

Analizador
sintáctico
pidesiguiente
token

árbol
sintáctico

Analizador
semántico

representación
intermedia

Tabla
de
símbolos

Figura 1: Interfaces del analizador sintáctico

2 GRAMATICAS LIBRES DE CONTEXTO
Habitualmente las estructura sintáctica de los lenguajes de programación se especifica sintácticamente mediante
gramáticas libres de contexto o de tipo 2.

2.1 Derivaciones y árboles sintácticosAnalizar sintácticamente una cadena de tokens es encontrar para ella un árbol sintáctico o derivación, que tenga
como raíz el símbolo inicial de la gramática libre de contexto y mediante la aplicación sucesiva de sus reglas de derivación se
pueda alcanzar dicha cadena como hojas del árbol sintáctico. En caso de éxito la sentencia pertenece al lenguaje generado por
la gramática, y puedeproseguirse el proceso de compilación. En caso contrario, es decir cuando no se encuentra el árbol que
genera dicha gramática, se dice entonces que la sentencia no pertenece al lenguaje, y el compilador emite un mensaje de error,
pero el proceso de compilación trata de continuar. Algunos compiladores paran el proceso de compilación cada vez que
encuentran un error, en ellos es necesario realizar tantascompilaciones como errores tendría el programa fuente.

2.1.1 Ejemplo: gramática de expresiones aritméticas
Supongamos que se desea construir una gramática G={VN, VT, S, P} que describe un lenguaje basado en la utilización
de expresiones aritméticas con sumas, diferencias, productos, divisiones, potenciación, paréntesis, y menos unario. Este lenguaje
también permitirá el uso de constantes...