Análisis Sintactico

Análisis Sintáctico
Cadena de

tokens

Analizador
Sintáctico

Árbol
Sintáctico

En realidad...
Componente léxico

Analizador
Léxico

Obtén otro
componente léxico

Analizador
Sintáctico

Árbol
sintáctico

Tabla de
Símbolos

1

Análisis Sintáctico. Procesadores de Lenguaje I

Análisis Sintáctico
Funciones
Comprobar que la secuencia de componentes
léxicos cumplelas reglas de la gramática
Generar el árbol sintáctico

Ventajas de utilizar gramáticas
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üedades
Imparte estructura al lenguaje de programación,
siendo más fácil generar código y detectar errores
Es más fácil ampliar y modificarel lenguaje

Análisis Sintáctico. Procesadores de Lenguaje I

Analizador Sintáctico, Tipos
Tres tipos generales de analizadores sintácticos:
Métodos Universales: Cocke-Younger-Kasami y Earley
Sirven para cualquier gramática
Muy ineficientes

Descendentes (top-down)
Construyen el árbol de análisis sintáctico desde arriba (raíz,
axioma) hasta abajo (hojas, terminales)
AnalizadoresDescendentes 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)

2

Análisis Sintáctico. Procesadores de Lenguaje I

Analizador Sintáctico
Tanto para el análisis descendente como para el
ascendente:
La entrada se examina de izquierda a derecha, unsímbolo
cada vez
Trabajan con subclases de gramáticas

En general las gramáticas serán LL y LR
LR(k) ⊃ LL(k)
En la práctica solo se utilizan LR(1) y LL(1)

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

Análisis Sintáctico.Procesadores de Lenguaje I

Analizador Sintáctico
Árbol sintáctico

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

Ejemplo: Id.*.Id.+.Id
Expresión

Expresión

Expresión

Término

*

+

Término

Término

Id

Id

Id

3

Análisis Sintáctico. Procesadores de Lenguaje I

Análisis Sintáctico Descendente
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. Procesadores de Lenguaje I

Análisis Sintáctico Ascendente
Definición: Pivote
Secuencia más larga de símbolos (ΣT y ΣN) en la parte más
izquierda de la entrada que se 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
elpivote 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

4

Análisis Sintáctico. Procesadores de Lenguaje IAnalizadores Sintácticos,
Problemas
Descendentes
Mas de una opción: A::= α | β

Retroceso
Analizar los siguientes elementos de la entrada

Recursividad izquierda
Eliminación de la recursividad

Ambigüedad
Factorización por la izquierda

Ascendentes
Más de una opción: A::= α y α es el pivote

Otros
Problemas semánticos

Análisis Sintáctico. Procesadores de Lenguaje I...