Procesamiento del Lenguaje Natural

Actividad: Análisis sintáctico

Objetivos

Se pretende implementar el algoritmo CKY probabilístico y aplicarlo para realizar el análisis sintáctico automático de una oración.

Pautas de elaboración

La definición de la gramática que se utilizó para la presente actividad:

G= (T, N, R, S)

Conjunto de terminales: T= {time, flies, arrow, an, like}

Conjunto de no terminales: N= {S, NP, VP, PP, Det, Nominal, Verb, Preposition, Noun}

Conjunto de reglas:

 R={

S → NP VP                                0.800

NP → time | flies | arrow                0.002

NP → Det Nominal                        0.300

NP → Nominal Nominal                0.200

Nominal → time | flies | arrow        0.002

Nominal → Nominal Noun                0.100

Nominal → Nominal PP                0.200

VP → time                                0.004

VP → flies| like                        0.008

VP → Verb NP                                0.300

VP → Verb PP                                0.200

PP → Preposition NP                        0.100

Verb → time                                0.010

Verb → flies| like                        0.020

Noun → time | flies | arrow                0.010

Det → an                                0.050

Preposition → like                        0.050

}

Axioma de la gramática: S

Se debe realizar el análisis sintáctico de la frase:

«Time flies like an arrow».

Los pasos que se deben realizar en la actividad son:

• Paso 1. Implementar en Python la estructura de la matriz de análisis sintáctico (CKY).

La implementación de la matriz sintáctico, se utilizaron las siguientes estructuras de datos:

Se tienen entidades para mantener los datos en memoria, tales como la siguiente figura:

[pic 1]

Figura de Entidades

Las clases se explican en breve:

Hoja. Mantiene el mínimo de información, Sintagma y las coordenadas de la matriz de sintagamas donde se localiza.

Nodo. Contiene un par de hojas o clases que representan la intersección o coincidencia entre los datos o sintagmas

SintagmaP. Mantiene un sintagma y la probabilidad de ocurrencia, contiene el nodo inicial

Main, crea las estructuras de los datos con diccionarios, y listas. Crea una instancia del objeto AlgoritmoCYK, y realiza la orquestación de métodos para llenar la matriz con los datos de probabilidad sintáctica en forma de diagonal.

Tree. Clase de utilería para tratar de generar un grafo con los nodos

• Paso 2. Implementar en Python la representación de la gramática proporcionada.

La representación de la gramática se modeló con la ayuda de un diccionario, tuplas y arreglos, tal como se muestra a continuación:

R = {
   "S": [(["NP", "VP"],[0.800])],
   "NP": [
          (["time", "flies", "arrow"], [0.002]),
          (["Det", "Nominal"], [0.300]),
          (["Nominal","Nominal"], [0.200])],
   "Nominal": [(["time", "flies","arrow"], [0.002]),
               (["Nominal","Noun"],[0.100]),
               (["Nominal","PP"],[0.200])],
   "VP": [
           (["time"],[0.004]),
           (["flies","like"],[0.008]),
       (["Verb", "NP"],[0.300]),
       (["Verb", "PP"], [0.200])
   ],
   "PP": [
       (["Preposition", "NP"],[0.100])
   ],
   "Verb":[
       (["time"],[0.010]),
       (["flies", "like"], [0.020])
   ],
   "Noun": [
       (["time", "flies", "arrow"], [0.010])
   ],
   "Det": [(["an"],[0.050])],
   "Preposition":[(["like"], [0.050])]
}

...