10_Clasificacion_de_Gramaticas

Compiladores

Clasificación de Gramáticas y Manejo de Errores

Oscar Bonilla 2 Universidad Galileo

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?

• Tanto LR(0) como LR(1) tienen el mismo engine de ejecución, la diferencia está en la construcción de la tabla de parseo– Entonces, ¿dónde está el look ahead?


LR(0) y LR(1), ¿donde está el look ahead?

• Shift sn– ve el símbolo de entrada,

– ya sea lo consume o termina de parsear (accept o error) 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


ACTION GotoState ( ) $ X Ys0 shift to s1 reduce (5) reduce (5) goto s5 goto s6s1 shift to s2 reduce (5) reduce (5) goto s3s2 shift to s2 reduce (5) reduce (5) goto s3s3 error shift to s4 error s4 error reduce (4) reduce (4) s5 error error accept s6 error error reduce (2)

SL

(1)

LR

(0)

ACTION GotoState ( ) $ Xs0 shift to s2 error error goto s1s1 error error accept s2 shift to s2 shift to s5 error goto s3s3 error shift to s4 error s4 reduce (2) reduce (2) reduce (2) s5 reduce (3) reduce (3) reduce (3)


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 shift/reduce o reduce/reduce


Construcción de un Parse Engine LR(0)

• Agregamos la producción especial S’ S $

• Encontramos los ítems de la CFG

• Creamos el DFA– Comenzamos con el ítem S’ • S $

– Usando las funciones closure y goto

• Construimos la tabla de parseo

LR(0)ParserEngine


Construcción de un parse engine SLR(1)

• Agregamos la producción especial S’ S $• Calcular el conjunto follow para todos los no-

terminales• Encontrar los ítems LR(0) de la CFG• Crear el DFA

– Comenzamos con el ítem S’ • S $

– Usando las funciones closure y goto

• Construir la tabla de parseo– Usando el DFA y la información del conjunto

follow

SLRParserEngine


Construcción de un parse engine LR(1)

• Agregamos la producción especial S’ S $

• Encontramos los ítems LR(1) de la CFG

• Creamos el DFA– Comenzamos con el ítem [S’ • S $, ?]– Usamos las funciones closure y goto

• Construimos la tabla de parseo

LR(1)ParserEngine


Resumen



• Lenguajes LR




Clasificación de Gramáticas

Context free



regular

Context free

G0


Gramáticas Regulares• Una gramática que puede ser expresada usando

una expresión regular es una gramática regular• Lenguaje Ejemplo:

– Cero o más paréntesis abiertos seguidos de cero o más paréntesis cerrados

• G0 = { (a )b

| a, b >= 0 }• Gramática

S X Y $X ( X | Y ) Y |



regular

LR(0)

Context free

G0 G1


Gramáticas LR(0)

• Una gramática que puede crear una tabla de parseo LR(0) sin ningún conflicto shift/reduce o reduce/reduce

• Lenguaje Ejemplo:– Uno o más paréntesis abiertos seguidos de un número

igual de paréntesis cerrados

• G1 = { (n )n

| n > 0 }• La gramática

<S> <X> $<X> ( <X> ) | ( )



regular

LR(0)SLR(1)

Context free

G0 G1 G2


Gramáticas SLR(1)

• Una gramática que puede crear una tabla de parseo SLR(1) sin ningún conflicto shift/reduce o reduce/reduce

• Lenguaje Ejemplo:– Cero o más paréntesis abiertos seguidos de un número

igual de paréntesis cerrados

• G2 = { (n )n

| n >= 0 }• La gramática

<S> <X> $<X> ( <X> ) |



regular

LR(0)SLR(1)

LALR(1)

Context free

G0 G1 G2 G3


Gramáticas LALR(1)

• Una gramática que puede crear una tabla de parseo LALR(1) sin ningún conflicto shift/reduce o reduce/reduce

• Lenguaje Ejemplo:– ???

• G3 = { ??? }

• La gramática



regular

LR(0)SLR(1)

LALR(1)LR(1)

Context free

G0 G1 G2 G3 G4


Gramáticas LR(1)

• Una gramática que puede crear una tabla de parseo LR(1) sin ningún conflicto shift/reduce o reduce/reduce

• 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

• G4 = { (n )n

| n >= 0 } { ( }

• La gramática<S> <X> $

<X> ( | <Y>

<Y> ( <Y> ) |



regular

LR(0)SLR(1)

LALR(1)LR(1)LR(k)

Context free

G0 G1 G2 G3 G4 G5


Gramáticas LR(k)• Una gramática que puede crear una tabla de parseo LR(k)

sin ningún conflicto shift/reduce o reduce/reduce• 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

• G5 = { (n )n

| n >= 0 } { (n ]n

| n >= 0 }

• La gramática<S> <X> $

<X> <Y> | <Z>

<Y> ( <Y> ) | <Z> ( <Z> ] |



regular

LR(0)SLR(1)

LALR(1)LR(1)LR(k)

unambiguousContext free

G0 G1 G2 G3 G4 G5 G6


Gramáticas no Ambiguas• Una gramática es no ambigua sí y sólo sí tiene una

secuencia de derivación derecha (rightmost) única (parse tree)

• Ejemplo:

• G6 = { [(n )n

| n >= 0 } { ](n )2n

| n >= 0 }

• La gramática<S> <X> $<X> [ <Y> | ] <Z><Y> ( <Y> ) | <Z> ( <Z> ))|



regular

LR(0)SLR(1)

LALR(1)LR(1)LR(k)


G0 G1 G2 G3 G4 G5 G6 G7


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:

• G7 = { (i )j

(k | i = j or j = k }

• La gramática<S> <X> $<X> <Q> | <R> <S> ( ) | <Q> ( <Q> | <R> ( <R> | <S> ) <S> ( |


G0


regular

LR(0)SLR(1)

LALR(1)LR(1)LR(k)


G1 G2 G3 G4 G5 G6 G7


G0


regular

LR(0)SLR(1)

LALR(1)LR(1)LR(k)


G1 G2 G3 G4 G5 G6 G7

LL(0)


G0


regular

LR(0)SLR(1)

LALR(1)LR(1)LR(k)


G1 G2 G3 G4 G5 G6 G7

LL(0)

LL(1)


Pregunta• ¿Qué hay acerca del lenguaje?

• G8 = { (i )j

(k | i = j = k }


Resumen



• Lenguajes LR




Lenguajes LR

• 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


Lenguajes LR

• El conjunto de lenguajes LR es independiente de la distancia de lookahead k

• Dada cualquier gramática LR(k) Gk, existe una gramática LR(0) G0 tal que L(Gk) = L(G0)

• 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)!!!


EjemploLenguaje

Cero o más paréntesis abiertos seguidos de un número igual de paréntesis cerradoso 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?


<S> • <X> $<X> • Y<X> • ( <Y> • ( <Y> )<Y> •

s0

Y

<S> <X> • $s5

(Y

s4<Y> ( <Y> ) •

)<Y> ( <Y> • )s3

<X> ( •<Y> ( • <Y> ) <Y> • ( <Y> )<Y> •

s1

(<Y> ( • <Y> ) <Y> • ( <Y> )<Y> •

s2(

<X> <Y> •s6

X

Y

Ejemplo Expandido DFA

<S> <X> $<X> <Y>

<X> ( <Y> ( <Y> )

<Y>

26


<S> • <X> $<X> • Y<X> • ( <Y> • ( <Y> )<Y> •

s0

Y

<S> <X> • $s5

(Y

s4<Y> ( <Y> ) •

)<Y> ( <Y> • )s3

<X> ( •<Y> ( • <Y> ) <Y> • ( <Y> )<Y> •

s1

(<Y> ( • <Y> ) <Y> • ( <Y> )<Y> •

s2(

<X> <Y> •s6

X

Y

Ejemplo Expandido DFA

<S> <X> $<X> <Y>

<X> ( <Y> ( <Y> )

<Y>

26


LenguajeCero o más paréntesis abiertos seguidos de un número igual de paréntesis cerradoso un solo paréntesis abierto

Gramática LR(1)<S> <X> $ <X> <Y> <X> ( <Y> ( <Y> ) <Y>

Ejemplo

Gramática LR(0)<S> <X> $

<X> <Y><X> ( <Z><X> <Z> <Y> ( <Y> )<Y> <Z> <Z>


<S> • <X> $<X> • <Y><X> • ( <Z><X> • <Z><Y> • ( <Y> )<Y> • <Z>

s0

<S> <X> • $s5

( Y

s4<Y> ( <Y> ) •

)<Y> ( <Y> • )s3

<Y> ( • <Y> )<X> ( • <Z><Y> • ( <Y> )<Y> • <Z>

s1

(<Y> ( • <Y> )<Y> • ( <Y> )<Y> • <Z>

s2

(

X

Y

DFA del Ejemplo<S> <X> $ <X> <Y> <X> ( <Z><X> <Z> <Y> ( <Y> ) <Y> <Z><Z>

Y

<X> <Y> •s6

<Z> •s7

ZZ

Z


<S> • <X> $<X> • <Y><X> • ( <Z><X> • <Z><Y> • ( <Y> )<Y> • <Z>

s0

<S> <X> • $s5

( Y

s4<Y> ( <Y> ) •

)<Y> ( <Y> • )s3

<Y> ( • <Y> )<X> ( • <Z><Y> • ( <Y> )<Y> • <Z>

s1

(<Y> ( • <Y> )<Y> • ( <Y> )<Y> • <Z>

s2

(

X

Y

DFA del Ejemplo<S> <X> $ <X> <Y> <X> ( <Z><X> <Z> <Y> ( <Y> ) <Y> <Z><Z>

Y

<X> <Y> •s6

<Z> •s7

ZZ

Z


Lenguajes LR

• El conjunto de lenguajes LR es independiente de la distancia de lookahead k

• Dada cualquier gramática LR(k) Gk, existe una gramática LR(0) G0 tal que L(Gk) = L(G0)

• 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)!!!

• ¡¡¡Pero esto puede ser muy difícil!!!


Resumen



• Lenguajes LR




Lenguajes Ambiguos

• Un lenguaje libre de contexto es inherentemente ambiguo si toda gramática que genera el lenguaje es ambigua

• Sin embargo, la mayoría de gramáticas ambiguas encontradas en la práctica son para lenguajes no ambiguos– Queremos hacerlas no ambiguas


Gramáticas Ambiguas

• Si tenemos una gramática ambigua para un lenguaje no ambiguo, podemos:– Escribir una gramática no ambigua– Usar precedencia y asociatividad para resolver los

conflictos en las acciones del parser


Ejemplo

<E> <E> + <E> | <E> * <E> | ( <E> ) | id


Ejemplo

<E> <E> + <E> | <E> * <E> | ( <E> ) | id

• Escribiendo una gramática no ambigua


Ejemplo

<E> <E> + <E> | <E> * <E> | ( <E> ) | id

• Escribiendo una gramática no ambigua<E> <E> + <T> | <T>

<T> <T> * <F> | <F>

<F> ( <E> ) | id


<S> <E> $

<E> <E> + <E> | <E> * <E> | ( <E> ) | id


<S> <E> $

<E> <E> + <E> | <E> * <E> | ( <E> ) | id

<S> • <E><E> • <E> + <E><E> • <E> * <E><E> • ( <E> )<E> • id

s0

<S> <E> • <E> <E> • + <E><E> <E> • * <E>

s1

<S> ( • <E> )<E> • <E> + <E><E> • <E> * <E><E> • ( <E> )<E> • id

s2

<E> id •

s3

<S> <E> + • <E><E> • <E> + <E><E> • <E> * <E><E> • ( <E> )<E> • id

s4<S> <E> * • <E><E> • <E> + <E><E> • <E> * <E><E> • ( <E> )<E> • id

s5

<E> <E> • + <E><E> <E> • * <E><E> ( <E> •)

s6

<S> <E> * <E> •<E> <E> • + <E><E> <E> • * <E>

s8

<E> <E> + <E> •<E> <E> • + <E><E> <E> • * <E>

s7

<E> ( <E> ) •

s9


s0 $

*id + id id


s1s4s7

<E>+

<E>

s0 $

*id + id id


s1s4s7

<E>+

<E>

s0 $

*id + id id

<E> <E> + <E> •<E> <E> • + <E><E> <E> • * <E>

s7

Shift or reduce


Usando Precedencia y Asociatividad

• Construimos el DFA y construimos la tabla de parseo

• Cuando hay un conflicto usamos la información de precedencia y asociatividad


Otro Ejemplo

<stmt> if <expr> then <stmt> else <stmt><stmt> if <expr> then <stmt> <stmt> other


Otro Ejemplo


if ... then if ... then … else if ... then … else …


Otro Ejemplo




Otro Ejemplo




Otro Ejemplo




Otro Ejemplo



Asociatividad izquierda, ¡esto es lo que queremos!


Otro Ejemplo


<S> <E> $<E> i <E> o <E> <E> i <E><E> <A>


<S> <E> $<E> i <E> o <E> | i <E> | <A>

<S> • <E><E> • i <E> o <E><E> • <E><E> • <A>

s0

<E> i • <E> o <E><E> i • <E><E> • i <E> o <E><E> • i <E><E> • <A>

s1

<S> <E> •

s2

<S> <A> •

s3

<E> i <E> • o <E><E> i <E> •

s4 <E> i <E> o • <E><E> • i <E> o <E><E> • i <E><E> • <A>

s5

<E> i <E> o <E> •

s6

E

A

i i

A

i

A

E

o

E


<S> <E> $<E> i <E> o <E> | i <E> | <A>

<S> • <E><E> • i <E> o <E><E> • <E><E> • <A>

s0

<E> i • <E> o <E><E> i • <E><E> • i <E> o <E><E> • i <E><E> • <A>

s1

<S> <E> •

s2

<S> <A> •

s3

<E> i <E> • o <E><E> i <E> •

s4 <E> i <E> o • <E><E> • i <E> o <E><E> • i <E><E> • <A>

s5

<E> i <E> o <E> •

s6

E

A

i i

A

i

A

E

o

E


<S> <E> $<E> i <E> o <E> | i <E> | <A>

ACTION GotoState i o $ E As0 shift to s1 error error goto s2 goto s3s1 shift to s2 error error goto s4 goto s3s2 error error accept s3 reduce reduce reduce s4 reduce shift to s5/reducereduce s5 error shift to s6 error goto s3s6 reduce reduce reduce


<S> <E> $<E> i <E> o <E> | i <E> | <A>

ACTION GotoState i o $ E As0 shift to s1 error error goto s2 goto s3s1 shift to s2 error error goto s4 goto s3s2 error error accept s3 reduce reduce reduce s4 reduce shift to s5/reducereduce s5 error shift to s6 error goto s6 goto s3s6 reduce reduce reduce

Follow(<E>) = { i, o, $ }


s0 $

oi i a a



s1 is0 $

oi i a a



s1 is1 is0 $

oi i a a



s3 As1 is1 is0 $

oi i a a



Es1 is1 is0 $

oi i a a



s4 Es1 is1 is0 $

oi i a a



s4 Es1 is1 is0 $

oi i a a



s4 Es1 is1 is0 $

oi i a a

Como asocia por la izquierda, hacemos el shift



s5 os4 Es1 is1 is0 $

oi i a a



s3 As5 os4 Es1 is1 is0 $

oi i a a



Es5 os4 Es1 is1 is0 $

oi i a a



s6 Es5 os4 Es1 is1 is0 $

oi i a a



Es1 is0 $

oi i a a



s4 Es1 is0 $

oi i a a



Es0 $

oi i a a



s3 Es0 $

oi i a a



Resumen



• Lenguajes LR




Manejo de Errores

• ¡¡Los programas no siempre son correctos!!

• El compilador tiene que:– Reportar clara y exactamente la presencia de errores– Recuperarse de cada error lo suficientemete rápido

para poder detectar errores subsiguientes– Tratar de evitar mensajes falsos de error


Tipos de Errores

• Léxicos

• Sintácticos

• Semánticos

• Lógicos


Errores Léxicos

• Un error que produce un token erroneo

• Errores léxicos posibles– Un identificador, palabra reservada u operador mal

escrito (typo)


Errores Sintácticos

• Un programa que no satisface la CFG del lenguaje

• Ejemplos– Expresión aritmética con paréntesis no balanceados– Un punto y coma faltante


Errores Semánticos

• Un error que necesita información sensitiva al contexto para ser identificado

• Ejemplos– Un operador aplicado a un tipo incompatible de

operando– Accesar una variable no declarada


Errores Lógicos

• Errores en el modelo de ejecución

• Ejemplos– Recursión infinita– Accesar un arreglo fuera de los límites– Dereferenciar un null pointer


Tipos de recuperación de errores de sintáxis

• Panic mode recovery

• Parse level recovery

• Producciones de error

• Corrección global


Panic mode recovery

• Al descubrir un error – pop cero o más estados/símbolos del stack– descartar cero o más símbolos de entrada– hasta que lleguemos a un punto donde podemos

continuar parseando

• Usamos no-terminales definidos para el panic– Ejemplo: cerrar llave, punto y coma


Panic mode recovery

• En error – pop del stack hasta que lleguemos a un estado X de

donde se pueda hacer un goto para alguno de los no-terminales de pánico

• Se termina el parseo si no se encuentra ninguno

– Descartamos tokens del buffer de entrada hasta que encontremos un token sincronizador

• Un token que pertenece a follow(A) del no-terminal de pánico A que encontramos en el paso anterior

– Push de A y del estado goto(S,A) en los stacks y seguimos parseando


s0 $

Ejemplo de panic mode error recoveryGramática:

<S> <E> $<E> <X> ; <E> | <X> <X> id | <X> = <X>


s0 $

idid id ; =

Ejemplo de panic mode error recovery

idid ; id

Gramática :<S> <E> $<E> <X> ; <E> | <X> <X> id | <X> = <X>


s3 ids0 $

id id


id ; id; = idid



s6 <X>s0 $

id id


id ; id; = idid



s6 <X>s4 ;

s0 $

id id


id ; id; = idid



s2 <Y>s0 $

id id


id ; id; = idid



s3 ids2 <E>s0 $

id id


id ; id; = idid



s6 <X>s2 <E>s0 $

id id


id ; id; = idid



s3 ids6 <X>s2 <E>s0 $

id id


id ; id; = idid



s6 <X>s6 <X>s2 <E>s0 $

id id


id ; id; = idid



s6 <X>s6 <X>s2 <E>s0 $

id id


id ;

PANIC

id; = idid



s6 <X>s6 <X>s2 <E>s0 $

id id


id ;

PANICno-terminales de pánico = { <E> ... }follow(<E>) = { ; }

id; = idid



s2 <E>s0 $

id id


id ;

PANIC

id; = idid


s6 <X>s6 <X>

no-terminales de pánico = { <E> ... }follow(<E>) = { ; }


s2 <E>s0 $

id id


id ;

PANIC

id; = idid




s2 <E>s0 $

id id


id ;

PANIC

id; = idid




s2 <E>s0 $

id id


id ;

PANIC

id; = idid




s2 <E>s0 $

id id


id ; id; = idid



s3 ids2 <E>s0 $

id id


id ; id; = idid



Parse Level Error Recovery

• En error – invocamos una rutina especial para cambiar el

prefijo de los tokens de entrada que quedan– y continuamos el parseo

• Ejemplo– Reemplazar una coma por un punto y coma


Ejemplo de parser level error recovery

• Action Table

s0 $

(( ( )


$


s3 Xs2 (


• Action Table

s0 $

(( ( )


$


s3 Xs2 (


• Action Table

s0 $

(( ( )


$


s3 Xs2 (


• Action Table

s0 $

(( ( )


$

Invocamos rutina de recuperación de error


s3 Xs2 (


• Action Table

s0 $

)( ( )


$

Invocamos rutina de recuperación de error


s3 Xs2 (


• Action Table

s0 $

)( ( )


$


s4 )s3 Xs2 (


• Action Table

s0 $

)( ( )


$


Producciones de Error

• Agregamos producciones especiales de la forma A error para manejar errores.– error se trata como un símbolo terminal especial

• En error – Insertamos el terminal error como el primer token de

entrada– Pop del stack hasta que lleguemos a un estado E en el que se

pueda hacer un goto para el terminal error– El parser hace shift del terminal error, el estado actual es es

F = goto(E, error)– Descartamos los tokens del buffer de entrada hasta que

encontremos un token para el que se pueda ejecutar una acción de parseo legal a partir del estado F


Ejemplo de Producciones de Error

• Gramática<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X>


Ejemplo de Producciones de Error

• Gramática<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error


Ejemplo de Producciones de Error• Gramática

<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error

s0 $



<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error

s0 $

idid id ; = idid ; id


s0 $

idid id ; = idid ; id


<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error


s3 ids0 $

id idid ; id; = idid


<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error


s6 <X>s0 $



<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error


s6 <X>s4 ;

s0 $



<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error


s2 <Y>s0 $



<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error


s3 ids2 <E>s0 $



<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error


s6 <X>s2 <E>s0 $



<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error


s6 <X>s6 <X>s2 <E>s0 $



<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error


s6 <X>s6 <X>s2 <E>s0 $

id idid ;

Error

id; = idid


<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error


s6 <X>s6 <X>s2 <E>s0 $

id idid ;

Error

id; = idid


<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error

error


s2 <E>s0 $

id idid ;

Error

id; = idid


<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error

error

s6 <X>s6 <X>


s2 <E>s0 $

id idid ;

Error

id; = idid


<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error

error


s5 errors2 <E>s0 $

id idid ;

Error

id; = idid


<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error

error


s5 errors2 <E>s0 $

id idid ;

Error

id; = idid


<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error

error


s5 errors2 <E>s0 $

id idid ;

Error

id; = idid


<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error

error


s5 errors2 <E>s0 $



<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error

error


s2 <E>s0 $



<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error

error


s3 ids2 <E>s0 $



<S> <E> $

<E> <X> ; <E> | <X>

<X> id | <X> = <X> | error

error


Corrección Global

• Tratamos de anticipar las acciones del programador

• Hacemos el programa legal elijiendo la mínima cantidad de cambios

• Muchos problemas– Costoso– Los cambios pueden crear un programa

semánticamente correcto, ¡¡¡pero no el que el programador quería escribir!!!


Lecturas

• El Tigre– Chapter 5

• La Ballena– 3.1, 3.2, 3.3, 3.4

• El Dragón– Chapter 6

Documents

10_Clasificacion_de_Gramaticas