Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Traducción dirigida por la sintaxis y analizador descendente

Compiladores. Universidad Mariano Gálvez de Guatemala
by

Guil TGUD

on 28 May 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Traducción dirigida por la sintaxis y analizador descendente

Ejemplos y Ejercicios
Traducción dirigida por la sintaxis

Asocia información a construcciones de un lenguaje de programación, asignándole atributos al símbolo de la gramática que representa dicha construcción.
El valor de los atributos se calcula mediante reglas semánticas que se asocian a cada producción.

Hay dos notaciones:

o Definiciones dirigidas por sintaxis

o Esquemas de traducción (árbol sintáctico)


Definición
Es una generalización de una gramática incontextual en la cual cada símbolo tiene asociado un conjunto de atributos.Hay dos clases de atributos posibles: Atributos Sintetizados y Atributos Heredados
Analizador descendente
Analizador sintáctico descendente (Top-Down-Parser):
Un analizador puede empezar con el símbolo inicial e intentar transformarlo en la entrada, intuitivamente esto sería ir dividiendo la entrada progresivamente en partes cada vez más pequeñas, de esta forma funcionan los analizadores LL, un ejemplo es el javaCC.
Atributos

En general los atributos de un nodo reciben valor mediante la evaluación de las reglas semánticas asociadas a la producción usada en ese nodo propietario del atributo.
Los valores de los atributos sintetizados se calculan a partir de los valores de atributos de sus nodos hijos en el árbol de análisis sintáctico.
Los valores de los atributos heredados se calculan a partir de los valores de atributos de su nodo padre o sus nodos hermanos.

Reglas semánticas

Las reglas semánticas establecen dependencias entre los atributos de los diferentes símbolos.
Esas dependencias se reflejan en un grafo con el fin de establecer un orden de evaluación de las reglas.
La evaluación de las reglas asigna valor a los atributos.
Un árbol de análisis sintáctico que contiene también los atributos y su valores se llama un árbol anotado o decorado.

Traducción dirigida por la sintaxis y analizador descendente
Guilmar Urizar
Jose Daniel Argueta Gómez
Daisy Medrano
Gary Wilson Cano Mota

Arboles Sintetizados


Los atributos sintetizados se utilizan ampliamente.
Si una definición dirigida por sintaxis tiene únicamente atributos sintetizados se dice que es S-atribuida.
El árbol de análisis sintáctico de una gramática S-atribuida puede decorarse mediante un recorrido en post orden.

Arboles Heredados

Sirven para expresar la dependencia que hay entre una construcción del lenguaje de programación y su contexto.
Siempre es posible reescribir una definición dirigida por sintaxis para que sea S-atribuida.
En ocasiones es más natural utilizar atributos heredados

Fuente
https://gramaticasformales.wordpress.com/category/traduccion-dirigida-por-sintaxis/

http://es.wikipedia.org/wiki/Analizador_sint%C3%A1ctico_LL
https://sycg.wordpress.com/2010/12/14/analizador-sintactico-ascendente-y-descendente/

Analizador Sintáctico LL
El analizador sintático LL es un analizador sintáctico descendente, por un conjunto de gramática libre de contexto. En este analizador las entradas son de izquierda a derecha, y construcciones de derivaciones por la izquierda de una sentencia o enunciado. La clase de gramática que es analizable por este método es conocido como gramática LL.
Características
El análisis sintáctico descendente (ASD) intenta encontrar entre las producciones de la gramática la derivación por la izquierda del símbolo inicial para una cadena de entrada.
Parte del axioma de la gramática.
Procesa la entrada de izquierda a derecha.
Escoge reglas gramaticales.
Bueno primeramente para trabajar el análisis sintáctico descendente se debe realizar primeramente algunas operaciones para que la gramática sea LL1 las cuales son:


– ELIMINAR AMBIGUEDAD: Para eliminar la ambigüedad se debe reescribir la gramática.

– ELIMINAR RECURSIVIDAD POR LA IZQUIERDA: Una gramática es recursiva por la izquierda si tiene un nodo Terminal a tal que existe una derivación A->Aα para alguna cadena . Es decir por simple observación podemos identificar.
– Factorizar: Se trata de rescribir las producciones de la gramática con igual comienzo para retrasar la decisión hasta haber visto lo suficiente de la entrada como para elegir la opción correcta.
Análisis Sintáctico Descendente Con Retroceso
El método parte del axioma inicial y aplica todas las posibles reglas al no terminal más a la izquierda.

• Se usa el retroceso para resolver la incertidumbre.
• Sencillo de implementar.
• Muy eficiente.

Ejemplo:
Análisis Sintáctico Descendente Predictivo (Asdp)
El analizador debe realizar la previsión de la regla a aplicar sólo con ver el primer símbolo que produce para que el algoritmo tenga una complejidad lineal.

Las gramáticas que son susceptibles de ser analizadas sintácticamente de forma descendente mediante un análisis predictivo y consultando un únicamente un símbolo de entrada pertenecen al grupo LL(1).

A partir de gramáticas LL(1) se pueden construir analizadores sintácticos descendentes predictivos (ASDP), que son ASD sin retroceso.

Ejemplo:
Full transcript