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

Análisis Sintáctico Descendente LL(1)

Trabajo de compiladpores, realizado el día 15 de Nov del 2013
by

Freddy Salcedo Ospino

on 16 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Análisis Sintáctico Descendente LL(1)

ANÁLISIS SINTÁCTICO DESCENDENTE LL(1)
Introducción
Un analizador LL es llamado un analizador LL (k) si usa k tokens cuando el analizador ve hacia delante de la sentencia. Si existe tal analizador para cierta gramática y puede analizar sentencias de ésta gramática sin marcha atrás, entonces es llamada una gramática LL (k). De ésta gramáticas, la gramática LL (1), aunque es bastante restrictiva, éstas son muy populares porque los analizadores LL correspondientes sólo necesita ver el siguiente token para hacer el análisis de sus decisiones.

Existe controversia entre la escuela europea del diseño del lenguaje, quien prefiere gramática basada en LL, y los otros países prefieren predominantemente gramática basada en LR. Esto se debe en gran parte a la influencia de Niklaus Wirth en la ETH Zürich en Suiza, cuya investigación ha descrito una serie de maneras de optimizar lenguajes y compiladores LL (1).
.

– análisis DESCENDENTE (Top-Down)
» construye el árbol desde la raíz (S) hasta llegar a las hojas
– análisis ASCENDENTE (Bottom-Up)
» construye el árbol desde las hojas hacia la raíz (S)
Implementación Análisis Sintáctico Descendente
Sobre implementación de analizadores descendentes
– la forma más natural es asociar un procedimiento con cada no terminal.
– cada procedimiento: » comprueba la corrección del token en estudio con el que el propio procedimiento representa incorrecto: mensaje de error y/o estrategia de recuperación
» hacer avanzar al siguiente token
– afinando un poco más:
» no terminal: genera invocaciones
» terminal: concordancia entre terminales
• error sintáctico ó avanzar a token siguiente
El análisis sintáctico descendente LL(1) pueden ser (de vuelta atrás lenta o sin vuelta atrás)
LL(1) Vuelta Atrás Lenta
Análisis descendente determinista:
LL(1) (sin vuelta atrás)
• También se llama “sin vuelta atrás”, en oposición a la técnica descrita al principio del tema.
• También se llama “descenso recursivo” por la técnica de paso automático de la gramática LL(1) al analizador.
• Intuitivamente, la razón de su eficiencia reside en que las partes derechas de cada no terminal pueden considerarse “indexadas” por el siguiente terminal.

• De hecho con LL(1) se puede construir una tabla de doble entrada (no terminales / terminales ) en la que, cada celda, está ocupada solamente por una regla que es la única opción que se puede aplicar cuando en el “árbol sintáctico” corresponda tratar el no terminal y en el recorrido del programa toque tratar el terminal.
Conclusión
Uno de los objetivos de este tema es demostrar que se pueden construir fácilmente analizadores de tipo LL(1) (la entrada se lee desde la izquierda – left – las derivaciones en el árbol se hacen de izquierda – left – a derecha y se necesita conocer sólo 1 símbolo de la entrada por anticipado) si la gramática se puede expresar en forma adecuada
Gramática LL(1) mediante la construcción
de la tabla de análisis descendente
Uso de la tabla para el análisis descendente
Vídeo Tutorial
Full transcript