ANALISIS SINTACTICOANALISIS SINTACTICOParte IParte I

Universidad Nacional de JujuyFacultad de Ingeniería

COMPILADORESCOMPILADORES

Elizabeth Reinoso edrreinoso@fi.unju.edu.ar

Objetivos del Tema

Introducir el funcionamiento de un A. sintáctico

Introducir términos utilizados Presentar la especificación en forma

de gramáticas Identificar los tipos de analizadores

sintácticos

Eliz2abeth Reinoso: edrreinoso@fi.unju.edu.ar

Índice General

Introducción Árboles de análisis sintáctico Especificación de un analizador

sintáctico Tipos de analizadores sintácticos

Elizabeth Reinoso: edrreinoso@fi.unju.edu.ar

Introducción Función

Comprobar el orden en que llegan los tokens

Construir una representación del programa fuente

Si es sintacticamente incorrecto generar error

Elizabeth Reinoso: edrreinoso@fi.unju.edu.ar

Fuente Analizador Léxico

Tabla de Símbolo

AnalizadorSintácticoTOKENS

Siguiente Token()

Introducción

Función principalEl parser es la unidad que guía todo

el proceso, o casi todo, de la compilación, ya que por un lado va solicitando al lexer los tokens y al mismo tiempo va dirigiendo el proceso de análisis semántico y generación de código intermedio.

Funcionamiento Obtienen un árbol teórico que permite

expresar el orden de los lexemas, según van apareciendo.

Ese árbol debe ser el modelo de donde sale el análisis semántico.

Para generar un parser tenemos 2 tecnicas:

A manos Mediante herramientas que lo generan

automáticamente. Para que un AS funcione debemos

especificar el lenguaje que debe leer El lenguaje debe ser formal (tener

reglas bien definida) Estas reglas se llaman gramáticas.

Programa fuente

lexer

Parser

Árbol de análisis

sintáctico

Tablas de símbolos y de tipos

token

Diseño de gramáticas

EjemploE::=E+T|T

T::=T*F|F

F::=id|F|(E)

Si queremos construir una cadena de tokens que sean generados por una gramática, podemos hacerlo aplicando las reglas de la gramática.

Por ejemplo: dada la siguiente gramática:

E::=E+E|E*E|num|id|(E)

Intentaremos derivar el tokens: id1+id2*id3Por la izq: E::=E*E=>E+E*E=>id1+E*E=>id1+id2*E=>id1+id2*id3

Diseño de Gramaticas

Para construir el árbol sintáctico

E

EE

EE

*

id3+

id2id1

Dificultades

La recursividad: se expresa por medio de una o mas reglas no recursivas que son la base y una o mas regla que son recursivas y que permite hacer crecer la estructura del lenguaje aplicándose así misma una y otra vez

A::=aAb

Dificultades

La ambigüedad: cuando una gramática contiene una cadena para la que hay mas de un árbol de análisis sintáctico se dice que es ambigua.

Debido a que una gramática de estas característica permite que a partir del mismo código fuente se puedan obtener diferentes códigos intermedios, no es valida para construir un compilador.

Dificultades

La ambigüedadSi una gramática tiene alguna de estas característica

podremos afirmar que es ambigua Gramatica con ciclo: S::=A|S::=a|A::=S Gramatica con alguna regla de la forma: E::=E…..E Gramatica que ofrezcan caminos alternativos

S::=B|S::=C|B::=C Producciones recursivas en las que las variables no

recursivas de la produccion puedan derivar a la cadena vacia

S::=ABS|S::=s|A::=a|λ|B::=b|a|λ

Dificultades

La asociatividad: es cuando se operan tres o mas operandos

Por ejemplo:6/3/2, si el operador tiene asociatividad por la izquierda, primero se opera 6/3 y el resultado con /2

La precedencia: indica el orden en el que se aplicara respecto a los demas operadores en caso de poder aplicar mas de uno. Es decir si en una regla podemos aplicar mas de un operador, comenzaremos aplicando el de mas precedencia y terminaremos por aplicar el de menor precedencia

Dificultades

La parentizacion: incluir paréntesis a la hora de evaluar expresiones en una gramática, se añade una variable que produzca expresiones entre paréntesis. Los operandos se ponen a la mayor distancia posible del símbolo inicial (porque tiene la mayor precedencia)

Análisis Sintáctico Lineal

Hay varios algoritmos de análisis sintáctico (incluso para gramáticas ambiguas), pero su coste computacional es elevado. Si se consigue eliminar la ambigüedad, podemos utilizar 2 estrategias:

Análisis descendentes: partimos de la raíz del árbol sintáctico y aplicamos las reglas por la izquierda (LL(k))

Análisis ascendentes: partimos de la cadena de entrada y construimos el árbol a partir de las hojas para llegar a la raíz (LR(k))

Tipos de Analizadores

AnalizadoresSintácticos

Descendentes

Ascendentes

LL(1)

SLR (1)

LR (1)

LALR (1)

Es predictivo, solo necesita un componente léxico

Se aplica las producciones de izquierda

Orden de lectura de la entrada de izquierda a derecha

Diagrama de Sintaxis

Son grafos dirigidos donde los elementos no terminales de la gramática aparecen como rectángulos y los terminales como círculos o elipses

Todo diagrama de sintaxis se supone que tiene un origen y un destino aunque no se dibujan.

Diagrama de sintaxis

Correspondencia entre la notación BNF y los diagramas de sintaxis.

BNF Diagrama de sintaxis

AB

A|B

A|λ

A B

A

B

A

Diagrama de Sintaxis

BNF Diagrama de sintaxis

(A)*

(A)+

A

A

Ejemplos

Secuencia::=(sentencia “;”)+

Sentencia::=identificador “=“ Numero

Sentencia ;

Ejercicios

Diseñar una gramática no ambigua para el lenguaje de las expresiones que se pueden construir con true y false y los operadores booleanos or, and, not y paréntesis. La precedencia de mayor o menor es not and or los dos últimos son asociativos por la derecha

Ejercicios

Crear los diagramas de sintaxis para esta gramática:

Programa::=Declaraciones Sentencias

Declaraciones::=(Decl “;”)+

Decl::=Entero Identificador

Sentencia::=(Asignacion “;”)+

Asignacion::=ParteIzq “=“ ParteDer

ParteIzq::=Identificador

ParteDer::=Expresion

Expresion::=(Expresion “+” Expresion)|(Expresion “-” Expresion)

Expresion::= (Identificador | Numero)