Organización de Lenguajes y Compiladores 1
description
Transcript of Organización de Lenguajes y Compiladores 1
Organización de Lenguajes y Compiladores 1 Método de análisis sintáctico LL1
Método Descendente LL(1)
La primera L representa el tipo de lectura de la cadena de entrada Left (de izquierda a derecha)
La segunda L representa la que la derivación Left, por la izquierda.
Y el 1, es el número de símbolos de entrada para analizar por anticipado.
Método Descendente LL(1)
Ninguna gramática ambigua o recursiva por la izquierda puede ser LL(1).
Método Descendente LL(1)
Buffer de EntradaCadena de entrada a analizar, finaliza con el carácter $
PilaSímbolos gramaticales que se van utilizando
Tabla de Análisis SintácticoMatriz bidimensional que sirve para el análisis
Cadena de SalidaCadena de Salida posterior al análisis
LL(1)
Pasos para el Método LL(1)
1. Escribir adecuadamente la gramática
2. Calcular el First y el Follow
3. Construir la tabla de Análisis Sintáctico
4. Hacer el análisis de sintáctico por medio de la pila y la tabla de análisis
Pasos para el Método LL(1)
1. Escribir adecuadamente la gramática
Para poder utilizar un analizador descendente no recursivo la gramática debe cumplir con:
No debe tener ambigüedad No debe ser recursiva por la izquierda Debe estar factorizada
Pasos para el Método LL(1)
Símbolo First/PrimeroSi x
es terminal First(X) = {x}
Si X → εproducción Añadir ε al First(X)
X →YZW Añadir First (Y) a First (X)
2. Calcular el First / Primero
Símbolo Follow/SiguienteSi X
es símbolo inicial Follow ( X ) = { $ }
Si X → α Y MProducción
1. Follow (Y) = First (M) excepto ε.
2. Si el First(M) contiene ε entonces añadir el Follow(X) a Follow (Y)
Si X → α YProducción Añadir el Follow(X) a Follow(Y)
2. Calcular el Follow / Siguiente
Pasos para el Método LL(1)
Pasos para el Método LL(1)
3. Construir la tabla de Análisis Sintáctico
Símbolos No TerminalesSímbolos No Terminales
Símbolo TerminalSímbolo Terminal
Pasos para el Método LL(1)
3. Construir la tabla de Análisis Sintáctico1. Para cada A → α, ejecute 2 y 3.2. Para cada terminal a del First (α), añádase
A → α en la posición M[A , a].3. Si ε esta en el First (α), añádase A → ε a
M[A , b ] para cada terminal b de Follow(A).
4. Cada entrada vacía hágase ERROR.
Pasos para el Método LL(1)
3. Construir la tabla de Análisis Sintáctico
Se colocan las produccionesque corresponden a los datosobtenidos del cálculo del first.
Se colocan las produccionesque corresponden a los datosobtenidos del cálculo del first.
Pasos para el Método LL(1)
4. Hacer el análisis de sintáctico por medio de la pila y la tabla de análisis
13
Pila Entrada
. .
.
Ejemplo LL(1)
Partiendo de la Gramática:
S → ‘(‘ A ‘)’
A → C B
B → ‘;’ A | ε
C → ‘x’ | S
1. Es una gramática adecuada para el análisis LL(1)
Ejemplo LL(1)
2. Cálculo del First / PrimeroS → ‘(‘ A ‘)’
A → C B
B → ‘;’ A | ε
C → ‘x’ | S
SímboloNo Terminal First
S ( AB ;
C x
Para calcular el first Se usan Los no terminales del lado izquierdo de la producción
Si X es terminal First(X) = {x}
Ejemplo LL(1)
2. Cálculo del First / PrimeroS → ‘(‘ A ‘)’
A → C B
B → ‘;’ A | ε
C → ‘x’ | S
SímboloNo Terminal First
S ( AB ; , ε
C x
Si X → εproducción Añadir ε al First(x)
Para calcular el first Se usan Los no terminales del lado izquierdo de la producción
Ejemplo LL(1)
2. Cálculo del First / PrimeroS → ‘(‘ A ‘)’
A → C B
B → ‘;’ A | ε
C → ‘x’ | S
SímboloNo Terminal First
S ( A x , (B ; , ε
C x , (
X →YZW Añadir First (Y) a First (X)
Para calcular el first Se usan Los no terminales del lado izquierdo de la producción
Ejemplo LL(1)
2. Cálculo del First / PrimeroS → ‘(‘ A ‘)’
A → C B
B → ‘;’ A | ε
C → ‘x’ | S
SímboloNo Terminal First
S ( A x , (B ; , ε
C x , (
Ejemplo LL(1)
2. Cálculo del Follow / SiguienteS → ‘(‘ A ‘)’
A → C B
B → ‘;’ A | ε
C → ‘x’ | S
SímboloNo Terminal Follow
S $ABC
Si Xes símbolo
inicialFollow (X) = { $ }
Para cacular el follow Se usan Los no terminales del lado izquierdo de la producción
Ejemplo LL(1)
2. Cálculo del Follow / SiguienteS → ‘(‘ A ‘)’
A → C B
B → ‘;’ A | ε
C → ‘x’ | S
SímboloNo Terminal Follow
S $A )BC
Para cacular el follow Se usan Los no terminales del lado izquierdo de la producción
Ejemplo LL(1)
2. Cálculo del Follow / SiguienteS → ‘(‘ A ‘)’
A → C B
B → ‘;’ A | ε
C → ‘x’ | S
SímboloNo Terminal Follow
S $A )B )
C
Si X → α YProducción
Añadir el Follow(X) a Follow(Y)
Para cacular el follow Se usan Los no terminales del lado izquierdo de la producción
Ejemplo LL(1)
2. Cálculo del Follow / Siguiente
S → ‘(‘ A ‘)’
A → C B
B → ‘;’ A | ε
C → ‘x’ | S
SímboloNo Terminal Follow
S $A )B )
C ; , )
Se usan Los no terminales del lado derecho de la producción
Si X → α Y MProducción
1.Follow (Y) = First (M) excepto ε.
2. Si el First(M) contiene εentonces añadir elFollow(X) a Follow (Y)
First(B) ; , ε
2. Para cada terminal a del First (α), añádase A → α en la posición M[A , a].
Ejemplo LL(1) Construir la tabla de Análisis Sintáctico
SímboloNo Terminal First
S ( A x , (B ; , εC x , (
; x ( ) $S S ( A )
A A CB A CB
B B ; A
C C x C S
S → ‘(‘ A ‘)’
A → C B
B → ‘;’ A | ε
C → ‘x’ | S
3. Si ε esta en el First (α), añádase A → ε a M[A , b ] para cada terminal b de Follow(A).
Ejemplo LL(1) Construir la tabla de Análisis Sintáctico
SímboloNo Terminal First
B ; , ε
; x ( ) $S S ( A )
A A CB A CB
B B ; A B ε
C C x C S
S → ‘(‘ A ‘)’
A → C B
B → ‘;’ A | ε
C → ‘x’ | S
SímboloNo Terminal Follow
B )
4. Cada entrada vacía hágase ERROR
Ejemplo LL(1) Construir la tabla de Análisis Sintáctico
; x ( ) $S ERROR ERROR S ( A ) ERROR ERROR
A ERROR A CB A CB ERROR ERROR
B B ; A ERROR ERROR B ε ERROR
C ERROR C x C S ERROR ERROR
3. Construir la tabla de Análisis Sintáctico
Ejemplo LL(1)
; x ( ) $S ERROR ERROR S ( A ) ERROR ERROR
A ERROR A CB A CB ERROR ERROR
B B ; A ERROR ERROR B ε ERROR
C ERROR C x C S ERROR ERROR
Pasos para el Método LL(1)
4. Hacer el análisis de sintáctico por medio de la pila y la tabla de análisis
Pila Entrada$ S ( x ; ( x ) ) $
( x ; ( x ) )
Colocar $ y el símbolo inicialColocar $ y el símbolo inicial
Colocar la cadena de entrada y $Colocar la cadena de entrada y $
Pasos para el Método LL(1)
4. Hacer el análisis de sintáctico por medio de la pila y la tabla de análisis
Pila Entrada Acción
$ S ( x ; ( x ) ) $ S ( A )
Se busca el símbolo terminal y el no terminal, remplazándolo por la producción que le corresponda en la tabla.Colocándola de izquierda a derecha
Se busca el símbolo terminal y el no terminal, remplazándolo por la producción que le corresponda en la tabla.Colocándola de izquierda a derecha
(S S → ( A )
Pasos para el Método LL(1)
4. Hacer el análisis de sintáctico por medio de la pila y la tabla de análisis
Pila Entrada Acción
$ S$ ) A (
( x ; ( x ) ) $( x ; ( x ) ) $
S ( A )
Cuando se llega a una coincidencia, se eliminan ambos, y se continua con el análisisCuando se llega a una coincidencia, se eliminan ambos, y se continua con el análisis
Pasos para el Método LL(1)
4. Hacer el análisis de sintáctico por medio de la pila y la tabla de análisis
Pila Entrada Acción
$ S$ ) A (
( x ; ( x ) ) $( x ; ( x ) ) $
S ( A )
Cuando se llega a una coincidencia, se eliminan ambos, y se continua con el análisisCuando se llega a una coincidencia, se eliminan ambos, y se continua con el análisis
Pila Entrada Acción
$ S$ ) A $ ) B C$ ) B x$ ) B$ ) A ;$ ) A$ ) B C $ ) B S$ ) B ) A ($ ) B ) A$ ) B ) B C $ ) B ) B x$ ) B ) B$ ) B )$ ) B $ )$
( x ; ( x ) ) $ x ; ( x ) ) $x ; ( x ) ) $x ; ( x ) ) $
; ( x ) ) $; ( x ) ) $
( x ) ) $( x ) ) $( x ) ) $( x ) ) $
x ) ) $x ) ) $x ) ) $
) ) $) ) $
) $) $
$
S ( A )A C B
C x
B ; A
A C BC S
S ( A )
A C BC x
B ε
B ε
Pila Entrada Acción
$ S$ ) A $ ) B C$ ) B x$ ) B$ ) A ;$ ) A$ ) B C $ ) B S$ ) B ) A ($ ) B ) A$ ) B ) B C $ ) B ) B x$ ) B ) B$ ) B )$ ) B $ )
$
( x ; ( x ) ) $ x ; ( x ) ) $x ; ( x ) ) $x ; ( x ) ) $
; ( x ) ) $; ( x ) ) $
( x ) ) $( x ) ) $( x ) ) $( x ) ) $
x ) ) $x ) ) $x ) ) $
) ) $) ) $
) $) $
$
S ( A )A C B
C x
B ; A
A C BC S
S ( A )
A C BC x
B ε
B ε
ACEPTADA
Se acepta la cadena si se logra eliminar de la pila y la entrada, todos los símbolos.De lo contrariono se acepta la cadena.
Se acepta la cadena si se logra eliminar de la pila y la entrada, todos los símbolos.De lo contrariono se acepta la cadena.
RESUMEN
Pasos para el método LL1
1. Escribir adecuadamente la gramática
2. Calcular el First y el Follow
3. Construir la tabla de Análisis Sintáctico
4. Hacer el análisis de sintáctico por medio de la pila y la tabla de análisis