Algoritmos de análisis para gramáticas de inserción de árboles: Relaciones (LSI-2003-01)

Algoritmos de an´alisis para gram´aticas de inserci´on de ´arboles: Relaciones. Vicente Carrillo Departamento de Lenguajes y Sistemas Inform´aticos Universidad de Sevilla [email protected] Resumen Tree Insertion Grammar (TIG) es un compromiso entre Context Free Grammar (CFG) y Tree Adjoining Grammar (TAG) que puede ser analizada con un coste temporal de O(n3). En la literatura, tan s´olo han sido descritos dos algoritmos de an´alisis para TIGs, basados en los ya conocidos CYK y Earley para CFGs. En este informe se describen en detalle los analizadores para TIGs presentados en [7, 5, 4], as´ı como las relaciones formales existentes entre ellos. El objetivo es definir la espina dorsal del n´ucleo de una taxonom´ıa de analizadores basados en el algoritmo de Earley, similar a las ya existentes para CFGs [20] y TAGs [1] [9]. 1 Introducci´on Las gram´aticas de adjunci´on de ´arboles (Tree Adjoining Grammar, TAG) [14] constituyen un formalismo naturalmente lexicalizado muy adecuado para la descripci´on de la sintaxis de los lenguajes naturales. Como contrapartida, el proceso de an´alisis para este formalismo implica mayores costes computacionales que el mismo proceso para las gram´aticas independientes del contexto (Context Free Grammar, CFG): la complejidad temporal en el caso peor de los analizadores para TAG es de O(n6), donde nes la longitud de la cadena de entrada, frente a la complejidad O(n3) que presentan los analizadores para CFG. En los ´ultimos a˜nos, se han descrito muchas aproximaciones que intentan mejorar las prestaciones de los analizadores para TAG: unas basadas en la compilaci´on de los ´arboles elementales en aut´omatas de estados finitos [13], otras que aplican ciertos filtros a los algoritmos de an´alisis [6, 8, 11] y otras, como la empleada en este trabajo, basadas en restricciones sobre el formalismo [15]. 1 Las gram´aticas de inserci´on de ´arboles (Tree Insertion Grammar, TIG) [15] constituyen un compromiso entre CFG y TAG que combina la eficiencia de an´alisis de las primeras con la fuerte lexicalizaci´on de las segundas, ya que, al igual que ocurre con las CFGs, cualquier TIG se puede analizar con un coste temporal de O(n3) en el peor caso y, por otra parte, al ser las TIGs una subclase de las TAGs, se encuentran naturalmente lexicalizadas. La importancia del formalismo TIG se fundamenta en el hecho de que la mayor´ıa de las gram´aticas de adjunci´on de ´arboles de amplia cobertura se corresponden en su mayor parte con dicho formalismo. Esta afirmaci´on se puede comprobar en la gram´atica del ingl´es XTAG [12], donde el 99% de los ´arboles y adjunciones posibles son compatibles con el formalismo TIG. La mayor´ıa de los analizadores para TAG y TIG son extensiones de analizadores bien conocidos para CFG. En la literatura podemos encontrar multitud de analizadores para TAG, algunos usan una estrategia ascendente [2, 10, 17], otros utilizan estrategias ascendentes predictivas de manera similar al algoritmo de Earley para CFG [2, 16] y otros, como [11, 8], usan una adaptaci´on para TAG del conocido filtro left corner para CFG con objeto de aumentar las prestaciones de los analizadores predictivos. Podr´ıa pensarse que los analizadores para TIG pueden ser derivados directamente de los analizadores para TAG, dadas las similitudes entre ambos formalismos. Sin embargo, los aspectos que los diferencian son lo suficientemente significativos como para hacer que tal adaptaci´on no sea sencilla de realizar. Como ilustraci´on, podemos considerar la enorme diferencia existente entre el analizador de tipo Earley para TAG y el analizador de tipo Earley para TIG definido en [15].En [7] se presentan un conjunto de analizadores para TIG, concretamente cuatro, tres que usan estrategia ascendente y uno ascendente predictivo. En este trabajo ampliamos esta red de analizadores para TIG, introduciendo un nuevo analizador que aplica un filtro de tipo left corner a una variante del analizador ascendente predictivo presentado en [7]. El informe se encuentra estructurado de la siguiente manera. Una primera secci´on donde se introducen los conceptos y la notaci´on necesarios. Dada la longitud del trabajo, hemos preferido dividir el bloque principal en dos partes. En la primera parte se describen en detalle algunos de los analizadores para TIGs presentados en [7] y las relaciones formales existentes entre ellos. Como punto de partida definiremos un esquema basado en el conocido algoritmo CYK para CFGs. A continuaci´on definiremos un esquema ascendente basado en Earley que nos permita ampliar la clase de gram´aticas sobre la que pueda actuar. Y concluiremos el conjunto de esquemas de estrategia 2 ascendente con la presentaci´on de un analizador con recorrido bidireccional de la cadena de entrada al estilo del propuesto por de Vreught y Honig para CFGs [21]. Como punto final de esta primera red de analizadores, introduciremos una variante del esquema basado en el algoritmo de Earley para TIGs [15] y estableceremos las relaciones formales existentes entre ellos. En la segunda parte se define el concepto de left corner en el contexto del formalismo TIG, el cual se aplica para obtener una versi´on ascendente y dos predictivas de algoritmos basados en LC para TIG. Tambi´en se presentar´a una variante predictiva que servir´a como esquema intermedio para mostrar la relaci´on existente entre los dos analizadores predictivos definidos. Para terminar demostraremos las relaciones existentes entre estos esquemas y los presentados en la primera parte. 2 Notaci´on Una TIG es una 5-tupla (VN, VT, S, I,A), donde VNes un conjunto de s´ımbolos no terminales, VTes un conjunto de s´ımbolos terminales, S∈VN es el axioma, Ies un conjunto finito de ´arboles iniciales finitos y Aes un conjunto finito de ´arboles auxiliares finitos. Al conjunto I∪Ase le denomina ´arboles elementales. Nos referiremos a la ra´ız de un ´arbol elemental γ como Rγ. En cada ´arbol elemental, los nodos de la frontera se etiquetan con s´ımbolos terminales, la palabra vac´ıa (ε) o s´ımbolos no terminales marcados para sustituci´on, excepto un nodo en cada ´arbol auxiliar, cuya etiqueta es la misma que la de la ra´ız y que se denomina nodo pie. Denotaremos como Fβ al nodo pie de un ´arbol auxiliar β. Denominamos espina al camino de la ra´ız al pie de un ´arbol auxiliar. Usaremos label(Mγ) para denotar la etiqueta asociada al nodo Mγ. Los ´arboles auxiliares en los cuales todo nodo frontera est´a a la izquierda (derecha) del nodo pie se denominan ´arboles auxiliares izquierdos (derechos). El resto de ´arboles auxiliares se denominan ´arboles wrapping. Usaremos A L yA R para denotar los conjuntos de ´arboles auxiliares izquierdos y derechos, respectivamente. Una derivaci´on TIG comienza con un ´arbol inicial cuya ra´ız est´a etiquetada por S. Este ´arbol se extiende repetidamente usando las operaciones de adjunci´on ysustituci´on. La adjunci´on inserta un ´arbol auxiliar βen el nodo Mγde un ´arbol γque tenga la misma etiqueta que Rβ. En concreto, Mγes reemplazado por βyFβes reemplazado por el sub´arbol dominado por Mγ. Usaremos β∈adj(Mγ) para denotar que un ´arbol β∈Apuede ser adjuntado en un nodo Mγ, es decir, Mγes un nodo de adjunci´on. Si la adjunci´on 3 no es obligatoria en Mγentonces nil ∈adj(Mγ), donde nil es un s´ımbolo vac´ıo. La adjunci´on de un ´arbol auxiliar izquierdo (derecho) se denomina adjunci´on izquierda (derecha). Usaremos β∈ladj(Mγ) (β∈radj(Mγ)) para denotar que β∈A L (β∈A R ) se puede adjuntar en el nodo Mγ, es decir, Mγes un nodo de adjunci´on izquierda (derecha). Si una adjunci´on izquierda (derecha) no es obligatoria en el nodo Mγentonces nil ∈ladj(Mγ) (nil ∈radj(Mγ)). La sustituci´on es una operaci´on obligatoria y reemplaza un nodo marcado para sustituci´on Mγcon una copia de un ´arbol inicial α cuya ra´ız est´e etiquetada igual que Mγ. Usamos α∈subst(Mγ) para indicar que el nodo Mγpuede ser sustituido por el ´arbol α∈I. TIG no permite: (1) ´arboles auxiliares wrapping, (2) la adjunci´on de un ´arbol auxiliar izquierdo (derecho) en la espina de un ´arbol auxiliar derecho (izquierdo) y (3) la adjunci´on en los nodos ra´ız y pie de los ´arboles auxiliares. Para incrementar los ´arboles que se pueden generar, TIG permite un n´umero arbitrario de adjunciones simult´aneas sobre un mismo nodo. La adjunci´on simult´anea es una operaci´on esencialmente ambigua y provoca la creaci´on de muchos ´arboles diferentes. F´acilmente se pueden imaginar variantes de TIG donde la adjunci´on simult´anea est´e m´as limitada. Para no incrementar la ambiguedad de la derivaci´on, hemos elegido para la definici´on de los esquemas la variante de TIG presentada en [18], que como m´aximo permite una adjunci´on izquierda y otra derecha sobre un mismo nodo. Adem´as, para mantener los ´arboles que se pueden generar mediante adjunci´on simult´anea, permitiremos la adjunci´on en los nodos ra´ız y pie de los ´arboles auxiliares. Con objeto de representar los ´arboles de an´alisis parciales, definimos una producci´on Nγ→Nγ 1. . . Nγ gpara cada nodo Nγy sus secuencia ordenada de ghijos Nγ 1. . . Nγ gen un ´arbol elemental. Denotaremos el conjunto de producciones asociado a un ´arbol elemental γcomo P(γ). Por razones t´ecnicas, consideramos las producciones adicionales > → Rα,> → Rβy Fβ→ ⊥ para cada ´arbol inicial αy cada ´arbol auxiliar β. Para mantener la capacidad generativa de la gram´atica, se proh´ıbe la adjunci´on y sustituci´on en los nodos >y⊥. Los esquemas de an´alisis sint´actico [20] constituyen un m´etodo general para la especificaci´on de algoritmos de an´alisis sint´actico, que surge como una formalizaci´on de trabajos presentados sobre analizadores deductivos [19]. Entre sus ventajas fundamentales se encuentran: •Definici´on de los analizadores sin tener en cuenta las estructuras de datos y de control que se usar´an en su implementaci´on. •Permite establecer de una manera f´acil las relaciones entre distintos algoritmos mediante el an´alisis de ciertas relaciones formales. 4 El uso de sistemas de an´alisis para la especificaci´on de analizadores sint´acticos nos permite explotar todas las propiedades de los sistemas deductivos, entre otras, la posibilidad de establecer relaciones entre distintos sistemas. En [3] se pueden encontrar todas las definiciones necesarias para comprender y aplicar los esquemas de an´alisis sint´actico y la notaci´on referente a ellos empleadas a lo largo de este informe. 3 Esquema basado en CYK El primer esquema que veremos, que denominaremos CYKi, presenta una estrategia de an´alisis ascendente con lectura unidireccional, de izquierda a derecha, de la cadena de entrada. Se trata de una extensi´on del algoritmo CYK definido originalmente para gram´aticas independientes del contexto. El esquema CYKifue introducido en [7] y se basa en el presentado en forma algor´ıtmica para las SLTIG en [18]. El esquema CYKis´olo es aplicable a la clase de gram´aticas de inserci´on de ´arboles CNFT IG cuyos ´arboles elementales presentan las siguientes restricciones: (i) un nodo interno, salvo el nodo pie, dominar´a directamente un m´aximo de dos nodos y (ii) los nodos etiquetados con s´ımbolos terminales, la palabra vac´ıa o el nodo bottom no tendr´an nodos hermanos. El dominio del esquema CYKiviene dado por: ICYKi={[Mγ, i, j, code]|Mγ∈VN,γ∈I∪A, 0≤i≤j,code ⊆ {L, R}} La funci´on del par´ametro code es indicar si sobre el nodo Mγse ha completado una adjunci´on izquierda y/o derecha o no se ha completado ninguna adjunci´on, y puede tomar uno de los siguientes valores: • ∅ si no ha ha completado ninguna adjunci´on en el nodo Mγ, • {L}si se ha completado una adjunci´on de un ´arbol auxiliar izquierdo en el nodo Mγ, • {R}si se ha completado una adjunci´on de un ´arbol auxiliar derecho en el nodo Mγ, • {L, R}si se ha completado las adjunciones de un ´arbol auxiliar izquierdo y otro derecho en el nodo Mγ. 5 Los pasos deductivos del esquema son: DCYKi=DScan CYKi∪ Dε CYKi∪ DCompUna CYKi∪ DCompBin CYKi∪ DLAdj CYKi∪ DRadj CYKi∪ DSubs CYKi DScan CYKi=[a, j, j + 1] [Nγ, j, j + 1,∅]Nγ→a∈ P(γ) Dε CYKi=[Nγ, j, j, ∅] Nγ→ε∈ P(γ) ´o Nγ→ ⊥ DCompUna CYKi=[Oγ, i, j, code] [Mγ, i, j, ∅]Mγ→Oγ∈ P(γ) donde se debe cumplir: (i) (nil ∈ladj(Oγ) y L /∈code) ´o (β∈ladj(Oγ) y L∈code), (ii) (nil ∈radj(Oγ) y R /∈code) ´o (β∈radj(Oγ) y R∈code). DCompBin CYKi= [Oγ 1, i, j, code] [Oγ 2, j, k, code0] [Mγ, i, k, ∅]Mγ→Oγ 1Oγ 2∈ P(γ) donde se debe cumplir: (i) (nil ∈ladj(Oγ 1) y L /∈code) ´o (β∈ladj(Oγ 1) y L∈code), (ii) (nil ∈radj(Oγ 1) y R /∈code) ´o (β∈radj(Oγ 1) y R∈code), (iii) (nil ∈ladj(Oγ 2) y L /∈code0) ´o (β∈ladj(Oγ 2) y L∈code0), (iv) (nil ∈radj(Oγ 2) y R /∈code0) ´o (β∈radj(Oγ 2) y R∈code0). DLAdj CYKi= [Pβ, i, j, ∅] [Mγ, j, k, code] [Mγ, i, k, {L} ∪ code] label(Pβ) = > β∈ladj(Mγ) L /∈code DRAdj CYKi= [Pβ, j, k, ∅] [Mγ, i, j, code] [Mγ, i, k, {R} ∪ code] label(Pβ) = > β∈radj(Mγ) R /∈code DSubs CYKi=[Pα, i, j, ∅] [Mγ, i, j, ∅] label(Pα) = > α∈subst(Mγ) 6 Los pasos deductivos DScan CYKi,Dε CYKison los que inician el reconocimiento ascendente. Tambi´en se incluye en este caso los nodos pies de los ´arboles auxiliares, ya que en los ´arboles auxiliares TIGs no es necesario transmitir la informaci´on del sub´arbol escindido. Una vez reconocido el sub´arbol dominado por un nodo, los pasos DCompUna CYKi yDCompBin CYKipermiten continuar el reconocimiento ascendente. Cuando se ha reconocido un ´arbol auxiliar izquierdo (resp. derecho), el paso DLAdj CYKi (DRAdj CYKi) efect´ua la adjunci´on en un nodo de adjunci´on izquierda (resp. derecha), siempre que el reconocimiento lo haya alcanzado y no haya sido ya adjuntado por la izquierda (resp. derecha). La condici´on que acompa˜na a ambos pasos de compleci´on comprueba que el nodo que domina el sub´arbol que se va a completar no presente adjunci´on (izquierda y/o derecha) obligatoria y, en el caso de presentarla, que se haya efectuado. Por ´ultimo, la operaci´on DSubs CYKisustituye un ´arbol inicial que ha sido completamente reconocido en todos los nodos de sustituci´on donde se puede sustituir dicho ´arbol. El conjunto de ´ıtems finales se define como: FCYKi={[Pα,0, n, ∅]|α∈I, label(Pα) = >, label(Rα) = S} 4 Esquema ascendente basado en Earley Este esquema, al que vamos a denominar buEi, es una adaptaci´on para TIGs del esquema ascendente basado en Earley (bottom-up Earley para CFGs descrito en [20]. Fue presentado en [7] y se puede obtener a partir de una generalizaci´on del esquema CYKi. El inter´es de este esquema radica en que se trata de un reconocedor con estrategia ascendente que elimina la restricci´on impuesta por el esquema anterior sobre la forma que deben tener los ´arboles elementales. El dominio del esquema buEies: IbuEi=I(i) buEi∪ I(ii) buEi I(i) buEi={[Mγ→δ•ν, i, j, ∅]|Mγ→δν ∈ P(γ) , γ∈I∪A, 0≤i≤j,ν6=ε} donde el valor ∅indica que no se ha completado ninguna adjunci´on en el nodo Mγ. 7 I(ii) buEi={[Mγ→ν•, i, j, code]|Mγ→ν∈ P(γ) , γ∈I∪A, 0≤i≤j,code ⊆ {L, R}} donde code =∅si no se complet´o ninguna adjunci´on sobre Mγ,code = {L}si se complet´o una adjunci´on izquierda sobre Mγ,code ={R}si se complet´o una adjunci´on derecha sobre Mγycode ={L, R}si se complet´o una adjunci´on izquierda y otra derecha sobre Mγ. Los pasos deductivos del esquema son: DbuEi=DIni buEi∪ DScan buEi∪ Dε buEi∪ DComp buEi∪ DLAdj buEi∪ DRadj buEi∪ DSubs buEi DIni buEi=[Nγ→ •ν, i, i, ∅]γ∈I∪A DScan buEi= [a, j, j + 1] [Nγ→δ•Mγν, i, j, ∅] [Nγ→δMγ•ν, i, j + 1,∅]label(Mγ) = a Dε buEi=[Nγ→δ•Mγν, i, j, ∅] [Nγ→δMγ•ν, i, j, ∅] label(Mγ) = ε ´o label(Mγ) = ⊥ DComp buEi= [Mγ→ω•, j, k, code] [Nγ→δ•Mγν, i, j, ∅] [Nγ→δMγ•ν, i, k, ∅] donde se debe cumplir: (i) (nil ∈ladj(Mγ) y L /∈code) ´o (β∈ladj(Mγ) y L∈code), (ii) (nil ∈radj(Mγ) y R /∈code) ´o (β∈radj(Mγ) y R∈code). DLAdj buEi= [> → Rβ•, i, j, ∅] [Mγ→ν•, j, k, code] [Mγ→ν•, i, k, {L} ∪ code] β∈ladj(Mγ) L /∈code DRAdj buEi= [> → Rβ•, j, k, ∅] [Mγ→ν•, i, j, code] [Mγ→ν•, i, k, {R} ∪ code] β∈radj(Mγ) R /∈code 8 DSubs buEi= [> → Rα•, j, k, ∅] [Nγ→δ•Mγν, i, j, ∅] [Nγ→δMγ•ν, i, k, ∅]α∈subst(Mγ) El paso DIni buEiinicia el reconocimiento desde todos los sub´arboles de los ´arboles elementales. El paso DScan buEireconoce la presencia de un s´ımbolo terminal en la cadena de entrada. Mientras Dε buEirefleja el hecho de que se puede saltar sobre nodos etiquetados con εy nodos pie sin tener que reconocer nada. El paso DComp buEicontin´ua el reconocimiento ascendente cuando se ha completado el reconocimiento de un sub´arbol. El resto de pasos funcionan de forma an´aloga a los hom´onimos del esquema anterior. El conjunto de ´ıtems finales es: FbuEi={[> → Rα•,0, n, ∅]|α∈I, label(Rα) = S} 4.1 Una variante del esquema ascendente basado en Earley Si estudiamos con atenci´on el esquema buEipodemos observar ciertas deficiencias, las cuales son debidas esencialmente a que el paso DIni buEiinicia el reconocimiento de todos los sub´arboles, sin comprobar que la ra´ız del mismo sea un nodo que presente una restricci´on de adjunci´on izquierda obligatoria. Ello provoca un doble problema, el primero es de prestaciones del analizador, ya que puede reconocer sub´arboles que no son correctos y cuya incorrecci´on no se detecta hasta que se lleva a cabo un paso de compleci´on de sub´arbol. Y de ´esto se deriva el segundo problema, debido a que el paso DComp buEidebe conocer las adjunciones que se han efectuado antes de realizar la compleci´on, lo que obliga al analizador a llevar esta informaci´on. Sin embargo, si se controla el inicio del reconocimiento de cada sub´arbol obtendr´ıamos un doble beneficio: (1) aumentar´ıamos la eficiencia eliminando del reconocimiento sub´arboles que de partida sabemos que son incorrectos y (2) el par´ametro code se simplificar´ıa, ya que s´olo debe indicar si tuvo lugar una adjunci´on derecha sobre el nodo. El esquema que proponemos, al que denominaremos buEk, pretende paliar estos problemas. Se obtiene modificando las condiciones laterales de los pasos DIni buEiyDComp buEi, el paso DLAdj buEiy la forma del par´ametro code del esquema buEi. El dominio del esquema buEkes: IbuEk=I(i) buEk∪ I(ii) buEk 9 Compleci´on de sub´arbol Este paso deductivo de compleci´on de sub´arbol es igual al del esquema buEk: DComp Earleyi=DComp buEk Predicci´on de adjunci´on izquierda Cuando el reconocimiento alcanza un nodo adjuntable por la izquierda, el an´alisis debe lanzar el reconocimiento de todos los ´arboles auxiliares que se pueden adjuntar en ´el: DLAdjPred Earleyi=[Nγ→δ•Mγν, i, j, false] [> → •Rβ, j, j, false]β∈ladj(Mγ) Compleci´on de adjunci´on izquierda Una vez que se ha completado el reconocimiento de un ´arbol auxiliar izquierdo, debemos continuar el reconocimiento del ´arbol donde se ha efectuado la adjunci´on: DLAdjComp Earleyi= [> → Rβ•, j, k, false] [Nγ→δ•Mγν, i, j, false] [Mγ→ •ν, j, k, false]β∈ladj(Mγ) Predicci´on de adjunci´on derecha Cuando se completa el reconocimiento de un sub´arbol dominado por un nodo adjuntable por la derecha, el an´alisis debe lanzar el reconocimiento de todos los ´arboles auxiliares que se pueden adjuntar en ´el: DRAdjPred Earleyi=[Mγ→ν•, i, j, false] [> → •Rβ, j, j, false]β∈radj(Mγ) Compleci´on de adjunci´on derecha El paso deductivo de compleci´on de adjunci´on derecha es igual al del esquema buEk: DRAdjComp Earleyi=DRAdj buEk Predicci´on de sustituci´on 16 Cuando el reconocimiento alcanza un nodo marcado para sustituci´on, el an´alisis debe lanzar el reconocimiento de todos los ´arboles iniciales que se pueden sustituir en ´el: DSubsPred Earleyi=[Nγ→δ•Mγν, i, j, false] [> → •Rα, j, j, false]α∈subst(Mγ) Compleci´on de sustituci´on El paso deductivo de compleci´on de sustituci´on es igual al del esquema buEk: DSubsComp Earleyi=DSubs buEk El conjunto de ´ıtems finales es igual al del esquema buEk: FEarleyi=FbuEk 7 Relaciones entre esquemas Teorema 7.1 Relaci´on entre los esquemas CYKiybuEi Se mantienen las siguientes relaciones entre esquemas: CYKisc =⇒CYKi 1 ir =⇒CYKi 2 sr =⇒ECYKiext =⇒buEi Prueba El esquema CYKi 1se obtiene desdoblando el paso de sustituci´on del esquema CYKien cuatro. El dominio del nuevo esquema es igual al del CYKi: ICYKi 1=ICYKi El conjunto de pasos deductivos es: DCYKi 1=DScan CYKi 1∪ Dε CYKi 1∪ DCompUna CYKi 1 ∪ DCompBin CYKi 1 ∪ DLAdj CYKi 1 ∪ DRadj CYKi 1 ∪ DSubsUna CYKi 1∪ DSubsBin1 CYKi 1 ∪ DSubsBin2 CYKi 1 ∪ DSubsBin3 CYKi 1 DScan CYKi 1=DScan CYKi 1 Dε CYKi 1=Dε CYKi 1 17 DCompUna CYKi 1 =DCompUna CYKi 1 DCompBin CYKi 1 DCompBin CYKi 1 DLAdj CYKi 1 =DLAdj CYKi 1 DRadj CYKi 1 =DRadj CYKi 1 DSubsUna CYKi 1=[Pα, i, j, ∅] [Mγ, i, j, ∅] label(Pα) = > Mγ→Oγ∈ P(γ) α∈subst(Oγ) DSubsBin1 CYKi 1 = [Pα, i, j, ∅] [Oγ 2, j, k, code] [Mγ, i, k, ∅] label(Pα) = > Mγ→Oγ 1Oγ 2∈ P(γ) α∈subst(Oγ 1) donde se debe cumplir: (i) (nil ∈ladj(Oγ 2)yL /∈code)´o (β∈ladj(Oγ 2)yL∈code), (ii) (nil ∈radj(Oγ 2)yR /∈code)´o (β∈radj(Oγ 2)yR∈code). DSubsBin2 CYKi 1 = [Oγ 1, i, j, code] [Pα, j, k, ∅] [Mγ, i, k, ∅] label(Pα) = > Mγ→Oγ 1Oγ 2∈ P(γ) α∈subst(Oγ 2) donde se debe cumplir: (i) (nil ∈ladj(Oγ 1)yL /∈code)´o (β∈ladj(Oγ 1)yL∈code), (ii) (nil ∈radj(Oγ 1)yR /∈code)´o (β∈radj(Oγ 1)yR∈code). DSubsBin3 CYKi 1 = [Pα, i, j, ∅] [Pα1, j, k, ∅] [Mγ, i, k, ∅] label(Pα) = > label(Pα1) = > Mγ→Oγ 1Oγ 2∈ P(γ) α∈subst(Oγ 1) α1∈subst(Oγ 2) El conjunto de items finales es id´entico al del esquema CYKi: FCYKi 1=FCYKi Para demostrar que CYKisc =⇒CYKi 1hay que probar que: 18 1. ICYKi 1⊆ ICYKi 2. `∗ CY Ki 1 ⊆`∗ CY Ki Lo primero es cierto por definici´on, ya que los dominios de ambos esquemas son iguales: ICYKi 1=ICYKi Para demostrar que `∗ CY Ki 1 ⊆`∗ CY Kinos basta con probar que DCYKi 1 ⊆`∗ CY Ki. Vamos a ver s´olo los pasos de sustituci´on, el resto de pasos son id´enticos en ambos esquemas: •Un paso deductivo DSubsUna CYKi 1 es equivalente a la secuencia formada por un paso DSubs CYKi [Pα, i, j, ∅] [Oγ, i, j, ∅] seguido de otro DCompUna CYKi [Oγ, i, j, code] [Mγ, i, j, ∅] •Un paso deductivo DSubsBin1 CYKi 1 es equivalente a una secuencia formada por un paso DSubs CYKi [Pα, i, j, ∅] [Oγ 1, i, j, ∅] seguido de otro DCompBin CYKi [Oγ 1, i, j, ∅] [Oγ 2, j, k, code] [Mγ, i, k, ∅] •Un paso deductivo DSubsBin2 CYKi 1 es equivalente a una secuencia formada por un paso DSubs CYKi [Pα, j, k, ∅] [Oγ 2, j, k, ∅] seguido de otro DCompBin CYKi [Oγ 1, i, j, code] [Oγ 2, j, k, ∅] [Mγ, i, k, ∅] 19 •Un paso deductivo DSubsBin3 CYKi 1 es equivalente a una secuencia formada por dos pasos DSubs CYKi [Pα, i, j, ∅] [Oγ 1, i, j, ∅] [Pα1, j, k, ∅] [Oγ 2, j, k, ∅] seguidos de otro DCompBin CYKi [Oγ 1, i, j, ∅] [Oγ 2, j, k, ∅] [Mγ, i, k, ∅] El esquema CYKi 2se obtiene incluyendo reglas de producci´on en los items del esquema CYKi 1. El dominio de CYKi 2se define mediante: ICYKi 2={[Mγ→ν•, i, j, code]|Mγ→ν∈ P(γ),γ∈I∪A, 0≤i≤j,code ⊆ {L, R}} El conjunto de pasos deductivos es: DCYKi 2=DScan CYKi 2∪ Dε CYKi 2∪ DCompUna CYKi 2 ∪ DCompBin CYKi 2 ∪ DLAdj CYKi 2 ∪ DRadj CYKi 2 ∪ DSubsUna CYKi 2∪ DSubsBin1 CYKi 2 ∪ DSubsBin2 CYKi 2 ∪ DSubsBin3 CYKi 2 DScan CYKi 2=[a, j, j + 1] [Nγ→Pγ•, j, j + 1,∅]label(Pγ) = a Dε CYKi 2=[Nγ→Pγ•, j, j, ∅]label(Pγ) = ε´o label(Pγ) = ⊥ DCompUna CYKi 2 =[Oγ→ν•, i, j, code] [Mγ→Oγ•, i, j, ∅] donde se debe cumplir: (i) (nil ∈ladj(Oγ)yL /∈code)´o (β∈ladj(Oγ)yL∈code), (ii) (nil ∈radj(Oγ)yR /∈code)´o (β∈radj(Oγ)yR∈code). DCompBin CYKi 2 = [Oγ 1→ν•, i, j, code] [Oγ 2→δ•, j, k, code0] [Mγ→Oγ 1Oγ 2•, i, k, ∅] 20 donde se debe cumplir: (i) (nil ∈ladj(Oγ 1)yL /∈code)´o (β∈ladj(Oγ 1)yL∈code), (ii) (nil ∈radj(Oγ 1)yR /∈code)´o (β∈radj(Oγ 1)yR∈code), (iii) (nil ∈ladj(Oγ 2)yL /∈code0)´o (β∈ladj(Oγ 2)yL∈code0), (iv) (nil ∈radj(Oγ 2)yR /∈code0)´o (β∈radj(Oγ 2)yR∈code0). DLAdj CYKi 2 = [> → Rβ•, i, j, ∅] [Mγ→ν•, j, k, code] [Mγ→ν•, i, k, {L} ∪ code] β∈ladj(Mγ) L /∈code DRAdj CYKi 2 = [> → Rβ•, j, k, ∅] [Mγ→ν•, i, j, code] [Mγ→ν•, i, k, {R} ∪ code] β∈radj(Mγ) R /∈code DSubsUna CYKi 2=[> → Rα•, i, j, ∅] [Mγ→Oγ•, i, j, ∅]α∈subst(Oγ) DSubsBin1 CYKi 2 = [> → Rα•, i, j, ∅] [Oγ 2→ν•, j, k, code] [Mγ→Oγ 1Oγ 2•, i, k, ∅]α∈subst(Oγ 1) donde se debe cumplir: (i) (nil ∈ladj(Oγ 2)yL /∈code)´o (β∈ladj(Oγ 2)yL∈code), (ii) (nil ∈radj(Oγ 2)yR /∈code)´o (β∈radj(Oγ 2)yR∈code). DSubsBin2 CYKi 2 = [Oγ 1→ν•, i, j, code] [> → Rα•, j, k, ∅] [Mγ→Oγ 1Oγ 2•, i, k, ∅]α∈subst(Oγ 2) donde se debe cumplir: (i) (nil ∈ladj(Oγ 1)yL /∈code)´o (β∈ladj(Oγ 1)yL∈code), (ii) (nil ∈radj(Oγ 1)yR /∈code)´o (β∈radj(Oγ 1)yR∈code). DSubsBin3 CYKi 2 = [> → Rα•, i, j, ∅] [> → Rα1•, j, k, ∅] [Mγ→Oγ 1Oγ 2•, i, k, ∅] α∈subst(Oγ 1) α1∈subst(Oγ 2) El conjunto de ´ıtems finales se define como: FCYKi 2={[> → Rα,0, n, code]|α∈I, label(Rα) = S} Probemos ahora la relaci´on CYKi 1 ir =⇒CYKi 2. Para ello debemos mostrar que existe una funci´on regular f:ICYKi 2→ ICYKi 1tal que: 21 1. ICYKi 1=f(ICYKi 2) 2. 4CYKi 1=f(4CYKi 2) Una funci´on regular de contracci´on de items que cumple estas condiciones es la siguiente: f([Nγ→δ•, i, j, code]) = [Nγ, i, j, code] De fse sigue inmediatamente que ICYKi 1=f(ICYKi 2)y4CYKi 1=f(4CYKi 2) por inducci´on en la longitud de las secuencias de derivaci´on. El esquema ECYKise obtiene a partir del esquema buEi, restringiendo la clase de gram´aticas sobre las que se define. De forma que el esquema ECYKis´olo est´a definido para la clase de gram´aticas de inserci´on de ´arboles en las cuales ning´un nodo puede tener m´as de dos descendientes y los nodos etiquetados con s´ımbolos terminales, εo⊥no tienen nodos hermanos. Los conjuntos de items, pasos deductivos y finales del esquema ECYKi son iguales a los del esquema buEi. IECYKi=IbuEi DECYKi=DIni ECYKi∪DScan ECYKi∪Dε ECYKi∪DComp ECYKi∪DLAdj ECYKi∪DRadj ECYKi∪DSubs ECYKi DIni ECYKi=DIni buEi DScan ECYKi=DScan buEi Dε ECYKi=Dε buEi DComp ECYKi=DComp buEi DLAdj ECYKi=DLAdj buEi DRadj ECYKi=DRadj buEi DSubs ECYKi=DSubs buEi FECYKi=FbuEi Para demostrar la relaci´on ECYKiext =⇒buEihay que probar: 1. CGECY Ki⊆CGbuEi 2. ECYKi(G)(a1. . . an) = buEi(G)(a1. . . an) para toda G∈ CGECYKiy cadena de entrada a1. . . an 22 Lo primero es obvio, ya que la subclase de gram´aticas sobre la que se define ECYKies un subconjunto de la clase de gram´aticas de inserci´on de ´arboles, sobre la cual est´a definido el esquema buEi. Lo segundo es cierto por definici´on, ya que ECYKi=buEi. A continuaci´on probaremos la relaci´on CYKi 2 sr =⇒ECYKi. Para ello tenemos que demostrar que: 1. ICYKi 2⊆ IECYKi 2. `∗ CY Ki 2 ⊆`∗ ECY Ki Lo primero es cierto porque el dominio del esquema CYKi 2, que solo contempla items con el punto al final de la regla, est´a contenido en el dominio de ECYKi: ICYKi 2⊂ IECYKi Para demostrar que `∗ CY Ki 2 ⊆`∗ ECY Kinos basta con probar que DCYKi 2 ⊆`∗ ECY Ki. Veamos cada paso: •Un paso deductivo DScan CYKi 2 es equivalente a una secuencia formada por un paso DIni ECYKi [Nγ→ •Mγ, j, j, ∅] seguido de otro DScan ECYKi [a, j, j + 1] [Nγ→ •Mγ, j, j, ∅] [Nγ→Mγ•, j, j + 1,∅] •Un paso deductivo Dε CYKi 2 es equivalente a una secuencia formada por un paso DIni ECYKi [Nγ→ •Mγ, j, j, ∅] seguido de otro Dε ECYKi [Nγ→ •Mγ, j, j, ∅] [Nγ→Mγ•, j, j, ∅] •Un paso deductivo DCompUna CYKi 2 es equivalente a una secuencia formada por un paso DIni ECYKi [Nγ→ •Mγ, j, j, ∅] 23 seguido de otro DComp ECYKi [Mγ→ν•, j, k, code] [Nγ→ •Mγ, j, j, ∅] [Nγ→Mγ•, j, k, code] •Un paso deductivo DCompBin CYKi 2 es equivalente a una secuencia formada por un paso DIni ECYKi [Nγ→ •MγPγ, i, i, ∅] seguido de una secuencia de dos pasos DComp ECYKi [Mγ→ν•, i, j, code] [Nγ→ •MγPγ, i, i, ∅] [Nγ→Mγ•Pγ, i, j, ∅] [Pγ→ω•, j, k, code0] [Nγ→Mγ•Pγ, i, j, ∅] [Nγ→MγPγ•, i, k, ∅] •Un paso deductivo DSubsUna CYKi 2 es equivalente a una secuencia formada por un paso DIni ECYKi [Nγ→ •Mγ, j, j, ∅] seguido de otro DSubs ECYKi [> → Rα•, j, k, ∅] [Nγ→ •Mγ, j, j, ∅] [Nγ→Mγ•, j, k, ∅] •Un paso deductivo DSubsBin1 CYKi 2 es equivalente a una secuencia formada por un paso DIni ECYKi [Nγ→ •MγPγ, i, i, ∅] seguido de uno DSubs ECYKi [> → Rα•, i, j, ∅] [Nγ→ •MγPγ, i, i, ∅] [Nγ→Mγ•Pγ, i, j, ∅] 24 y de otro DComp ECYKi [Pγ→ν•, j, k, code] [Nγ→Mγ•Pγ, i, j, ∅] [Nγ→MγPγ•, i, k, ∅] •Un paso deductivo DSubsBin2 CYKi 2 es equivalente a una secuencia formada por un paso DIni ECYKi [Nγ→ •MγPγ, i, i, ∅] seguido de uno DComp ECYKi [Mγ→ν•, i, j, code] [Nγ→ •MγPγ, i, i, ∅] [Nγ→Mγ•Pγ, i, j, ∅] y de otro DSubs ECYKi [> → Rα•, j, k, ∅] [Nγ→Mγ•Pγ, i, j, ∅] [Nγ→MγPγ•, i, k, ∅] •Un paso deductivo DSubsBin3 CYKi 2 es equivalente a una secuencia formada por un paso DIni ECYKi [Nγ→ •MγPγ, i, i, ∅] seguido de dos DSubs ECYKi [> → Rα•, i, j, ∅] [Nγ→ •MγPγ, i, i, ∅] [Nγ→Mγ•Pγ, i, j, ∅] [> → Rα1•, j, k, ∅] [Nγ→Mγ•Pγ, i, j, ∅] [Nγ→MγPγ•, i, k, ∅] 25 •Dado un paso [Nγ→δ•Mγν, i, j, false] [> → •Rα, j, j, false]∈ DSubsPred Earleyi existe un paso [Nγ→ •ν, j, j, false]∈ DIni buEk y, por tanto, existe la inferencia [Nγ→δ•Mγν, i, j, false]`buEk[> → •Rα, j, j, false] •El resto de pasos mantienen las siguientes equivalencias: DScan Earleyi=DScan buEk Dε Earleyi=Dε buEk DComp Earleyi=DComp buEk DRAdjComp Earleyi=DRAdj buEk DSubsComp Earleyi=DSubs buEk 8 Esquema ascendente guiado por la esquina izquierda De forma similar el esquema buLC para TAGs [6], este esquema elimina del dominio de buEkaquellos items que no aportan nada significativo en el proceso de an´alisis, y que son los items de la forma: [Mγ→ •ν, i, i, false] Al posibilitar el esquema buEkeste tipo de items, se provoca un aumento en el n´umero de items deducidos y, por tanto, una merma en el comportamiento pr´actico del analizador. Por ello proponemos modificar el dominio y los pasos deductivos de dicho esquema para evitar que se generen este tipo de items, obteniendo como resultado el esquema buLCi. El dominio del esquema buLCies: IbuLCi=I(i) buLCi∪ I(ii) buLCi 32 Ii buLCi={[Mγ→Pγδ•ν, i, j, false]|Mγ→δν ∈ P(γ) , γ∈I∪A, 0≤i≤j,ν6=ε} El subconjunto I(ii) buLCise define igual al del esquema buEk: I(ii) buLCi=I(ii) buEk Los pasos deductivos del esquema son: DbuLCi=DLCt buLCi∪ DLCε buLCi∪ DLCsubs buLCi∪ DLCn buLCi∪ DLAdjt buLCi∪ DLAdjε buLCi∪ DLAdjsubs buLCi∪ DLAdjn buLCi∪ Dε buLCi∪ DScan buLCi∪ DComp buLCi∪ DRAdj buLCi∪ DSubs buLCi DLCt buLCi=[a, j, j + 1] [Oγ→Mγ•ν, j, j + 1, false] nil ∈ladj(Oγ) label(Mγ) = a DLCε buLCi=[Oγ→Mγ•ν, j, j, false] nil ∈ladj(Oγ) label(Mγ) = ε´o label(Mγ) = ⊥ DLCsubs buLCi=[> → Rα•, j, k, false] [Oγ→Mγ•ν, j, k, false] nil ∈ladj(Oγ) α∈subst(Mγ) DLCn buLCi=[Oγ→δ•, j, k, radj] [Qγ→Oγ•ν, j, k, false] donde se debe cumplir: (i) nil ∈ladj(Qγ), (ii) si radj =false entonces nil ∈radj(Oγ). DLAdjt buLCi= [> → Rβ•, i, j, false] [a, j, j + 1] [Qγ→Mγ•ν, i, j + 1, false] β∈ladj(Qγ) label(Mγ) = a DLAdjε buLCi=[> → Rβ•, i, j, false] [Qγ→Mγ•ν, i, j, false] β∈ladj(Qγ) label(Mγ) = ε´o label(Mγ) = ⊥ 33 DLAdjsubs buLCi= [> → Rβ•, i, j, false] [> → Rα•, j, k, false] [Qγ→Mγ•ν, i, k, false] β∈ladj(Qγ) α∈subst(Mγ) DLAdjn buLCi= [> → Rβ•, i, j, false] [Oγ→δ•, j, k, radj] [Qγ→Oγ•ν, i, k, false] donde se debe cumplir: (i) β∈ladj(Qγ), (ii) si radj =false entonces nil ∈radj(Oγ). DScan buLCi= [a, j, j + 1] [Nγ→Pγδ•Mγν, i, j, false] [Nγ→PγδMγ•ν, i, j + 1, false]label(Mγ) = a Dε buLCi=[Nγ→Pγδ•Mγν, i, j, false] [Nγ→PγδMγ•ν, i, j, false]label(Mγ) = ε´o label(Mγ) = ⊥ DComp buLCi= [Mγ→ν•, j, k, radj] [Nγ→Pγδ•Mγν, i, j, false] [Nγ→PγδMγ•ν, i, k, false] donde se debe cumplir que si radj =false entonces nil ∈radj(Mγ). El paso de compleci´on de adjunci´on derecha es igual a su hom´onimo del esquema buEk: DRAdj buLCi=DRAdj buEk DSubs buLCi= [> → Rα•, j, k, false] [Nγ→Pγδ•Mγν, i, j, false] [Nγ→PγδMγ•ν, i, k, false]α∈subst(Mγ) La eliminaci´on del dominio de un determinado tipo de ´ıtems provoca que tengamos que reescribir el paso DIni buEk, obteniendo los pasos DLCt buLCi,DLCε buLCi, DLCsubs buLCiyDLCn buLCi, que se aplican cuando el s´ımbolo que est´a a la izquierda de la regla (la esquina izquierda) es un terminal, la cadena vac´ıa, un nodo de sustituci´on o un no terminal, respectivamente. Actuamos de forma an´aloga 34 con la regla DLAdj buEkpara obtener las cuatros reglas: DLAdjt buLCi,DLAdjε buLCi,DLAdjsubs buLCi yDLAdjn buLCien este esquema. El resto de pasos funcionan de forma an´aloga a sus hom´onimos en el esquema buEk, pero los pasos DScan buLCi,Dε buLCiyDSubs buLCi s´olo se aplican a nodos que no son hijos izquierdos. El conjunto de items finales es id´entico al del esquema buEk: FbuLCi=FbuEk 9 La relaci´on esquina izquierda en las TIGs En las siguientes secciones vamos a definir esquemas que usan una extensi´on del concepto de relaci´on de esquina izquierda (LC), conocido sobre las CFGs, para filtrar las predicciones en el analizador basado en el algoritmo de Earley para TIGs. La complejidad temporal de todos estos algoritmos se mantienen en la cota de O(n3), pero mejoran sus prestaciones mediante una reducci´on en el tama˜no del chart. Antes de describir los nuevos analizadores necesitamos definir el concepto de relaci´on de esquina izquierda en las TIGs. Definici´on 9.1 Relaci´on de esquina izquierda (LC) en los ´arboles elementales de TIGs La esquina izquierda de un nodo Oγes su hijo izquierdo Pγsi y s´olo si ladj(Pγ) = {nil}. La relaci´on esquina izquierda >`en VN×{VN∪VT∪{ε, ⊥}} se define como Oγ>`Pγsi hay una producci´on Oγ→Pγν∈ P(γ)yladj(Pγ) = {nil}. La clausura reflexiva y transitiva de >`la denotaremos como >∗ `. En un abuso de notaci´on, vamos a denotar como Pγ>`4si hay una producci´on Oγ→Pγν∈ P(γ) y existe un βtal que β∈ladj(Pγ). La relaci´on LC en las TIGs no va m´as all´a de los l´ımites de un ´arbol elemental. Es importante se˜nalar que toda relaci´on de LC en las TIGs comienza en un nodo etiquetado con un s´ımbolo no terminal y finaliza en: (1) un nodo adjuntable por la izquierda; (2) un nodo etiquetado con un s´ımbolo terminal , εo⊥; (3) ´o un nodo marcado para sustituci´on. Las diferencias de esta definici´on respecto a la que presentamos para TAGs en [3] son fundamentalmente dos: •Al introducir la operaci´on de adjunci´on, en las fronteras de los ´arboles elementales de las TIGs pueden aparecer nodos etiquetados con s´ımbolos no terminales marcados para sustituci´on. ´ Esto nos obliga a introducir este caso como una posibilidad de finalizaci´on en las relaciones LC. 35 •En las TIGs distinguimos dos tipos de adjunciones: izquierda y derecha. Las segundas no afectan a las relaciones de esquina izquierda, puesto que s´olo introducen contextos derechos en los sub´arboles. Sin embargo, las primeras si rompen las relaciones LC. Por esta causa ´unicamente tenemos en cuenta los nodos adjuntables por la izquierda como fin de una relaci´on LC. 10 Un esquema LC con items predictivos Este esquema, denominado pLCiy presentado en [4], se obtiene reemplazando los pasos predictivos en el esquema Earleyipor objetivos que se intentan satisfacer de forma ascendente. La fase ascendente del proceso de reconocimiento es guiada hacia el correspondiente objetivo mediante la relaci´on LC. Por tanto, en el dominio del esquema pLCivamos a distinguir dos tipos de items: predictivos y left corner, cuya sem´antica es similar a la de los items de la misma denominaci´on en el esquema pLC para TAGs [3]. El conjunto de items de pLCise define mediante: IpLCi=I(i) pLCi∪ I(ii) pLCi∪ I(iii) pLCi∪ I(iv) pLCi El conjunto de items predictivos es: I(i) pLCi={[Mγ, j]|γ∈I∪A, 0 ≤j} Y el conjunto de items left corner viene definido por los tres siguientes subconjuntos: I(ii) pLCi={[Cγ;Mγ→Pγδ•ν, i, j, false]|Cγ>∗ `Mγ,Mγ→Pγδν ∈ P(γ) , γ∈I∪A, 0 ≤i≤j,ν6=ε} I(iii) pLCi={[Cγ;Mγ→ν•, i, j, radj]|Cγ>∗ `Mγ,Mγ→ν∈ P(γ) , γ∈I∪A, 0 ≤i≤j,radj ∈ {true, false}} donde radj =false si no se complet´o ninguna adjunci´on derecha sobre Mγ yradj =true si se complet´o una adjunci´on derecha sobre Mγ. I(iv) pLCi={[Cγ;Mγ→ •Pγν, j, j, false]|Cγ>∗ `Mγ,Mγ→Pγν∈ P(γ) , γ∈I∪A, 0 ≤i≤j} 36 donde Pγ>`4´o existe un αtal que α∈subst(Pγ). Es decir, el punto s´olo aparece al comienzo de la regla cuando el hijo izquierdo sea un nodo adjuntable por la izquierda o un nodo de sustituci´on, con objeto de lanzar el reconocimiento del ´arbol auxiliar izquierdo ´o del ´arbol inicial, respectivamente. Con respecto al conjunto de pasos deductivos, definimos subconjuntos para reconocimiento ycompleci´on similares a los del esquema Earleyi para TIGs. La relaci´on de esquina izquierda se aplicar´a a cinco casos de predicci´on: inicial, sub´arbol, pie, adjunci´on izquierda y adjunci´on derecha. Obs´ervese que aparece un filtro sobre la predicciones del pie, aunque este tipo de predicci´on aparentemente no aparece en el esquema Earleyi. Sin embargo, si nos fijamos con atenci´on el paso de compleci´on de adjunci´on izquierda DRAdjComp Earleyihace una doble funci´on: completa la adjunci´on izquierda e inicia el reconocimiento del sub´arbol escindido. Por ello podemos aplicar un filtro sobre esta predicci´on de pie. Los pasos de esquina izquierda vienen en tres variedades, seg´un el tipo de nodo en que finalice la relaci´on: terminal, cadena vac´ıa ´o nodo bottom, y no terminal. Los nodos etiquetados con εy⊥se incluyen en el mismo caso porque los nodos ⊥en las TIGs se comportan igual que una cadena vac´ıa, debido que no subsumen nada. El ´ultimo caso es necesario cuando la esquina izquierda es un nodo de adjunci´on izquierda o est´a marcado para sustituci´on. Los pasos deductivos del esquema son: DpLCi=DLIt pLCi∪ DLIε pLCi∪ DLIpre pLCi∪ DScan pLCi∪ Dε pLCi∪ DLCt pLCi∪ DLCε pLCi∪ DLCpre pLCi∪ DLCn pLCi∪ DPre pLCi∪ DComp pLCi∪ DLAt pLCi∪ DLAε pLCi∪ DLApre pLCi∪ DLFt pLCi∪ DLFε pLCi∪ DLFpre pLCi∪ DRAε pLCi∪ DRAdjComp pLCi∪ DLSt pLCi∪ DLSε pLCi∪ DLSpre pLCi∪ DSubsComp pLCi Filtrado de inicio DLIt pLCi=[a, 0,1] [>;Oα→Pα•ν, 0,1, false] α∈I label(Rα) = S label(Pα) = a DLIε pLCi=[>;Oα→Pα•ν, 0,0, false] α∈I label(Rα) = S label(Pα) = ε 37 DLIpre pLCi=[>;Oα→ •Pαν, 0,0, false] α∈I label(Rα) = S Pα>`4´o ∃α0∈subst(Pα) En el paso DLIε pLCino incluimos la condici´on label(Pα) = ⊥porque este paso se aplica exclusivamente a ´arboles iniciales. Reconocimiento Los pasos de reconocimiento son similares a los del esquema Earleyipero s´olo se aplican a nodos que no son hijos izquierdos. DScan pLCi= [a, j, j + 1] [Cγ;Nγ→Pγδ•Mγν, i, j, false] [Cγ;Nγ→PγδMγ•ν, i, j + 1, false]label(Mγ) = a Dε pLCi=[Cγ;Nγ→Pγδ•Mγν, i, j, false] [Cγ;Nγ→PγδMγ•ν, i, j, false]label(Mγ) = ε Filtrado de predicci´on de sub´arbol DLCt pLCi= [Mγ, j] [a, j, j + 1] [Mγ;Oγ→Pγ•ν, j, j + 1, false] nil ∈ladj(Mγ) label(Pγ) = a DLCε pLCi=[Mγ, j] [Mγ;Oγ→Pγ•ν, j, j, false] nil ∈ladj(Mγ) label(Pγ) = ε´o label(Pγ) = ⊥ DLCpre pLCi=[Mγ, j] [Mγ;Oγ→ •Pγν, j, j, false] nil ∈ladj(Mγ) Pγ>`4´o ∃α∈subst(Pγ) Compleci´on en la esquina izquierda El paso DLCn pLCies el que lleva a cabo las compleciones en los nodos que han sido filtrados por una relaci´on LC. DLCn pLCi=[Mγ;Oγ→ν•, j, k, radj] [Mγ;Qγ→Oγ•ω, j, k, false]Mγ6=Oγ donde se debe cumplir que si radj =false entonces nil ∈radj(Oγ). 38 Predicci´on Este paso realiza la predicci´on de los nodos que dominan relaciones LC, excepto los nodos ra´ıces de los ´arboles elementales. DPre pLCi=[Cγ;Nγ→δ•Mγν, i, j, false] [Mγ, j]label(Mγ)∈VN Compleci´on de sub´arbol DComp pLCi= [Mγ;Mγ→ν•, j, k, radj] [Cγ;Nγ→δ•Mγν, i, j, false] [Cγ;Nγ→δMγ•ν, i, k, false] donde se debe cumplir que si radj =false entonces nil ∈radj(Oγ). Filtrado de predicci´on de adjunci´on izquierda DLAt pLCi= [Mγ, j] [a, j, j + 1] [>;Oβ→Pβ•ν, j, j + 1, false] β∈ladj(Mγ) label(Pβ) = a DLAε pLCi=[Mγ, j] [>;Oβ→Pβ•ν, j, j, false] β∈ladj(Mγ) label(Pβ) = ε DLApre pLCi=[Mγ, j] [>;Oβ→ •Pβν, j, j, false] β∈ladj(Mγ) Pβ>`4´o ∃α∈subst(Pγ) En el paso DLAε pLCino incluimos la condici´on label(Pβ) = ⊥porque en un ´arbol auxiliar izquierdo no se puede dar el caso >>∗ `⊥. Filtrado de predicci´on de pie Este conjunto de pasos son el resultado de aplicar un filtro LC al paso DLAdjComp Earleyi, el cual, como dijimos antes, cumple una funci´on de predicci´on de pie. DLFt pLCi= [a, k, k + 1] [>;> → Rβ•, j, k, false] [Mγ, j] [Mγ;Oγ→Pγ•ν, k, k + 1, false] β∈ladj(Mγ) label(Pγ) = a 39 DLFε pLCi= [>;> → Rβ•, j, k, false] [Mγ, j] [Mγ;Oγ→Pγ•ν, k, k, false] β∈ladj(Mγ) label(Pγ) = ε´o label(Pγ) = ⊥ DLFpre pLCi= [>;> → Rβ•, j, k, false] [Mγ, j] [Mγ;Oγ→Pγ•ν, k, k, false] β∈ladj(Mγ) Pγ>`4´o ∃α∈subst(Pγ) Filtrado de predicci´on de adjunci´on derecha Teniendo en cuenta que los ´arboles auxiliares derechos se caracterizan porque a la izquierda de la espina no se pueden adjuntar ´arboles auxiliares izquierdos y en esa parte de su frontera s´olo pueden aparecer nodos etiquetados con ε, ´esto reduce la finalizaci´on del filtro LC sobre la ra´ıces de los ´arboles auxiliares derechos a un solo caso: ε´o ⊥. DRAε pLCi=[Cγ;Mγ→δ•, k, l, false] [>;Oβ→Pβ•ν, l, l, false] β∈radj(Mγ) label(Pβ) = ε´o label(Pβ) = ⊥ Compleci´on de adjunci´on derecha DRAdjComp pLCi= [>;> → Rβ•, j, k, false] [Cγ;Mγ→ν•, i, j, false] [Mγ→ν•, i, k, true]β∈radj(Mγ) Filtrado de predicci´on de sustituci´on DLSt pLCi= [Mγ, j] [a, j, j + 1] [>;Oα→Pα•ν, j, j + 1, false] α∈subst(Mγ) label(Pα) = a DLSε pLCi=[Mγ, j] [>;Oα→Pα•ν, j, j, false] α∈subst(Mγ) label(Pα) = ε DLSpre pLCi=[Mγ, j] [>;Oα→ •Pαν, j, j, false] α∈subst(Mγ) Pα>`4 40 Compleci´on de sustituci´on DSubsComp pLCi= [>;> → Rα•, j, k, false] [Cγ;Nγ→δ•Mγν, i, j, false] [Cγ;Nγ→δMγ•ν, i, k, false]α∈subst(Mγ) El conjunto de items finales del esquema se define mediante: FpLCi={[>;> → Rα•,0, n, false]|α∈I, label(Rα) = S} 11 Un esquema LC con items simplificados Vamos a derivar un nuevo esquema, al que denominaremos sLCi, simplificando los items del esquema pLCide forma similar a como derivamos el esquema sLC para TAGs en [3]. Es decir, al conjunto de items left corner de pLCiles eliminamos la parte predictiva y los convertimos en items Earley en el esquema sLCi. Evidentemente, esta modificaci´on del dominio conlleva una adaptaci´on del conjunto de pasos deductivos. El dominio del esquema sLCipresenta dos tipos de items: predictivos y Earley. Y se define de la siguiente manera: IsLCi=I(i) sLCi∪ I(ii) sLCi∪ I(iii) sLCi∪ I(iv) sLCi El conjunto de items predictivos es igual al del esquema anterior: I(i) sLCi=I(i) pLCi El conjunto de items Earley es similar al del esquema Earleyi, pero cierto tipo de items con el punto al comienzo de las reglas son filtrados del dominio. Dicho conjunto viene definido por los siguientes subconjuntos: I(ii) sLCi={[Mγ→Pγδ•ν, i, j, false]|Mγ→Pγδν ∈ P(γ) , γ∈I∪A, 0 ≤i≤j,ν6=ε} I(iii) sLCi={[Mγ→ν•, i, j, radj]|Mγ→ν∈ P(γ) , γ∈I∪A, 0 ≤i≤j,radj ∈ {true, false}} donde radj =false si no se complet´o ninguna adjunci´on derecha sobre Mγ yradj =true si se complet´o una adjunci´on derecha sobre Mγ. 41 Filtrado de predicci´on de adjunci´on derecha Este paso deductivo es igual a su hom´onimo del esquema sLCi: DRAε LCi=DRAε sLCi Compleci´on de adjunci´on derecha Este paso deductivo es igual a su hom´onimo del esquema sLCi: DRAdjComp LCi=DRAdjComp sLCi Filtrado de predicci´on de sustituci´on DLSt LCi= [Nγ→δ•Mγω, i, j, false] [a, j, j + 1] [Oα→Pα•ν, j, j + 1, false] >>∗ `Oα α∈subst(Mγ) label(Pα) = a DLSε LCi=[Nγ→δ•Mγω, i, j, false] [Oα→Pα•ν, j, j, false] >>∗ `Oα α∈subst(Mγ) label(Pα) = ε DLSpre LCi=[Nγ→δ•Mγω, i, j, false] [Oα→ •Pαν, j, j, false] >>∗ `Oα α∈subst(Mγ) Pα>`4 Compleci´on de sustituci´on Este paso deductivo es igual a su hom´onimo del esquema sLCi: DSubsComp LCi=DSubsComp sLCi El conjunto de items finales es igual al del esquema sLCi: FLCi=FsLCi 48 13 Relaciones entre esquemas Teorema 13.1 Relaci´on entre los esquemas pLCi,sLCiyLCi Se mantienen las siguientes relaciones de refinamiento de pasos e items: LC sr =⇒sLCiir =⇒pLCi Prueba Primero vamos a probar la relaci´on sLCiir =⇒pLCi. Debemos probar que existe una funci´on regular f:IpLCi→ IsLCital que: 1. IsLCi=f(IpLCi) 2. 4sLCi=f(4pLCi) Dada la funci´on regular: f([Cγ;Nγ→δ•ν, i, j |p, q]) = [Nγ→δ•ν, i, j |p, q] f([Cγ, j]) = [Cγ, j] se sigue inmediatamente que IsLCi=f(IpLCi)y4sLCi=f(4pLCi)por inducci´on en la longitud de las secuencias de derivaci´on. Ahora probaremos la relaci´on LCisr =⇒sLCi. Para ello tenemos que demostrar que: 1. ILCi⊆ IsLCi 2. `∗ LCi⊆`∗ sLCi Lo primero es cierto por definici´on, ya que el dominio del esquema LCi est´a formado por los conjuntos de items de tipo Earley del esquema sLCi: ILCi⊂ IsLCi Para demostrar que `∗ LCi⊆`∗ sLCihay que probar que DLCi⊆`∗ sLCi. Veamos cada paso: •Un paso deductivo DLCt LCies equivalente a la secuencia formada por un paso DPre sLCi [Nγ→δ•Mγν, i, j, false] [Mγ, j] seguido de otro DLCt sLCi [Mγ, j] [a, j, j + 1] [Oγ→Pγ•ν, j, j + 1, false] 49 •Un paso deductivo DLCε LCies equivalente a la secuencia formada por un paso DPre sLCi [Nγ→δ•Mγν, i, j, false] [Mγ, j] seguido de otro DLCε sLCi [Mγ, j] [Oγ→Pγ•ν, j, j, false] •Un paso deductivo DLCpre LCies equivalente a la secuencia formada por un paso DPre sLCi [Nγ→δ•Mγν, i, j, false] [Mγ, j] seguido de otro DLCpre sLCi [Mγ, j] [Oγ→ •Pγν, j, j, false] •Un paso deductivo DLAt LCies equivalente a la secuencia formada por un paso DPre sLCi [Nγ→δ•Mγν, i, j, false] [Mγ, j] seguido de otro DLAt sLCi [Mγ, j] [a, j, j + 1] [Oβ→Pβ•ν, j, j + 1, false] •Un paso deductivo DLAε LCies equivalente a la secuencia formada por un paso DPre sLCi [Nγ→δ•Mγν, i, j, false] [Mγ, j] seguido de otro DLAε sLCi [Mγ, j] [Oβ→Pβ•ν, j, j, false] 50 •Un paso deductivo DLApre LCies equivalente a la secuencia formada por un paso DPre sLCi [Nγ→δ•Mγν, i, j, false] [Mγ, j] seguido de otro DLApre sLCi [Mγ, j] [Oβ→ •Pβν, j, j, false] •Un paso deductivo DLFt LCies equivalente a la secuencia formada por un paso DPre sLCi [Nγ→δ•Mγν, i, j, false] [Mγ, j] seguido de otro DLFt sLCi [a, k, k + 1] [> → Rβ•, j, k, false] [Mγ, j] [Oγ→Pγ•ν, k, k + 1, false] •Un paso deductivo DLFε LCies equivalente a la secuencia formada por un paso DPre sLCi [Nγ→δ•Mγν, i, j, false] [Mγ, j] seguido de otro DLFε sLCi [> → Rβ•, j, k, false] [Mγ, j] [Oγ→Pγ•ν, k, k, false] •Un paso deductivo DLFpre LCies equivalente a la secuencia formada por un paso DPre sLCi [Nγ→δ•Mγν, i, j, false] [Mγ, j] seguido de otro DLFpre sLCi [> → Rβ•, j, k, false] [Mγ, j] [Oγ→ •Pγν, k, k, false] 51 •Un paso deductivo DLSt LCies equivalente a la secuencia formada por un paso DPre sLCi [Nγ→δ•Mγν, i, j, false] [Mγ, j] seguido de otro DLSt sLCi [Mγ, j] [a, j, j + 1] [Oα→Pα•ν, j, j + 1, false] •Un paso deductivo DLSε LCies equivalente a la secuencia formada por un paso DPre sLCi [Nγ→δ•Mγν, i, j, false] [Mγ, j] seguido de otro DLSε sLCi [Mγ, j] [Oα→Pα•ν, j, j, false] •Un paso deductivo DLSpre LCies equivalente a la secuencia formada por un paso DPre sLCi [Nγ→δ•Mγν, i, j, false] [Mγ, j] seguido de otro DLSpre sLCi [Mγ, j] [Oα→ •Pαν, j, j, false] •El resto de pasos hom´onimos en ambos esquemas son iguales. Teorema 13.2 Relaci´on entre los esquemas buLCiyLCi Se mantiene la siguientes relaciones de refinamiento de pasos y filtros din´amicos: buLCisr =⇒buLCi 1 df =⇒LCi 1 df ⇐=LCi Prueba El esquema buLCi 1se obtiene mediante la ampliaci´on del dominio de buLCi con items con el punto al comienzo de la regla cuando el hijo izquierdo sea 52 un nodo adjuntable o marcado para sustituci´on. Por tanto, el conjunto de items para este esquema es igual al del esquema LCi: IbuLCi 1=ILCi Hay que adaptar el conjunto de pasos deductivos al nuevo dominio: DbuLCi 1=DLCt buLCi 1 ∪DLCε buLCi 1 ∪DLCpre buLCi 1 ∪DLCn buLCi 1 ∪DLAdjt buLCi 1 ∪DLAdjε buLCi 1 ∪DLAdjpre buLCi 1 ∪ DLAdjn buLCi 1 ∪ Dε buLCi 1∪ DScan buLCi 1∪ DComp buLCi 1 ∪ DRAdj buLCi 1 ∪ DSubs buLCi 1 donde todos los pasos son id´enticos al los hom´onimos de buLCi, excepto el paso DSubs buLCi 1 y los nuevos pasos DLCpre buLCi 1 yDLAdjpre buLCi 1 . DLCt buLCi 1 =DLCt buLCi DLCε buLCi 1 =DLCε buLCi DLCn buLCi 1 =DLCn buLCi DLAdjt buLCi 1 =DLAdjt buLCi DLAdjε buLCi 1 =DLAdjε buLCi DLAdjn buLCi 1 =DLAdjn buLCi DScan buLCi 1=DScan buLCi Dε buLCi 1=Dε buLCi DComp buLCi 1 =DComp buLCi DRAdj buLCi 1 =DRAdj buLCi DLCpre buLCi 1 =[Oγ→ •Pγν, j, j, false] nil ∈ladj(Oγ) Pγ>`4´o ∃α∈subst(Pγ) DLAdjpre buLCi 1 =[> → Rβ•, i, j, false] [Oγ→ •Pγν, j, j, false] β∈ladj(Oγ) Pγ>`4´o ∃α∈subst(Pγ) DSubs buLCi 1= [> → Rα•, j, k, false] [Nγ→δ•Mγν, i, j, false] [Nγ→δMγ•ν, i, k, false]α∈subst(Mγ) 53 El conjunto de items finales es igual al del esquema buLCi: FbuLCi 1=FbuLCi Probemos ahora que buLCisr =⇒buLCi 1, para lo cual se tiene que cumplir que: 1. IbuLCi⊆ IbuLCi 1 2. `∗ buLCi⊆`∗ buLCi 1 Lo primero es cierto por definici´on, ya que el dominio del esquema buLCi 1est´a formado por los items del esquema buLCiampliado con items con el punto a comienzo de la regla. Por tanto: IbuLCi⊂ IbuLCi 1 Para demostrar que `∗ buLCi⊆`∗ buLCi 1 nos basta con probar que DbuLCi⊆`∗ buLCi 1 . Veamos ´unicamente los pasos en que difieren: •Un paso deductivo DLCsubs buLCies equivalente a una secuencia formada por una paso DLCpre buLCi 1 [Oγ→ •Pγν, j, j, false] seguido de otro DSubs buLCi 1 [> → Rα•, j, k, false] [Oγ→ •Pγν, j, j, false] [Oγ→Pγ•ν, j, k, false] •Un paso deductivo DLAdjsubs buLCies equivalente a una secuencia formada por una paso DLAdjpre buLCi 1 [> → Rβ•, i, j, false] [Oγ→ •Pγν, j, j, false] seguido de otro DSubs buLCi 1 [> → Rα•, j, k, false] [Oγ→ •Pγν, j, j, false] [Oγ→Pγ•ν, j, k, false] 54 •Un paso deductivo DSubs buLCiest´a incluido en la inferencia del paso DSubs buLCi 1 , ya que este ´ultimo contempla la operaci´on de sustituci´on en cualquier posici´on, mientras el primero s´olo es v´alido para sustituciones en nodos que no sean hijos izquierdos. Por tanto: DSubs buLCi⊂ DSubs buLCi 1 El esquema LCi 1se obtiene desdoblando el paso DComp LCidel esquema LCi en los pasos DComp1 LCi 1 yDComp2 LCi 1 , donde el primero se encarga de completar los sub´arboles en nodos que no son hijos izquierdos, mientras el segundo las completan en los hijos izquierdos. El dominio de LCi 1es igual al del esquema original: ILCi 1=ILCi El conjunto de pasos deductivos del nuevo esquema es: DLCi 1=DLIt LCi 1 ∪ DLIε LCi 1 ∪ DLIpre LCi 1 ∪ DScan LCi 1∪ Dε LCi 1∪ DLCt LCi 1 ∪ DLCε LCi 1 ∪ DLCpre LCi 1 ∪ DLCn LCi 1 ∪ DComp1 LCi 1 ∪ DComp2 LCi 1 ∪ DLAt LCi 1 ∪ DLAε LCi 1 ∪ DLApre LCi 1 ∪ DLFt LCi 1 ∪ DLFε LCi 1 ∪ DLFpre LCi 1 ∪ DRAε LCi 1 ∪ DRAdjComp LCi 1 ∪ DLSt LCi 1 ∪ DLSε LCi 1 ∪ DLSpre LCi 1 ∪ DSubsComp LCi 1 donde todos los pasos deductivos son iguales a sus hom´onimos del esquema LCi, excepto los dos nuevos obtenidos mediante el desdoble. DLIt LCi 1 =DLIt LCi DLIε LCi 1 =DLIε LCi DLIpre LCi 1 =DLIpre LCi DScan LCi 1=DScan LCi Dε LCi 1=Dε LCi DLCt LCi 1 =DLCt LCi DLCε LCi 1 =DLCε LCi 55 DLCpre LCi 1 =DLCpre LCi DLCn LCi 1 =DLCn LCi DLAt LCi 1 =DLAt LCi DLAε LCi 1 =DLAε LCi DLApre LCi 1 =DLApre LCi DLFt LCi 1 =DLFt LCi DLFε LCi 1 =DLFε LCi DLFpre LCi 1 =DLFpre LCi DRAε LCi 1 =DRaε LCi DRAdjComp LCi 1 =DRAdjComp LCi DLSt LCi 1 =DLSt LCi DLSε LCi 1 =DLSε LCi DLSpre LCi 1 =DLSpre LCi DSubsComp LCi 1 =DSubsComp LCi DComp1 LCi 1 = [Mγ→ν•, j, k, radj] [Nγ→Pγδ•Mγω, i, j, false] [Nγ→PγδMγ•ν, i, k, false] donde se debe cumplir que si radj =false entonces nil ∈radj(Oγ). DComp2 LCi 1 = [Mγ→ν•, j, k, radj] [Nγ→ •Mγω, j, j, false] [Nγ→Mγ•ν, j, k, false] donde se debe cumplir que si radj =false entonces nil ∈radj(Oγ). El conjunto de items finales tambi´en es igual al del esquema LCi: ILCi 1=ILCi Para probar que LCidf =⇒LCi 1tenemos que demostrar que: 56 1. ILCi 1⊆ ILCi 2. `LCi 1⊆`LCi Lo primero es cierto por definici´on, ya que los dominios de ambos esquemas son iguales: ILCi 1=ILCi Para probar que `LCi 1⊆`LCidebemos demostrar que DLCi 1 ⊆`LCi. S´olo vamos a considerar los dos pasos sobre los que se aplica el filtro din´amico, el resto son id´enticos: •Dado un paso [Mγ→ν•, j, k, radj] [Nγ→Pγδ•Mγω, i, j, false] [Nγ→PγδMγ•ν, i, k, false]∈ DComp1 LCi 1 existe un paso [Mγ→ν•, j, k, radj] [Nγ→δ•Mγω, i, j, false] [Nγ→δMγ•ν, i, k, false]∈ DComp LCi y, por tanto, existe la inferencia [Mγ→ν•, j, k, radj] [Nγ→Pγδ•Mγω, i, j, false]`LCi[Nγ→PγδMγ•ν, i, k, false] •Dado un paso [Mγ→ν•, j, k, radj] [Nγ→ •Mγω, j, j, false] [Nγ→Mγ•ν, j, k, false]∈ DComp2 LCi 1 existe un paso [Mγ→ν•, j, k, radj] [Nγ→δ•Mγω, i, j, false] [Nγ→δMγ•ν, i, k, false]∈ DComp LCi y, por tanto, existe la inferencia [Mγ→ν•, j, k, radj] [Nγ→ •Mγω, j, j, false]`LCi[Nγ→Mγ•ν, j, k, false] 57 Teorema 13.3 Relaci´on entre los esquemas buEkybuLCi Se mantiene la siguiente relaci´on de contracci´on de secuencias deductivas: buEksc =⇒buLCi Prueba Tenemos que demostrar que: 1. IbuLCi⊆ IbuEk 2. `∗ buLCi⊆`∗ buEk Lo primero es cierto por definici´on, ya que el dominio del esquema buLCies igual al del esquema buEkal que le hemos suprimido los items con el punto al comienzo de la regla: IbuLCi⊂ IbuEk Para probar que `∗ buLCi⊆`∗ buEkdebemos demostrar que DbuLCi⊆`∗ buEk. Veamos cada uno de los pasos: •Un paso deductivo DLCt buLCies equivalente a la secuencia formada por un paso DIni buEk [Oγ→ •Pγν, j, j, false] seguido de otro DScan buEk [a, j, j + 1] [Oγ→ •Pγν, j, j, false] [Oγ→δPγ•ν, j, j + 1, false] •Un paso deductivo DLCε buLCies equivalente a la secuencia formada por un paso DIni buEk [Oγ→ •Pγν, j, j, false] seguido de otro Dε buEk [Oγ→ •Pγν, j, j, false] [Oγ→Pγ•ν, j, j, false] 64 •Un paso deductivo DLCsubs buLCies equivalente a la secuencia formada por un paso DIni buEk [Oγ→ •Pγν, j, j, false] seguido de otro DSubs buEk [> → Rα•, j, k, false] [Oγ→ •Pγν, j, j, false] [Oγ→Pγ•ν, j, k, false] •Un paso deductivo DLCn buLCies equivalente a la secuencia formada por un paso DIni buEk [Qγ→ •Oγω, j, j, false] seguido de otro DComp buEk [Oγ→ν•, j, k, radj] [Qγ→ •Oγω, j, j, false] [Qγ→Oγ•ω, j, k, false] •Un paso deductivo DLAdjt buLCies equivalente a la secuencia formada por un paso DLAdj buEk [> → Rβ•, i, j, false] [Oγ→ •Pγν, i, j, false] seguido de otro DScan buEk [a, j, j + 1] [Oγ→ •Pγν, i, j, false] [Oγ→δPγ•ν, i, j + 1, false] •Un paso deductivo DLAdjε buLCies equivalente a la secuencia formada por un paso DLAdj buEk [> → Rβ•, i, j, false] [Oγ→ •Pγν, i, j, false] seguido de otro Dε buEk [Oγ→ •Pγν, i, j, false] [Oγ→Pγ•ν, i, j, false] 65 •Un paso deductivo DLAdjsubs buLCies equivalente a la secuencia formada por un paso DLAdj buEk [> → Rβ•, i, j, false] [Oγ→ •Pγν, i, j, false] seguido de otro DSubs buEk [> → Rα•, j, k, false] [Oγ→ •Pγν, i, j, false] [Oγ→Pγ•ν, i, k, false] •Un paso deductivo DLAdjn buLCies equivalente a la secuencia formada por un paso DLAdj buEk [> → Rβ•, i, j, false] [Qγ→ •Oγν, i, j, false] seguido de otro DComp buEk [Oγ→ν•, j, k, radj] [Qγ→ •Oγω, i, j, false] [Qγ→Oγ•ω, i, k, false] •El resto de pasos deductivos del esquema buLCiest´an incluidos en las inferencias de sus hom´onimos del esquema buEk, ya que estos ´ultimos contemplan las operaciones en cualquier posici´on, mientras que los pertenecientes a buLCis´olo son aplicables en nodos que no sean hijos izquierdos. Por tanto, se cumple: DScan buLCi⊂ DScan buEk Dε buLCi⊂ Dε buEk DComp buLCi⊂ DComp buEk DSubs buLCi⊂ DSubs buEk Teorema 13.4 Relaci´on entre los esquemas EarleyiyLCi Se mantiene la siguiente relaci´on de contracci´on de secuencias deductivas: Earleyisc =⇒LCi Prueba Tenemos que demostrar que: 66 1. ILCi⊆ IEarleyi 2. `∗ LCi⊆`∗ Earleyi Lo primero es cierto por definici´on, ya que el dominio del esquema LCi es igual al del esquema Earleyial que le hemos suprimido un subconjunto de los items con el punto al comienzo de la regla: ILCi⊂ IEarleyi Para probar que `∗ LCi⊆`∗ Earleyidebemos demostrar que DLCi⊆`∗ Earleyi. Veamos cada uno de los pasos: •Un paso DLIt LCies equivalente a la secuencia formada por un paso DIni Earleyi [> → •Rα,0,0, false] seguido de una secuencia de pasos DPred Earleyi [> → •Rα,0,0, false] [Rα→ •Mγν, 0,0, false] [Mγ→ •Oγν, 0,0, false] [Oγ→ •Pγδ, 0,0, false] y de un paso DScan Earleyi [Oγ→ •Pγν, 0,0, false] [a, 0,1] [Oγ→Pγ•ν, 0,1, false] •Un paso DLIε LCies equivalente a la secuencia formada por un paso DIni Earleyi [> → •Rα,0,0, false] seguido de una secuencia de pasos DPred Earleyi [> → •Rα,0,0, false]] [Rα→ •Mγν, 0,0, false] [Mγ→ •Oγν, 0,0, false] [Oγ→ •Pγδ, 0,0, false] y de un paso Dε Earleyi [Oγ→ •Pγν, 0,0, false] [Oγ→Pγ•ν, 0,0, false] 67 •Un paso DLIpre LCies equivalente a la secuencia formada por un paso DIni Earleyi [> → •Rα,0,0, false] seguido de una secuencia de pasos DPred Earleyi [> → •Rα,0,0, false] [Rα→ •Mγν, 0,0, false] [Mγ→ •Oγν, 0,0, false] [Oγ→ •Pγδ, 0,0, false] •Un paso DLCt LCies equivalente a una secuencia de pasos DPred Earleyi [Nγ→δ•Mγν, i, j, false] [Mγ→ •Oγω, j, j, false] [Mγ→ •Oγω, j, j, false] [Oγ→ •Pγν, j, j, false] seguida de un paso DScan Earleyi [Oγ→ •Pγν, j, j, false] [a, j, j + 1] [Oγ→Pγ•ν, j, j + 1, false] •Un paso DLCε LCies equivalente a una secuencia de pasos DPred Earleyi [Nγ→δ•Mγν, i, j, false] [Mγ→ •Oγω, j, j, false] [Mγ→ •Oγω, j, j, false] [Oγ→ •Pγν, j, j, false] seguida de un paso Dε Earleyi [Oγ→ •Pγν, j, j, false] [Oγ→Pγ•ν, j, j, false] •Un paso DLCpre LCies equivalente a una secuencia de pasos DPred Earleyi: [Nγ→δ•Mγν, i, j, false] [Mγ→ •Oγω, j, j, false] [Mγ→ •Oγω, j, j, false] [Oγ→ •Pγν, j, j |, false] 68 •Un paso DLCn LCies equivalente a una secuencia de pasos DPred Earleyi [Nγ→δ•Mγν, i, j, false] [Mγ→ •Oγω, j, j, false] [Mγ→ •Oγω, j, j, false] [Oγ→ •Pγν, j, j, false] seguida de un paso DComp Earleyi [Pγ→δ•, j, k, radj] [Oγ→ •Pγν, j, j, false] [Oγ→Pγ•ν, j, k, false] •Un paso DLAt LCies equivalente a la secuencia formada por un paso DLAdjPred Earleyi [Nγ→δ•Mγν, i, j, false] [> → •Rβ, j, j, false] una secuencia de pasos DPred Earleyi [> → •Rβ, j, j, false] [Rβ→ •Mβω, j, j, false] [Mβ→ •Oβω, j, j, false] [Oβ→ •Pβν, j, j, false] y un paso DScan Earleyi [Oβ→ •Pβν, j, j, false], [a, j, j + 1] [Oβ→Pβ•ν, j, j + 1, false] •Un paso DLAε LCies equivalente a la secuencia formada por un paso DLAdjPred Earleyi [Nγ→δ•Mγν, i, j, false] [> → •Rβ, j, j, false] una secuencia de pasos DPred Earleyi [> → •Rβ, j, j, false] [Rβ→ •Mβω, j, j, false] 69 [Mβ→ •Oβω, j, j, false] [Oβ→ •Pβν, j, j, false] y un paso Dε Earleyi [Oβ→ •Pβν, j, j, false] [Oβ→Pβ•ν, j, j, false] •Un paso DLApre LCies equivalente a la secuencia formada por un paso DLAdjPred Earleyi [Nγ→δ•Mγν, i, j, false] [> → •Rβ, j, j, false] seguido de una secuencia de pasos DPred Earleyi [> → •Rβ, j, j, false] [Rβ→ •Mβω, j, j, false] [Mβ→ •Oβω, j, j, false] [Oβ→ •Pβν, j, j, false] •Un paso DLFt LCies equivalente a la secuencia formada por un paso DLAdjComp Earleyi [> → Rβ•, j, k, false] [Oγ→δ•Nγν, i, j, false] [Nγ→ •Mγν, j, k, false] una secuencia de pasos DPred Earleyi [Nγ→ •Mγν, k, k, false] [Mγ→ •Oγω, k, k, false] [Mγ→ •Oγω, k, k, false] [Oγ→ •Pγν, k, k, false] y un paso DScan Earleyi [Oγ→ •Pγν, k, k, false] [a, k, k + 1] [Oγ→Pγ•ν, k, k + 1, false] 70 •Un paso DLFε LCies equivalente a la secuencia formada por un paso DLAdjComp Earleyi [> → Rβ•, j, k, false] [Oγ→δ•Nγν, i, j, false] [Nγ→ •Mγν, j, k, false] una secuencia de pasos DPred Earleyi [Nγ→ •Mγν, k, k, false] [Mγ→ •Oγω, k, k, false] [Mγ→ •Oγω, k, k, false] [Oγ→ •Pγν, k, k, false] y un paso Dε Earleyi [Oγ→ •Pγν, k, k, false] [Oγ→Pγ•ν, k, k, false] •Un paso DLFpre LCies equivalente a la secuencia formada por un paso DLAdjComp Earleyi [> → Rβ•, j, k, false] [Oγ→δ•Nγν, i, j, false] [Nγ→ •Mγν, j, k, false] seguido de una secuencia de pasos DPred Earleyi [Nγ→ •Mγν, k, k, false] [Mγ→ •Oγω, k, k, false] [Mγ→ •Oγω, k, k, false] [Oγ→ •Pγν, k, k, false] •Un paso DRAε LCies equivalente a la secuencia formada por un paso DRAdjPred Earleyi [Nγ→δ•, i, j, false] [> → •Rβ, j, j, false] una secuencia de pasos DPred Earleyi [> → •Rβ, j, j, false] [Rβ→ •Mβω, j, j, false] 71 [Mβ→ •Oβω, j, j, false] [Oβ→ •Pβν, j, j, false] y un paso Dε Earleyi [Oβ→ •Pβν, j, j, false] [Oβ→Pβ•ν, j, j, false] •Un paso DLSt LCies equivalente a la secuencia formada por un paso DSubsPred Earleyi [Nγ→δ•Mγν, i, j, false] [> → •Rα, j, j, false] una secuencia de pasos DPred Earleyi [> → •Rα, j, j, false] [Rα→ •Mαω, j, j, false] [Mα→ •Oαω, j, j, false] [Oα→ •Pαν, j, j, false] y un paso DScan Earleyi [Oα→ •Pαν, j, j, false], [a, j, j + 1] [Oα→Pα•ν, j, j + 1, false] •Un paso DLSε LCies equivalente a la secuencia formada por un paso DSubsPred Earleyi [Nγ→δ•Mγν, i, j, false] [> → •Rα, j, j, false] una secuencia de pasos DPred Earleyi [> → •Rα, j, j, false] [Rα→ •Mαω, j, j, false] [Mα→ •Oαω, j, j, false] [Oα→ •Pαν, j, j, false] y un paso Dε Earleyi [Oα→ •Pαν, j, j, false] [Oα→Pα•ν, j, j, false] 72 •Un paso DLSpre LCies equivalente a la secuencia formada por un paso DSubsPred Earleyi [Nγ→δ•Mγν, i, j, false] [> → •Rα, j, j, false] seguido de una secuencia de pasos DPred Earleyi [> → •Rα, j, j, false] [Rα→ •Mαω, j, j, false] [Mα→ •Oαω, j, j, false] [Oα→ •Pαν, j, j, false] •Los pasos deductivos de reconocimiento del esquema LCiest´an incluidos en las inferencias de sus hom´onimos del esquema Earleyi, ya que estos ´ultimos contemplan las operaciones en cualquier posici´on, mientras que los pertenecientes a LCis´olo son aplicables en nodos que no sean hijos izquierdos. Por tanto, se cumple: DScan LCi⊂ DScan Earleyi Dε LCi⊂ Dε Earleyi •El resto de pasos son id´enticos en ambos esquemas: DComp LCi=DComp Earleyi DRAdjComp LCi=DRAdjComp Earleyi DSubsComp LCi=DSubsComp Earleyi Referencias [1] Alonso, M. A., ”Interpretaci´on tabular de aut´omatas para lenguajes de adjunci´on de ´arboles”, Tesis doctoral, Universidade da Coru˜na, Espa˜na, 2000. [2] Alonso, M. A., Cabrero, D. , de la Clergerie, E. y Vilares, M., ”Tabular algorithms for TAG parsing”, En Proc. of EACL’99, p´aginas 150–157, Bergen, Noruega, 1999. 73