Lingüística computacional (IX)

El capítulo anterior de esta serie puede verse aquí.


En los capítulos anteriores hemos visto muy sucintamente algunos aspectos teóricos de los formalismos gramaticales. Es ya momento de pasar a la práctica, es decir a estudiar programas concretos que sirven para analizar frases y determinar si están bien escritas o mal escritas, si son o no son válidas gramaticalmente.

Es evidente que si disponemos de un sistema correcto de análisis sintáctico, el escribir literatura sería bastante sencillo, al menos mala literatura. Bastaría programar un generador de frases aleatorias combinando palabras de un diccionario para, después, pasar estas sentencias por el analizador, filtrando sólo aquellas que estuviesen formadas correctamente. Podría pensarse que este sería un trabajo ingente y con pocas posibilidades de éxito pero si contemplamos que un ordenador rápido puede generar y comprobar un millón de oraciones por segundo es bastante probable que en unas horas de funcionamiento diéramos con un texto breve de calidad aparente.

Parsers

Un Parser es un programa informático que toma una frase y comprueba que está bien formada de acuerdo a una serie de reglas. Su origen está en los programas de ordenador y en los compiladores/intérpetes. En este ámbito tan restrictivo en el que sólo hay unos pocos cientos de palabras válidas y unas pocas combinaciones estructurales correctas, los parsers determinan si las instrucciones que el programador ha escrito son correctas antes de pasarlas al compilador o el intérprete que las traducirá al lenguaje máquina. Así, en BASIC, por ejemplo tenemos un lexicón formado por menos de cien palabras clave ( REM, GOTO, PRINT, WRITE, OPEN, CLOSE, IF, DO, NEXT,….). Sólo estás pueden usarse. Pero además hay una serie de reglas de buena formación de la instrucción que se da al ordenador. Por ejemplo, podremos escribir:

FOR x=1 to 6

Pero no podríamos escribir:

FOR x==1 to 6 ni tampoco FOR X=1 tor 6

Un parser analizaría la primera instrucción y la reconocería como correcta. Al analizar la segunda determinaría que su gramática es incorrecta porque hay dos “=” en vez de uno sólo. Y al estudiar la tercera, determinaría también que es falsa porque la palabra “tor” no está en el lexicón de BASIC.

Otras acciones que realizan los parsers de un lenguaje de programación es comprobar que los paréntesis están emparejados dos a dos. Por ejemplo, la sentencia :


X= (a*2)+ ((b+2)/3)

sería correcta, pero la

x=(a*2)+((b+2)/3

no lo sería.


Normalmente, estos programas ejecutan la tarea de análisis en tres fases. En la primera (lexical analysis) separan los componentes- las palabras- de la sentencia. Así, en la sentencia aritmética:


X= 5 + ((3/8)^3)

El parser separaría los componentes reconocibles en el lexicón (que suelen denominarse tokens):

5, +, (,(,3,/,8,),^,3,).

Si en esta fase aparece algún token que no esté en el lexicón, el programa abortaría el análisis dando un mensaje de error.

La segunda fase, llamada sintáctica, verifica que la sentencia es válida de acuerdo a las reglas. Aquí, el parser determinaría que lo es ya que los paréntesis están emparejados (dos de apertura, dos de cierre), etc.

Finalmente, la tercera fase- llamada semántica- es la que ejecuta las acciones necesarias para interpretar la sentencia. En este caso, esta serie de cálculos:

- Resultado=3/8
- Elevar resultado anterior al cubo
- Sumar 5 al resultado anterior
- Visualizar resultado



Dependiendo de cómo se programe el algoritmo, los parsers pueden funcionar de arriba a abajo (top-down parsing) de abajo a arriba (bottom-up parsing), recursivamente hacia abajo, recursivamente hacia la izquierda, etc.

En cualquier caso, por complejo que sea un lenguaje de programación, el lexicón y las reglas de su gramática son siempre infinitamente simples en comparación con las de un lenguaje natural. De ahí que, aunque el concepto de parser sea válido, la dificultad de crear una gramática computable en un idioma humano es enorme. Amén de que el lexicón es mucho más extenso, la cantidad de reglas puede ser enorme, precisar recursividad profunda y precisar deshacer ambigüedades y retóricas, una característica muy propia de los lenguajes humanos que no se da en ningún lenguaje de ordenador. Si una sentencia de ordenador debe escribirse como:


IF (X < 2) then a=(3-X) else a=(3+x)

IF (X <2) ELSE (a=3+x) THEN (a=3-x)

y mucho menos:

IF (X <2) entonces a=(3-X) else a=(3+x)

Sin embargo es esta una situación habitual en las lenguas naturales:

El balón de Juan se perdió
Se perdió el balón de Juan
Perdiose el balón de Juan
Se perdió el esférico de Juan
Se perdió la pelota de Juan


Los parsers que buscan analizar lenguajes naturales parten de alguna de las gramáticas teóricas vistas en capítulos anteriores pero, por lo general, la simplifican para que puedan ser manejables por un algoritmo de manera eficiente. Evidentemente, esta simplificación hace que su rendimiento merme. Es por eso, por ejemplo, que los traductores automáticos logren traducciones que no suelen ser muy buenas. Además, hoy en día, muchos parsers se fundamentan parcialmente en un corpus extensos de texto real que han sido anotados manualmente de manera que, estadísticamente, comparan la frase a analizar con las existentes en la base de datos. Como los computadores son muy rápidos, este cálculo estadístico extenso puede hacerse de manera muy eficiente.



PATR –II

Uno de los primeros programas- ya anticuado pero que se usa mucho para empezar a trabajar en lingüística computacional- fue PATR-II, un parser de lenguaje natural desarrollado por Stuart M. Shieber. Es un programa que usa una gramática propia libre de contexto con reglas y restricciones.

Con su interface tipo MS-DOS de líneas de comandos resulta hoy muy anticuado, pero su sencillez permite entenderlo rápidamente y el que pueda descargarse de la red invita a practicar casi inmediatamente. Además, sirve para cualquier idioma ya que es el usuario el que define el léxico y la gramática a tratar.

PATR-II puede descargarse aquí para aquellos que estén interesados en comenzar a juguetear en este campo.

PATR-II necesita dos archivos para poder funcionar. Uno, que debe tener extensión “.lex” contiene el léxico. Otro, con extensión “.grm” contiene las reglas de la gramática. Cada usuario puede crear sus lexicones y sus gramáticas propias en función del ámbito que quiera analizar y de la extensión de los textos que quiera estudiar.

Un ejemplo muy sencillo de parte de un archivo de léxico sería, por ejemplo:
;NOMBRES
\w niño
\c N
\f masc-sing

\w niños
\c N
\f masc-plur
\w niña
\c N
\f fem-sing

\w niñas
\c N
\f fem-plur

\w futbolista
\c N
\f mascfem
< conc num> = sing

\w futbolistas
\c N
\f mascfem
< conc num> = plur

\w la
\c DET
\f < num> = sing
< pers> = 3a
< gen> = fem

\w María
\c N
\f < num> = sing
< sem> = anim
< pers> = 3a
< gen> = fem

\w explica
\c V
\f < num> = sing
< sem> = anim
< pers> = 3a
< tip> = trans

\w explican
\c V
\f < num> = plur
< sem> = anim
< pers> = 3a
< tip> = trans

\w historia
\c N
\f < num> = sing
< sem> = inanim
< pers> = 3a


\w un
\c DET
\f < num> = sing
< pers> = 3a

\w amigo
\c Nla jh
\f < num> = sing
< sem> = anim
< pers> = 3a

\w de
\c PREP

\w infancia
\c N
\f < num> = sing
< sem> = inanim
< pers> = 3a

\w a
\c PREP

\w Ana
\c N
\f < num> = sing
< sem> = anim
< pers> = 3a

\w patatas
\c N
\f < num> = plur
< sem> = inanim
< pers> = 3a
< gen> = fem

\w comen
\c V
\f < num> = plur
< sem> = anim
< pers> = 3a

\w padre
\c N
\m < num> = sing
< sem> = anim
< pers> = 3a

\w habla
\c V
\f < num> = sing
< sem> = anim
< pers> = 3a
< tip> =trans

\w con
\c PREP

Obsérvese que cada línea empieza con una simbología que indica al ordenador de qué estamos hablando. Así “\w” significa que empieza una palabra (Word). Evidentemente, puede complicarse mucho más añadiendo más características (serían rasgos en el sentido de lo estudiado en capítulos anteriores).

Por su parte, el fichero de gramática contendría las reglas explicitadas de manera aproximada como vimos en capítulos anteriores. Por ejemplo:
; primero se define la terminología de abreviación de conjuntos de rasgos del léxico mediante la instrucción de PATR “let--- be”.
; y después las reglas.
;ABREVIATURAS
;
; CONDICIONES

Let masc-sing be
< conc num> = sing
< conc gen> = masc

Let masc-plur be
< conc num> = plur
< conc gen> = masc

Let fem-sing be
< conc num> = sing
< conc gen> = fem

Let fem-plur be
< conc num> = plur
< conc gen> = fem

; condiciones de disjunción

Let mascfem be {[conc_gen: fem]
[conc_gen: masc]
}

;
;comienzan las reglas
;
;
RULE O -> SN SV
RULE SN -> {QUAN/DET/QUAN1R} N ADJ
< DET conc> = < N conc>
< QUAN conc> = < N conc>
< QUAN1R conc> = < N conc>
< N conc> = < ADJ conc>

RULE QUAN1R -> QUAN1 DET
< QUAN1 conc> = < DET conc>
< QUAN1R conc> = < QUAN1 conc>

RULE SV-> V SPO, por ejemplo, otro fichero de gramática podría ser:

Rule S -> NP VP (SubCl)
< NP head agr> = < VP head agr>
< NP head case> = NOM
< S subj> = < NP>
< S pred> = < VP>

Rule NP -> {(Det) (AdjP) N (PrepP)} / PR
< Det head number> = < N head number>
< NP head> = < N head>
< NP head> = < PR head>

Rule Det -> DT / PR
< PR head case> = GEN
< Det head> = < DT head>
< Det head> = < PR head>

Rule VP -> VerbalP (NP / AdjP) (AdvP)
< NP head case> = ACC
< NP head verbal> = -
< VP head> = < VerbalP head>

Rule VerbalP -> V
< V head finite> = +
< VerbalP head> = < V head>

Rule VerbalP -> AuxP V
< V head finite> = -
< VerbalP head> = < AuxP head>

Rule AuxP -> AUX (AuxP_1)
< AuxP head> = < AUX head>

Rule PrepP -> PP NP
< NP head case> = ACC
< PrepP head> = < PP head>

Rule AdjP -> (AV) AJ (AdjP_1)

Rule AdvP -> {AV / PrepP} (AdvP_1)
Rule SubCl -> CJ SUna vez que tenemos ambos ficheros definidos podemos ejecutar PATR que nos muestra una pantalla del tipo (como se ve nada amigable para los estándares de hoy en día)

Podemos, entonces, introducir unas pocas órdenes. Así, EXIT sirve para finalizar la ejecución; LOAD GRAMMAR cargará en memoria el fichero de gramática que queremos usar; LOAD LEXICON cargará el fichero de léxico que vayamos a usar; PARSE comprobará que una sentencia es correcta o no.

Podríamos por ejemplo ordenar:

PARSE la niña explica historia

Y el ordenador respondería con:

o sea, dictamina que es una frase correcta de acuerdo al léxico existente en el fichero lexicón y a las reglas de gramática del fichero de gramática. Si no se cumpliese alguna condición mostraría un mensaje de error.

En la siguiente figura se ve la salida en pantalla como respuesta a analizar la oración, el niño bueno:



O, para un lexicón y una gramática en inglés, obtendríamos:


La mejor forma de entender lingüística computacional es practicando, de modo que animo a todos a descargarse PATR-II, crear un fichero de léxico, otro de reglas gramaticales y comenzar a parsear



El algoritmo CYK y su parser


Otro parser con el que se puede practicar en red es el CYK. En este enlace puede disfrutarse de una gramática reducida para inglés. Si, como yo he hecho, introduzco la frase I saw a cat on the roof (se pueden ver las reglas de la gramática en la ventana superior):


el programa nos devolverá el análisis en modo gráfico:




El algoritmo CYK (Cocke-Younger-Kasami) determina si una frase es correcta de acuerdo a las reglas de una gramática libre de contexto. Es un algoritmo del tipo bottom-up. La gramática utiliza el formalismo normal de Chomsky que ya vimos en los capítulos teóricos anteriores. El algoritmo considera cada subconjunto posible de combinaciones de las palabras para determinar si cumplen con las reglas. Lo hace por orden de longitud. Primero, frases de una palabra, luego de dos, etc. Si, al final, toda la sentencia cumple con las reglas, es que es válida.





El analizador THERA en español

En la dirección puede practicarse con un parser en español. Por ejemplo, introduciendo la frase El día es muy soleado el programa nos devuelve:


Este parser analiza sentencias en español y en catalán.





AMOSINE

Es una analizador desarrollado por el Grupo de Estructuras de Datos y Lingüística computacional con un interfaz moderno y fácil uso. Puede accederse a su página aquí




Link Grammar Parser

Puede encontrarse aquí pudiéndose descargar o usar en línea.


Escrito en lenguaje C The Link Grammar Parser es un parser sintáctico en ingles. Introduciendo una frase, el sistema la analiza sintácticamente .
Así, para la frase The man who went to London is rich el parser nos devuelve:




Otros programas on-line

En esta dirección existe otro parser en inglés. Ante la misma frase The man who went to London is rich devuelve la siguiente pantalla:

aquí se puede encontrar un desambiguador morfosintáctico:


Aquí puede obtenerse TreeForm Syntax que es un diagramador en árbol de frases.


PhpSyntaxTree es un programa para diagramar árboles sintácticos que se han escrito en notación lineal. Por ejemplo, la cadena sintáctica

SC [SD Quiénes_i][C' [C animan_j [+Q]][SF [SD t_i'][F'[F t_j' [Phi]][SV [SD t_i][V'[V t_j][SD la vida]]]]]]]

Y el programa nos dibujará el árbol correspondiente:


Por fin, una herramienta para dibujar árboles sintácticos y X-barras es Linguistic Tree Constructor que no analiza nada pero que permite dibujar a mano y con gran calidad dibujos como los que han ilustrado algunos de estos posts. Puede descargarse aquí.


Hoy en día pueden encontrarse numerosos recursos de lingüística computacional en red gratuitos y, cómo no, muchos también profesionales. En cualquier caso, nada como practicar. Especialmente con aquellos software que nos obligan a crear el lexicón y las reglas gramaticales lo que no sólo nos ayudará a entender los algoritmos sino que nos permitirá comprender mejor los conceptos teóricos.




To be continued…

(El capítulo siguiente de esta serie puede leerse en este enlace)