Análisis Sintáctico Predictivo No Recursivo

Sección 4.4Leonel Morales Díaz

leonel@ingenieriasimple.com

Copyright 2008 by Leonel Morales Díaz – Ingeniería Simple.Derechos reservados Disponible en: http://www.ingenieriasimple.com/compiladores

Modelo analizador sintáctico predictivo no recursivo

Programa para análisis sintáctico

predictivo

Tabla de análisis sintáctico M

a + b $

X

Y

Z

$

PILA

ENTRADA

SALIDA

M[X,+]

Ejemplo

E => TE’ E’ => +TE’ | nilT => FT’ T’ => *FT’ | nilF => (E) | id

No Terminal id + * ( ) $

E E => TE' E => TE'E' E' => TE' E' => nil E' => nilT T => FT' T => FT'T' T' => nil T' => *FT' T' => nil T' => nilF F => id F => (E )

Símbolo de entrada

PILA ENTRADA SALIDA

$E id + id * id$$E'T id + id * id$ E => TE'$E'T'F id + id * id$ T => FT'$E'T' id id + id * id$ F => id$E'T' + id * id$$E' + id * id$ T' => nil$E'T+ + id * id$ E' => +TE'$E'T id * id$$E'T'F id * id$ T => FT'$E'T' id id * id$ F => id$E'T' * id$$E'T'F * * id$ T' => *FT'$E'T'F id$$E'T' id id$ F => id$E'T' $$E' $ T' => nil$ $ E' => nil

Primero y Siguiente Primero(α)

Conjunto de terminales Que inician las cadenas de α Si α =>* nil

nil también está en Primero(α)

Primero y Siguiente Siguiente(A)

Conjunto de terminales a Que pueden aparecer a la derecha de

A S =>* αAaβ para algún α y β Obsérvar

S =>* αABCaβ a pertenece a Siguiente(A) si:

B =>* nil C =>* nil

Construcción de tabla M M [X, x] X no terminal, x terminal Para cada A => α

Para cada terminal a de Primero(α) Añadir A => α a M[A,a]

Si nil está en Primero(α) Añadir A => α a M[A,b]

Para cada b de Siguiente(A)

Si nil está en Primero(α) y $ en Siguiente(A) Añadir A => α a M[A,$]

Toda entrada vacía de M es error

Ejemplo Construír M para

P => i E t PP’ | aP’ => e P | nilE => b

Gramáticas LL(1) Gramática con M sin entradas

múltiples L de “left”

Se analiza la entrada de izquierda a derecha

L de “left derivative” Se deriva por la izquierda

(1) de que solo se analiza un token anticipadamente

Propiedades LL(1) No pueden ser ambiguas No pueden ser recursivas por la

izquierda