Clasificaci n de Gram ticas y Manejo de Errores .


27 views
Uploaded on:
Category: Fashion / Beauty
Description
Clasificación de Gramáticas y Manejo de Errores. Resumen. Repaso de parseo LR y algunas clarificaciones Clasificación de gramáticas Lenguajes LR Eliminando Ambiguedad Manejo de errores y recuperación de errores. LR(0) y LR(1), ¿donde está el look ahead?.
Transcripts
Slide 1

Clasificación de Gramáticas y Manejo de Errores

Slide 2

Resumen Repaso de parseo LR y algunas clarificaciones Clasificación de gramáticas Lenguajes LR Eliminando Ambiguedad Manejo de errores y recuperación de errores Oscar Bonilla 2 Universidad Galileo

Slide 3

LR(0) y LR(1), ¿donde está el look ahead? Tanto LR(0) como LR(1) tienen el mismo motor de ejecución , la diferencia está en la construcción de la tabla de parseo Entonces, ¿dónde está el look ahead ? Oscar Bonilla 3 Universidad Galileo

Slide 4

LR(0) y LR(1), ¿donde está el look ahead? Move sn ve el símbolo de entrada , ya ocean lo devour o termina de parsear (acknowledge o mistake)  no es un look ahead Goto sn sólo ve el stack Reduce n LR(0) misma reducción para todos los inputs  no look ahead LR(1) necesitamos el símbolo de entrada  un look ahead Oscar Bonilla 4 Universidad Galileo

Slide 5

LR(0) SL (1) Oscar Bonilla 5 Universidad Galileo

Slide 6

Algunas Definiciones ¿Qué es una gramática XY(k)? (X, Y  {L, R}) Una gramática G es una gramática XY(k) si y sólo si podemos crear una tabla de parseo XY(k) sin ningún conflicto move/lessen o diminish/decrease Oscar Bonilla 6 Universidad Galileo

Slide 7

Construcción de un Parse Engine LR(0) Agregamos la producción particular S\'  S $ Encontramos los ítems de la CFG Creamos el DFA Comenzamos con el ítem S\'  • S $ Usando las funciones conclusion y goto Construimos la tabla de parseo LR(0) Parser Engine Oscar Bonilla 7 Universidad Galileo

Slide 8

Construcción de un parse motor SLR(1) Agregamos la producción particular S\'  S $ Calcular el conjunto take after para todos los no - terminal e s Encontrar los ítems LR(0) de la CFG Crear el DFA Comenzamos con el ítem S\'  • S $ Usando las funciones conclusion y goto Construir la tabla de parseo Usando el DFA y la información del conjunto take after SLR Parser Engine Oscar Bonilla 8 Universidad Galileo

Slide 9

Construcción de un parse motor LR(1) Agregamos la producción particular S\'  S $ Encontramos los ítems LR(1) de la CFG Creamos el DFA Comenzamos con el ítem [ S\'  • S $, ?] Usamos las funciones conclusion y goto Construimos la tabla de parseo LR(1) Parser Engine Oscar Bonilla 9 Universidad Galileo

Slide 10

Resumen Repaso de parseo LR y algunas clarificaciones Clasificación de gramáticas Lenguajes LR Eliminando Ambiguedad Manejo de errores y recuperación de errores Oscar Bonilla 10 Universidad Galileo

Slide 11

Clasificación de Gramáticas Context free Oscar Bonilla 11 Universidad Galileo

Slide 12

Clasificación de Gramáticas Context free G 0 normal Oscar Bonilla 12 Universidad Galileo

Slide 13

Gramáticas Regulares Una gramática que puede ser expresada usando una expresión consistent es una gramática standard Lenguaje Ejemplo : Cero o más paréntesis abiertos seguidos de cero o más paréntesis cerrados G 0 = { ( a ) b | a, b >= 0 } Gram ática S  X Y $ X  ( X |  Y  ) Y |  Oscar Bonilla 13 Universidad Galileo

Slide 14

Clasificación de Gramáticas Context free LR(0) G 0 G 1 customary Oscar Bonilla 14 Universidad Galileo

Slide 15

Gramáticas LR(0) Una gramática que puede crear una tabla de parseo LR(0) sin ningún conflicto move/lessen o decrease/diminish Lenguaje Ejemplo : Uno o más paréntesis abiertos seguidos de un número igual de paréntesis cerrados G 1 = { ( n ) n | n > 0 } La gramática <S>  <X> $ <X>  ( <X> ) | ( ) Oscar Bonilla 15 Universidad Galileo

Slide 16

Clasificación de Gramáticas Context free SLR(1) LR(0) G 0 G 1 G 2 general Oscar Bonilla 16 Universidad Galileo

Slide 17

Gramáticas SLR(1) Una gramática que puede crear una tabla de parseo SLR(1) sin ningún conflicto move/diminish o diminish/decrease Lenguaje Ejemplo : Cero o más paréntesis abiertos seguidos de un número igual de paréntesis cerrados G 2 = { ( n ) n | n >= 0 } La gramática <S>  <X> $ <X>  ( <X> ) |  Oscar Bonilla 17 Universidad Galileo

Slide 18

Clasificación de Gramáticas Context free LALR(1) SLR(1) LR(0) G 0 G 1 G 2 G 3 customary Oscar Bonilla 18 Universidad Galileo

Slide 19

Gramáticas LALR(1) Una gramática que puede crear una tabla de parseo LALR(1) sin ningún conflicto move/lessen o decrease/diminish Lenguaje Ejemplo : ??? G 3 = { ??? } La gramática Oscar Bonilla 19 Universidad Galileo

Slide 20

Clasificación de Gramáticas Context free LR(1) LALR(1) SLR(1) LR(0) G 0 G 1 G 2 G 3 G 4 general Oscar Bonilla 20 Universidad Galileo

Slide 21

Gramáticas LR(1) Una gramática que puede crear una tabla de parseo LR(1) sin ningún conflicto move/lessen o decrease/diminish Lenguaje Ejemplo : Cero o más paréntesis abiertos seguidos de un número igual de paréntesis cerrados o un solo paréntesis abierto G 4 = { ( n ) n | n >= 0 }  { ( } La gramática <S>  <X> $ <X>  ( | <Y> <Y>  ( <Y> ) |  Oscar Bonilla 21 Universidad Galileo

Slide 22

Clasificación de Gramáticas Context free LR(k) LR(1) LALR(1) SLR(1) LR(0) G 0 G 1 G 2 G 3 G 4 G 5 normal Oscar Bonilla 22 Universidad Galileo

Slide 23

Gramáticas LR(k) Una gramática que puede crear una tabla de parseo LR(k) sin ningún conflicto move/diminish o diminish/diminish Lenguaje Ejemplo : Cero o más paréntesis abiertos seguidos de un número igual de paréntesis cerrados o un número igual de corchetes cerrados G 5 = { ( n ) n | n >= 0 }  { ( n ] n | n >= 0 } La gramática <S>  <X> $ <X>  <Y> | <Z> <Y>  ( <Y> ) |  <Z>  ( <Z> ] |  Oscar Bonilla 23 Universidad Galileo

Slide 24

Clasificación de Gramáticas Context free unambiguous LR(k) LR(1) LALR(1) SLR(1) LR(0) G 0 G 1 G 2 G 3 G 4 G 5 G 6 customary Oscar Bonilla 24 Universidad Galileo

Slide 25

Gramáticas no Ambiguas Una gramática es no ambigua sí y sólo sí tiene una secuencia de derivación derecha (furthest right) única (parse tree) Ejemplo : G 6 = { [ ( n ) n | n >= 0 }  { ] ( n ) 2n | n >= 0 } La gramática <S>  <X> $ <X>  [ <Y> | ] <Z> <Y>  ( <Y> ) |  <Z>  ( <Z> )) |  Oscar Bonilla 25 Universidad Galileo

Slide 26

Clasificación de Gramáticas Context free unambiguous LR(k) LR(1) LALR(1) SLR(1) LR(0) G 0 G 1 G 2 G 3 G 4 G 5 G 6 G 7 standard Oscar Bonilla 26 Universidad Galileo

Slide 27

Gramáticas Ambiguas Una gramática es ambigua sí y sólo sí tiene más de una secuencia de derivación por la derecha Ejemplo : G 7 = { ( i ) j ( k | i = j or j = k } La gramática <S>  <X> $ <X>  <P> <Q> | <R> <S> <P>  ( <P> ) |  <Q>  ( <Q> |  <R>  ( <R> |  <S>  ) <S> ( |  Oscar Bonilla 27 Universidad Galileo

Slide 28

Clasificación de Gramáticas Context free unambiguous LR(k) LR(1) LALR(1) SLR(1) LR(0) G 0 G 1 G 2 G 3 G 4 G 5 G 6 G 7 consistent Oscar Bonilla 28 Universidad Galileo

Slide 29

Clasificación de Gramáticas Context free unambiguous LR(k) LR(1) LALR(1) SLR(1) LR(0) G 0 G 1 G 2 G 3 G 4 G 5 G 6 G 7 customary LL(0) Oscar Bonilla 29 Universidad Galileo

Slide 30

Clasificación de Gramáticas Context free unambiguous LR(k) LR(1) LALR(1) SLR(1) LR(0) G 0 G 1 G 2 G 3 G 4 G 5 G 6 G 7 general LL(0) LL(1) Oscar Bonilla 30 Universidad Galileo

Slide 31

Pregunta ¿Qué feed acerca del lenguaje? G 8 = { ( i ) j ( k | i = j = k } Oscar Bonilla 31 Universidad Galileo

Slide 32

Resumen Repaso de parseo LR y algunas clarificaciones Clasificación de gramáticas Lenguajes LR Eliminando Ambiguedad Manejo de errores y recuperación de errores Oscar Bonilla 32 Universidad Galileo

Slide 33

Lenguajes L R Un lenguaje libre de contexto es un lenguaje LR sí y sólo sí puede ser generado por una gramática LR(k) para algún k Oscar Bonilla 33 Universidad Galileo

Slide 34

Lenguajes LR El conjunto de lenguajes LR es independiente de la distancia de lookahead k Dada cualquier gramática LR(k) G k , existe una gramática LR(0) G 0 tal que L(G k ) = L(G 0 ) Para todos los lenguajes que vimos con gramáticas SLR(1), LALR(1) y LR(1), ¡¡¡podríamos haber encontrado una gramática LR(0)!!! Oscar Bonilla 34 Universidad Galileo

Slide 35

Ejemplo Lenguaje Cero o más paréntesis abiertos seguidos de un número igual de paréntesis cerrados o un solo paréntesis abierto Gramática LR(1) <S>  <X> $ <X>  <Y> <X>  ( <Y>  ( <Y> ) <Y>   ¿Hay alguna gramática LR(0) para este lenguaje ? Oscar Bonilla 35 Universidad Galileo

Slide 36

( s0 s1 s2 <S>  • <X> $ <X>  • Y <X>  • ( <Y>  • ( <Y> ) <Y>  • <X>  ( • <Y>  ( • <Y> ) <Y>  • ( <Y> ) <Y>  • <Y>  ( • <Y> ) <Y>  • ( <Y> ) <Y>  • s3 s4 s6 s5 <Y>  ( <Y> • ) <Y>  ( <Y> ) • <S>  <X> • $ <X>  <Y> • 26 Ejemplo Expandido DFA <S>  <X> $ <X>  <Y > <X>  ( < Y >  ( <Y> ) <Y >   ( Y X ) Oscar Bonilla 36 Universidad Galileo

Slide 37

( s0 s1 s2 <S>  • <X> $ <X>  • Y <X>  • ( <Y>  • (

Recommended
View more...