Análisis sintactico de un compilador

Cadena de tokens

Árbol Sintáctico

ANÁLISIS SINTÁCTICO
1

Análisis Sintáctico
2



Funciones


Comprobar que la secuencia de componentes léxicos cumple las reglas de la gramática Generar el árbol sintáctico Son especificaciones sintácticas y precisas de lenguajes Se puede generar automáticamente un analizador El proceso de construcción puede llevar a descubrir ambigüedadesImparte estructura al lenguaje de programación, siendo más fácil generar código y detectar errores Es más fácil ampliar y modificar el lenguaje





Ventajas de utilizar gramáticas
  





1

Analizador Sintáctico, Tipos
3



Tres tipos generales de analizadores sintácticos:


Métodos Universales: Cocke-Younger-Kasami y Earley
 

Sirven para cualquier gramática Muyineficientes Construyen el árbol de análisis sintáctico desde arriba (raíz, axioma) hasta abajo (hojas, terminales)
 



Descendentes (top-down)


Analizadores Descendentes Recursivos Analizadores LL(1) con tabla



Ascendentes (bottom-up)


Construyen el árbol de análisis sintáctico desde abajo hacia arriba
 

Analizadores de Precedencia de Operador Analizadores LR(1)Analizador Sintáctico
4



Tanto para el análisis descendente como para el ascendente:
 

La entrada se examina de izquierda a derecha, un símbolo cada vez Trabajan con subclases de gramáticas LR(k)  LL(k) En la práctica solo se utilizan LR(1) y LL(1)



En general las gramáticas serán LL y LR
 





Muchos compiladores se llaman “parser-driven” debido a que elanalizador sintáctico es el que llama al léxico Existen herramientas para generar automáticamente analizadores sintácticos (YACC, Bison)

2

Análisis Sintáctico Descendente
5



Algoritmo
1. 2.

Poner el axioma como raíz del árbol de derivación Hasta que solo haya símbolos terminales, derivar más a la izquierda



Ejemplo
 

Entrada: Id.*.Id.+.Id Gramática:Expresión::=Expresión.*.Término | Expresión.+.Término | Término Término ::= Id | Número



Derivación:
Expresión  Expresión.+.Término  Expresión.*.Término.+.Término  Término.*.Término.+.Término  Id.*.Término.+.Término  Id.*.Id.+.Término  Id.*.Id.+.Id

Análisis Sintáctico Ascendente
6



Definición: Pivote




Secuencia más larga de símbolos (T y N) en la parte más izquierda de la entrada quese puede encontrar en la parte derecha de una producción y tal que todos los símbolos a su derecha son terminales Ejemplo:
 

Si entrada es: Expresión.*.Término.+.Id el pivote es: Expresión.*.Término



Algoritmo
1. 2.

Empezar con la cadena de entrada Intentar llegar hasta el axioma, encontrando el pivote y reduciéndolo con la producción correspondiente



Ejemplo
Id.*.Id.+.Id Término.*.Id.+.Id  Expresión.*.Id.+.Id  Expresión.*.Término.+.Id  Expresión.+.Id  Expresión.+.Término  Expresión

3

7

Analizadores Sintácticos, Problemas


Descendentes


Mas de una opción: A::=  | 
 

Retroceso Analizar los siguientes elementos de la entrada Eliminación de la recursividad Factorización por la izquierda



Recursividad izquierda


Ambigüedad




Ascendentes


Más de una opción: A::=  y  es el pivote Problemas semánticos



Otros


Análisis Sintáctico Predictivo
8







No necesita realizar retroceso para analizar bien las sentencias del lenguaje Sólo con ver el siguiente carácter de la entrada puede decidir cuál va a ser la siguiente producción a emplear Condiciones
  

Diseñar bien lagramática Eliminar la recursividad izquierda Factorizar por la izquierda

  

No está asegurado el tener una gramática predictiva Las gramáticas son difíciles de leer Para las partes de las gramáticas que no son predictivas se pueden utilizar otros analizadores

4

Análisis Sintáctico Predictivo
9



Árbol sintáctico
 Ejemplo:

Id.*.Id.+.Id

Expresión

Expresión

+...