Loading presentation...
Prezi is an interactive zooming 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 3 February 2017

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