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

Introducción al Análisis Sintáctico

Compiladores ITESM-CCM enero-mayo 2013
by

Javier Abdul Córdoba Gándara

on 21 February 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Introducción al Análisis Sintáctico

Análisis Sintáctico -- Estructura -- Técnicas de Parsing Elementos de los métodos Conjunto de primeros Conjunto de Siguientes Conjuntos LR Problemas LL Predictivo LR Shift Reduce Descendente Recursivo Reglas de Reescritura
o Derivación Precedencia y asociatividad Ambigüedad Gramáticas Libres de contexto Símbolos terminales y no terminales
Derivación ordenada
Representación jerárquica de la estructura En un lenguaje de programación interesa
la precisión.

1+2+3 es (1+2)+3 ó 1+(2+3)
1-2-3 es (1-2)-3 ó 1-(2-3)

Representación en árboles de derivación El orden de aplicación de las reglas
de derivación define la precedencia

¿Qué debe aplicarse primero?

La asociatividad se relaciona con la
recursividad en las reglas En un enfoque top down, asumir que la
secuencia a analizar cumple con la gramática.

Aplicar las reglas para probar esta hipótesis.

A -> A b | C d | e
A y los demás no terminales se convierten en
funciones que intentan reconocer cada
alternativa usando backtracking, los tokens
simplemente se descartan al reconocerse.

A partir del conjunto de primeros de un no terminal
se intenta predecir la regla de derivación a ejecutar
(esto se representa previamente en tablas).

En caso de derivaciones vacías se usa el conjunto de
siguientes.

Se procede así mediante una pila, cuando hay match
de tokens se descartan. A partir de un análisis de los conjuntos LR de
la gramática, este método consiste en las siguientes
acciones:

Shift - desplazar un símbolo del input a una pila
cuando aún no puede considerarse dentro de
una regla completa.
Reduce - un conjunto de símbolos que corresponden
a la parte derecha de una regla se reducen (intercambian)
por el no terminal que representan. Recursión izquierda o derecha
Factorización
Ambigüedades comunes en lenguajes de programación

Propiedades de la gramática Conjunto de los terminales con los que
puede comenzar una derivación (de un no terminal)

1) A -> a
2) A -> B, B->a
3) A -> C a, C-> Conjunto de todos los terminales que pueden
aparecer después de una derivación (de un no terminal)

0) $ siempre como siguiente del símbolo inicial
1) A -> B c
2) A -> c B, A -> c B D con D -> Etapas de aplicación de una regla de derivación

A-> a b c

A->. a b c
A-> a . b c
A-> a b . c
A-> a b c .

Recursivamente en no terminales oración = sujeto verbo predicado
sujeto = artículo sustantivo [adjetivo]
verbo = auxiliar conjugación
predicado = objeto directo | objeto indirecto
... etc
Full transcript