ambigüedad_detección_y_eliminación

7/24/2019 Ambigedad_Deteccin_y_Eliminacin

1/23

Ambigedad. Deteccin yeliminacin

Enzo Andreetto


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.


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.


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


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


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/23

Dada una gramtica # $ %&' (' )' "*' las siguientesafirmaciones son equivalentes-

? +a inferencia recursiva determina que la cadena terminalwpertenece al lenguaje de la variableA.?A< w.?A


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" ; " < ".

" " " ; " " < "

" < " " ; "


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


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 " .


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.


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


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*.


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.


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


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


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.


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


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.


20/23

Ejercicios

* a* Escriba una gramtica libre de conte:to no ambiguapara e:presiones con n2meros enteros y las operaciones;' ?'


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.


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.


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

ambigüedad_detección_y_eliminación

Documents