Ambigüedad_Detección_y_Eliminación
Transcript of Ambigüedad_Detección_y_Eliminación
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
1/23
Ambigedad. Deteccin yeliminacin
Enzo Andreetto
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
2/23
rboles de derivacin
En clases anteriores se vieron a la inferencia recursiva y alas derivaciones por izquierda y por derecha como
procedimientos para demostrar que una palabra perteneceal lenguaje generado por una determinada gramtica. !nconcepto relacionado es el de rbol de derivacin.
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
3/23
"ea # $ %&' (' )' "*. +os rboles de derivacin para # son
aqu,llos que cumplen con las siguientes condiciones-
* /ada nodo interior est etiquetado con una variable de&.
0* /ada hoja est etiquetada bien con una variable' uns1mbolo terminal o . "in embargo' si la hoja estetiquetada con ' entonces tiene que ser el 2nico hijode su padre.
3* "i un nodo interior est etiquetado comoAy sus hijosestn etiquetados como -X'X0' ...'X4respectivamente' comenzando por la izquierda'entonces A XX0...X4es una produccin de P.
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
4/23
Ejemplo- "ea la gramtica # $ %&' (' )' "* definida como
& $ 5A' 67( $ 58' ' 97" $ 5A7) $ 5 A 8A' A 6' 6 9 7
+a palabra 889
+%#* y su rbol es-A
8 A
8 A
6
9
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
5/23
+a e:istencia de un rbol de derivacin para la palabra889 indica que pertenece al lenguaje generado de #
pero' adems' determina su estructura sintcticaindicando la precedencia de los s1mbolos terminales."i' por ejemplo' se escribiera una gramtica quegenerase e:presiones de n2meros enteros con la
suma y el producto' la palabra ; 3 < 0 podr1a tener'por ejemplo' el siguiente rbol-
"
A ; 6
A < A
3 0
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
6/23
)ero no el rbol-"
6 < A
; 3 0
ya que el producto tiene mayor precedencia que la suma yel resultado deber1a ser =' no >.
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
7/23
Dada una gramtica # $ %&' (' )' "*' las siguientesafirmaciones son equivalentes-
? +a inferencia recursiva determina que la cadena terminalwpertenece al lenguaje de la variableA.?A< w.?A
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
8/23
Ambigedad
!na gramtica es ambigua cuando e:isten dos rboles dederivacin diferentes para al menos una palabra. Esteproblema hace que la gramtica no determine la
estructura sintctica de los elementos de la palabra.Ejemplo- +a gramtica con las reglas de produccin" " ; " y " " < " tiene dos rboles para la palabra" ; " < ".
" " " ; " " < "
" < " " ; "
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
9/23
Bo e:iste un algoritmo que permita decidir si unagramtica libre de conte:to es ambigua. "in embargo' el
siguiente hecho sirve para determinar si hay ambigedad-En una gramtica no ambigua las derivaciones no sonnecesariamente 2nicas' pero las derivaciones ms a laizquierda y ms a la derecha s1 lo sern.
(eorema- )ara cada gramtica G$ %V' T' P' S* y cadenawen T
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
10/23
Bo hay un procedimiento que permita eliminar laambigedad de una gramtica' adems de que e:isten
ciertos lenguajes %llamados inherentemente ambiguos*para los que no e:isten gramticas no ambiguas. "inembargo' s1 se pueden identificar ciertas causas deambigedad y criterios para eliminarla.
En primer lugar' se deben evitar reglas de produccinredundantes que permitan derivar la misma palabra. !nejemplo trivial ser1a el de una gramtica ambigua para ellenguaje que tiene slo a la cadena vac1a . )or ejemplo-
" A 6' A , .C tambi,n " A "A' A .!na gramtica no ambigua para este lenguaje tendr1a slola regla " .
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
11/23
Ctro caso a considerar es la concatenacin de n
terminales. )or ejemplo' el lenguaje que consiste en laspalabras de una o ms a. "i se considera la palabra aaa'@,sta se interpreta como la e:presin aa seguida por a' ocomo a seguida por la e:presin aa !na gramtica no
ambigua deber1a seguir uno de estos criterios' pero no losdos a la vez. +a gramtica con las reglas " a" "a agenera el lenguaje en cuestin' pero es ambigua. Encambio' " "a a no lo es.
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
12/23
!na causa t1pica de ambigedad ocurre cuando la
gramtica no considera cmo se asocian ciertassecuencias de caracteres. Es fcil ver esto cuando ciertoss1mbolos se interpretan como operadores. )or ejemplo'consid,rese el lenguaje con n2meros enteros de un d1gito
y sumas de enteros de un d1gito. +a siguiente es unagramtica ambigua para el mismo-" " ; A A ; " A
A 8
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
13/23
+a palabra ; 0 ; 3 tiene los siguientes rboles- " "
" ; A A ; "
" ; A 3 A ; "
A 0 0 A
3
Dado que la adicin cumple con la ley asociativa' ambase:presiones arrojan el mismo resultado. "in embargo'difieren desde un punto de vista sintctico. El rbol de laizquierda equivale a % ; 0* ; 3' mientras que el de la
derecha es ; %0 ; 3*.
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
14/23
)ara eliminar la ambigedad' se debe lograr unagramtica que opte por el primer o por el segundo rbol.Es decir' que asocie al operador ; por izquierda o porderecha. !na vez ms' el problema est en laredundancia dada por las reglas " ; A y A ; ". "e debe
optar por una de las dos y' si se conserva " ; A la sumase analizar sintcticamente como asociativa porizquierdaF en cambio' si se emplea A ; "' la sumaasociar por derecha.
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
15/23
/onsid,rese ahora la gramtica dada por las siguientes
reglas-" " ; " " < " AA 8 AADos derivaciones por izquierda diferentes para la palabra ; 0 < 3 son-? " lm" ; " lmA ; " lm ; " lm ; " < " lm ; A < " lm ; 0 < " lm ; 0 < A lm ; 0 < 3? " lm" < " lm" ; " < " lmA ; " < " lm ; " < "
lm ; A < "
lm ; 0 < "
lm ; 0 < A lm ; 0 < 3Esto demuestra que la gramtica es ambigua. En estecaso' el problema se produce porque la gramtica no
puede determinar la precedencia de los operadores ; y
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
16/23
/omo el producto tiene mayor precedencia que la suma'
la primera de las derivaciones es la deseable' ya que sebusca que la e:presin sea evaluada como ; %0 < 3* yno como % ; 0* < 3. )ara eliminar la ambigedad' senecesitan otras variables' cada una de las cualese:presar un concepto diferente. "e usar el s1mboloinicial " para denotar una e:presin aritm,tica con suma yproducto. +a variable A representar el t,rmino de unasuma y 6 el factor de un producto. +as siguientes reglasproducen una gramtica no ambigua para el lenguaje en
cuestin-" " ; A A
A A < 6 6 %"*6 8 66
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
17/23
+a primer regla dice que una e:presin es un t,rmino o
una e:presin ms un t,rmino. Btese que la regla" " ; A fuerza a la gramtica a asociar a la suma porizquierdaF de lo contrario' se habr1a usado " A ; ". +asegunda dice que un t,rmino es el producto de un t,rminocon un factor' un factor o una e:presin entre par,ntesis.+a tercer regla dice que un factor es un d1gito o laconcatenacin de dos d1gitos./omo < tiene mayor precedencia que ; %es decir' deberesolverse primero a menos que los par,ntesis indiquen
otra cosa*' ,sta debe ocupar lugares ms cercanos a lara1z en el rbol de derivacin.
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
18/23
/on las nuevas reglas' la derivacin ms a la izquierda
para la palabra ; 0 < 3 es-" lm" ; A lmA ; A lm6 ; A lm ; A lm ; A < 6 lm ; 6 < 6 lm ; 0 < 6 lm ; 0 < 3. G el rbolresultante es-
"
" ; A
A A < 6
6 6 3
0
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
19/23
/omo la e:presin tiene una suma y un producto sin que
haya par,ntesis' la gramtica obliga a que se apliqueprimero la regla antes que la 0' por lo que la sumaestar ms cerca de la ra1z del rbol.)or 2ltimo' la gramtica vista asocia a la suma y alproducto por izquierda' si bien se podr1a haber optado porlo contrario. "in embargo' podr1a haber operaciones queforzosamente deban asociarse por izquierda o porderecha. )or ejemplo' la potenciacin asocia por derecha."i se denota a la misma con el signo ' se dir que
0 3 0 $ 0 %3 0* $ 0 $ H0.
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
20/23
Ejercicios
* a* Escriba una gramtica libre de conte:to no ambiguapara e:presiones con n2meros enteros y las operaciones;' ?'
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
21/23
3* /onsid,rese la gramtica " a" a"b" .
Esta gramtica es ambigua. Demuestre que la cadena aabtiene dos-
a*rboles de derivacin.
b*Derivaciones ms a la izquierda.
c*Derivaciones ms a la derecha.
L* Determine una gramtica no ambigua para el lenguajedel ejercicio 3. El lenguaje tiene todas y slo las cadenasformadas por s1mbolos a y s1mbolos b en las que ns1mbolos b consecutivos estn precedidos por n o mss1mbolos a.
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
22/23
H* Escriba una gramtica no ambigua para el
lenguaje de los identificadores cuyos elementosson secuencias de letras' d1gitos o guiones bajos'empezando con una letra o un guin bajo.
-
7/24/2019 Ambigedad_Deteccin_y_Eliminacin
23/23
-MCNA+' "eraf1nF Modelos de Computacin I.Departamento de /iencias de la /omputacin e OA. E("OOnformtica. !niversidad de #ranada. /ap1tulo L.
-KC)/NCP(' Qohn EF MC(RABO' NajeevF !+MAB' QeffreyD. Ontroduccin a la teora de autmatas, lenguaes !computacin. )earson. (ercera edicin. /ap1tulos H.0 yH.L.
Puentes