4-3_Ambiguedad
-
Upload
nilas-arcanister -
Category
Documents
-
view
221 -
download
0
description
Transcript of 4-3_Ambiguedad
-
El ProblemaConceptos
Ambigedad
La Ambigedad en el ParsingDefinicin y Ejemplos
Universidad de Cantabria
Dificultades
-
El ProblemaConceptos
Ambigedad
Outline
1 El Problema
2 Conceptos
3 Ambigedad
Dificultades
-
El ProblemaConceptos
Ambigedad
El Problema
En nuestra busqueda por encontrar la estructura exploraremoscomo elegir una derivacin entre varias opciones. No soloqueremos que la derivacin sea nica por sus propiedades,queremos que refleje algo del rbol de derivacin.
Dificultades
-
El ProblemaConceptos
Ambigedad
El Problema
Ntese que hay dos elementos indeterministas, para dar lasolucin al problema de palabra:
La produccin que elegimos.La eleccin de sobre qu variable actuamos.
Dificultades
-
El ProblemaConceptos
Ambigedad
El Problema
La idea de introducir derivaciones ms a la izquierda o ms ala derecha consiste en tratar de reducir el ingredienteindeterminstico a la hora de seleccionar qu variable es lavariable sobre la que vamos a actuar con nuestrasproducciones.
Dificultades
-
El ProblemaConceptos
Ambigedad
Derivaciones a la Izquierda y la Derecha
Definicin (Derivaciones Leftmost)
Sea G = (V ,,Q0,P) una gramtica libre de contexto. Seanc, c (V ) dos formas sentenciales.Diremos que c se obtiene mediante derivacin ms a laizquierda (o leftmost) de c, si existen ,A V , (V ), y existe una produccin A 7 ,con (V ) tales que
c = A, c = .
Denotaremos mediante c Glm c.
Dificultades
-
El ProblemaConceptos
Ambigedad
Derivaciones a la Izquierda y la Derecha
Definicin (Derivacin Rightmost)
Sea G = (V ,,Q0,P) una gramtica libre de contexto. Seanc, c (V ) dos formas sentenciales.Diremos que c se obtiene mediante derivacin ms a laderecha (o rightmost) de c, si existen (V ),A V , , y existe una produccin A 7 ,con (V ) tales que
c = A, c = .
Denotaremos mediante c Grm c.
Dificultades
-
El ProblemaConceptos
Ambigedad
Observaciones
Usualmente, y si no hay confusin, omitiremos el super-ndiceG.Las derivaciones a la izquierda suelen ser las ms naturales,pero las derivaciones ms a la derecha tienen ms interesprctico.
Dificultades
-
El ProblemaConceptos
Ambigedad
Cadenas de Derivaciones
DefinicinDiremos que c es deducible de c mediante derivaciones ms ala izquierda (y lo denotaremos mediante c `Glm c) si existe unacadena finita de derivaciones ms a la izquierda que va de c ac. Esto es, si existen:
c = c0 Glm c1 Glm ck1 Glm ck = c.
Dificultades
-
El ProblemaConceptos
Ambigedad
Cadenas de Derivaciones
DefinicinDiremos que c es deducible de c mediante derivaciones ms ala derecha (y lo denotaremos mediante c `Grm c) si existe unacadena finita de derivaciones ms a la derecha que va de c ac. Esto es, si existen:
c = c0 Grm c1 Grm ck1 Grm ck = c.
Dificultades
-
El ProblemaConceptos
Ambigedad
Ejemplos
EjemploTomemos la gramtica cuyas producciones son:
P := {Q0 7 AB | CA | AQ0 | 0,A 7 BA | 0A0 | 1,B 7 Q0A,C 7 1}.
Una cadena de derivaciones leftmost (ms la izquierda) serala siguiente:
Q0 AB CAB 1AB 11B 11Q0A 110A 1101.
Una cadena de derivaciones rightmost (ms a la derecha)sera la siguiente:
Q0 AB AQ0A AQ01 A01 0A001 01001.Dificultades
-
El ProblemaConceptos
Ambigedad
Grmaticas Ambiguas
Hemos dicho que la informacin de un programa estacontenida en la estructura. Qu pasa si una palabra en ellenguaje tiene ms de una estructura?
Dificultades
-
El ProblemaConceptos
Ambigedad
Grmaticas Ambiguas
Definicin (Gramticas Ambiguas)
Una gramtica se dice ambigua si existe una forma sentencial (V ) alcanzable desde el smbolo inicial (i.e Q0 `G )tal que existen al menos dos computaciones (derivaciones)ms a la izquierda (o ms a la derecha) distintas que permitengenerar .
Dificultades
-
El ProblemaConceptos
Ambigedad
Ejemplo
Ejemplo
Tomemos la gramtica P := {E 7 E + E | E E | a}. Ahoradisponemos de dos cadenas de derivacin para a + a adistintas:
E lm E +E lm a+E lm a+E E lm a+aE lm a+aa.
Y tambin
E lm EE lm E+EE lm a+EE lm a+aE lm a+aa.
Por lo que la anterior gramtica es ambigua.
Dificultades
-
El ProblemaConceptos
Ambigedad
La Ambiguedad es Indecidible
TeoremaDecidir si una gramtica libre de contexto es ambigua esindecidible (i.e. no existe algoritmo que permita decidir lacualidad de ser ambigua).
Dificultades
-
El ProblemaConceptos
Ambigedad
Observaciones
Hay muchas gramticas que se generan por medio demquinas (serialization)Hay lenguajes que solo admiten gramticas ambiguas.Hay tcnicas para eliminar algunas causas de laambiguedad.
Dificultades
El ProblemaConceptosAmbigedad