PDF de programación - Procesadores de Lenguajes - Tema 3.I. Análisis sintáctico

UNIVERSIDAD NACIONAL DE EDUCACIÓN A DISTANCIA

Escuela Técnica Superior de Ingeniería Informática

Procesadores de Lenguajes

Tema 3
Tema 3

Parte I
Parte I

Análisis Sintáctico
Análisis Sintáctico

Javier Vélez Reyes
[email protected]

Javier Vélez Reyes [email protected]

Objetivos del Tema
Objetivos del Tema

Intruducir el funcionamiento de un A. sintáctico
el funcionamiento de un A. sintáctico
(cid:132)(cid:132) Intruducir
Introducir términos utilizados
(cid:132)(cid:132) Introducir términos utilizados
Presentar la especificación en forma de gramáticas
(cid:132)(cid:132) Presentar la especificación en forma de gramáticas
Identificar los tipos de analizadores sintácticos
(cid:132)(cid:132) Identificar los tipos de analizadores sintácticos

1

Javier Vélez Reyes [email protected]

Índice General
Índice General

Introducción
(cid:132)(cid:132) Introducción
Árboles de análisis sintáctico
(cid:132)(cid:132) Árboles de análisis sintáctico
Especificación de un analizador sintáctico
(cid:132)(cid:132) Especificación de un analizador sintáctico
Tipos de analizadores sintácticos
(cid:132)(cid:132) Tipos de analizadores sintácticos

Javier Vélez Reyes [email protected]

Introducción
Introducción

Función
(cid:132)(cid:132) Función
Comprobar el orden en que llegan los tokens
(cid:132)(cid:132) Comprobar el orden en que llegan los tokens
Construir una representación del programa fuente
(cid:132)(cid:132) Construir una representación del programa fuente
Si es sintacticamente incorrecto generar error
(cid:132)(cid:132) Si es sintacticamente incorrecto generar error

fuente

Analizador
Analizador
Léxico
Léxico

SiguienteToken()

Token

Analizador
Analizador
Sintáctico
Sintáctico

Tabla de
Tabla de
Símbolos
Símbolos

2

Javier Vélez Reyes [email protected]

Índice General
Índice General

Introducción
(cid:132)(cid:132) Introducción
Árboles de análisis sintáctico
(cid:132)(cid:132) Árboles de análisis sintáctico
Árbol Sintáctico
(cid:132)(cid:132) Árbol Sintáctico
Árbol de Análisis sintáctico
(cid:132)(cid:132) Árbol de Análisis sintáctico
Derivaciones
(cid:132)(cid:132) Derivaciones
Derivación por la izquierda
(cid:132)(cid:132) Derivación por la izquierda
Derivación por la derecha
(cid:132)(cid:132) Derivación por la derecha
Frases y formas de frase
(cid:132)(cid:132) Frases y formas de frase
Especificación de un analizador sintáctico
(cid:132)(cid:132) Especificación de un analizador sintáctico
Tipos de analizadores sintácticos
(cid:132)(cid:132) Tipos de analizadores sintácticos

Javier Vélez Reyes [email protected]

Árbol sintáctico
Árbol sintáctico

Árbol sintáctico
(cid:132)(cid:132) Árbol sintáctico
Representación abstracta
(cid:132)(cid:132) Representación abstracta
Operadores en nodos no terminales
(cid:132)(cid:132) Operadores en nodos no terminales
Operandos en nodos terminales
(cid:132)(cid:132) Operandos en nodos terminales

A := B + C

Árbol sintáctico

:=

A

+

B

C

3

Javier Vélez Reyes [email protected]

Árbol de análisis sintáctico
Árbol de análisis sintáctico

Árbol de análisis sintáctico
(cid:132)(cid:132) Árbol de análisis sintáctico
Representación gramatical de una frase
(cid:132)(cid:132) Representación gramatical de una frase
No terminales en nodos no terminales
(cid:132)(cid:132) No terminales en nodos no terminales
Axioma en nodo raíz
(cid:132)(cid:132) Axioma en nodo raíz
Terminales en nodos terminales
(cid:132)(cid:132) Terminales en nodos terminales

E :=
E :=
E :=
E :=

E + E
E * E
n
(E)

2 + 3 * 5

E

+

E

3

E

2

E

*

E

5

Javier Vélez Reyes [email protected]

Derivaciones
Derivaciones

Derivaciones
(cid:132)(cid:132) Derivaciones
Las producciones gramaticales son reglas de reescritura
(cid:132)(cid:132) Las producciones gramaticales son reglas de reescritura
Una derivación es un proceso de reescritura
(cid:132)(cid:132) Una derivación es un proceso de reescritura
Tipos
(cid:132)(cid:132) Tipos
Derivación más a la izquierda
(cid:132)(cid:132) Derivación más a la izquierda

E => - E => - (E + E) => - (id + E) => - (id + id)

Derivación más a la derecha
(cid:132)(cid:132) Derivación más a la derecha

E => - E => - (E + E) => - (E + id) => - (id + id)

E :=
E :=
E :=
E :=
E :=

E + E
E * E
(E)
- E
id

- (id + id)

4

Javier Vélez Reyes [email protected]

Frases y formas de frase
Frases y formas de frase

Frase
(cid:132)(cid:132) Frase
Una frase de una gramática G es una colección de
(cid:132)(cid:132) Una frase de una gramática G es una colección de
símbolos terminales obtenidos de la aplicación de una
símbolos terminales obtenidos de la aplicación de una
derivación múltiple sobre las reglas de G
derivación múltiple sobre las reglas de G

- (id + id)

Forma de frase
(cid:132)(cid:132) Forma de frase
Una forma de frase de una gramática G es una colección
(cid:132)(cid:132) Una forma de frase de una gramática G es una colección
de símbolos terminales y no terminales obtenidos de la
de símbolos terminales y no terminales obtenidos de la
aplicación de una derivación múltiple sobre las reglas de
aplicación de una derivación múltiple sobre las reglas de
GG

- (id + E)

Javier Vélez Reyes [email protected]

Índice General
Índice General

Introducción
(cid:132)(cid:132) Introducción
Árboles de análisis sintáctico
(cid:132)(cid:132) Árboles de análisis sintáctico
Especificación de un analizador sintáctico
(cid:132)(cid:132) Especificación de un analizador sintáctico
Especificación formal
(cid:132)(cid:132) Especificación formal
Gramáticas Independientes del contexto
(cid:132)(cid:132) Gramáticas Independientes del contexto
Recursividad
(cid:132)(cid:132) Recursividad
Ambigüedad
(cid:132)(cid:132) Ambigüedad
Asociatividad
(cid:132)(cid:132) Asociatividad
Precedencia
(cid:132)(cid:132) Precedencia
Parentización
(cid:132)(cid:132) Parentización

Tipos de analizadores sintácticos
(cid:132)(cid:132) Tipos de analizadores sintácticos

5

Javier Vélez Reyes [email protected]

Especificación de analizador sintáctico
Especificación de analizador sintáctico
Especificación formal
(cid:132)(cid:132) Especificación formal
Gramáticas Independientes del contexto
(cid:132)(cid:132) Gramáticas Independientes del contexto
Lenguajes Independientes del contexto
(cid:132)(cid:132) Lenguajes Independientes del contexto
Autómatas a pila
(cid:132)(cid:132) Autómatas a pila

Gramáticas
Gramáticas

Independientes
Independientes
del contexto
del contexto

Autómatas
Autómatas

A Pila
A Pila

ISOMORFO
ISOMORFO

Lenguajes
Lenguajes

Independientes
Independientes
del contexto
del contexto

Javier Vélez Reyes [email protected]

G. independientes del contexto I
G. independientes del contexto I

Gramática Independiente del contexto
(cid:132)(cid:132) Gramática Independiente del contexto
Un conjunto de símbolos no terminales {A, B, C, … S}
(cid:132)(cid:132) Un conjunto de símbolos no terminales {A, B, C, … S}
Un conjunto de símbolos terminales {a, b, c, …}
(cid:132)(cid:132) Un conjunto de símbolos terminales {a, b, c, …}
Un símbolo no terminal, llamado axioma S
(cid:132)(cid:132) Un símbolo no terminal, llamado axioma S
Un conjunto de reglas de producción de la forma A := αα
(cid:132)(cid:132) Un conjunto de reglas de producción de la forma A :=

G = { N, T, S, P}

N = { S, L}
T = { id, ‘,’ }
P = { S := L,

L := L , id
L := id }

6

Javier Vélez Reyes [email protected]

G. independientes del contexto II
G. independientes del contexto II

Recursividad
(cid:132)(cid:132) Recursividad
Permite definir estructuras sintácticas complejas
(cid:132)(cid:132) Permite definir estructuras sintácticas complejas
utilizando un número
utilizando un

número pequeño de reglas de producción
pequeño de reglas de producción

Estructura
(cid:132)(cid:132) Estructura
Escritura de casos base
(cid:132)(cid:132) Escritura de casos base

L :=

id

Escritura de casos recursivos
(cid:132)(cid:132) Escritura de casos recursivos

S :=
L :=

L
L , id

Javier Vélez Reyes [email protected]

G. independientes del contexto III
G. independientes del contexto III

Ambigüedad
(cid:132)(cid:132) Ambigüedad
G es ambigua si el lenguaje que define contiene alguna
(cid:132)(cid:132) G es ambigua si el lenguaje que define contiene alguna
frase para la que exista más de un árbol de análisis
frase para la que exista más de un árbol de análisis
sintáctico para G
sintáctico para G

2+3*5

E

2

E

+

E

3

E

*

(cid:57)

E

5

(cid:56)

E

2

E

+

E

*

E

3

E

5

E :=
E :=
E :=
E :=

E + E
E * E
n
(E)

Problemas
(cid:132)(cid:132) Problemas
La frase puede significar cosas diferentes
(cid:132)(cid:132) La frase puede significar cosas diferentes
No es eficiente construir analizadores ambiguos
(cid:132)(cid:132) No es eficiente construir analizadores ambiguos

7

Javier Vélez Reyes [email protected]

G. independientes del contexto IV
G. independientes del contexto IV

No Ambigüedad
(cid:132)(cid:132) No Ambigüedad
Sólo un árbol de análisis sintáctico por cada frase
(cid:132)(cid:132) Sólo un árbol de análisis sintáctico por cada frase
Es difícil reconocer la no ambigüedad
(cid:132)(cid:132) Es difícil reconocer la no ambigüedad
Reglas de ambigüedad
(cid:132)(cid:132) Reglas de ambigüedad
(cid:132)(cid:132) Gramáticas con ciclos
(cid:132)(cid:132) Reglas de la forma
(cid:132)(cid:132) Caminos alternativos
(cid:132)(cid:132) Recursivas con
(cid:132)(cid:132) No terminales que derivan en

Gramáticas con ciclos {S := A, S := a, A := S}
Reglas de la forma {E := E…E}
Caminos alternativos {S := A, S := B, A := B}
Recursivas con εε en casos base
No terminales que derivan en εε {S:= HR, H:= h|ε, H:= h|ε}

en casos base {S:=HRS, S:=s,H:=h|ε, R:=r|ε}

Javier Vélez Reyes [email protected]

G. independientes del contexto V
G. independientes del contexto V

Asociatividad
(cid:132)(cid:132) Asociatividad
La asociatividad de un operador binario define cómo se
(cid:132)(cid:132) La asociatividad de un operador binario define cómo se
operan tres o más operandos con dicho operador
operan tres o más operandos con dicho op