<$BlogRSDUrl$>

Pro·Log·[IR]

Programación Lógica y Recuperación de Información

«Algorithm = Logic + Control» Robert Kowalski (1979)

¡Importante! esta página hace uso de estilos recogidos en la especificación CSS2, no soportados por el navegador que está utilizando. Por favor, lea esta recomendación al respecto.

Archivo

Guardado por meses.

Enlaces

Los siguientes listados son una referencia a partir de la cual ampliar la búsqueda de sitios relacionados (i).

Bitácoras en castellano

Bitácoras en inglés

Directorios, metablogs

Programación lógica, Inteligencia Artificial, Recuperación de Información

Usabilidad, Arquitectura de la Información

Listas, foros, wikis

Matemáticas, ciencias

Miscelánea

Búsquedas

Búsqueda simple en varios de los motores más conocidos. Para mayor precisión, entrar en la página correspondiente e ir al apartado de búsqueda avanzada.

Búsqueda con Google
 

Búsqueda con Yahoo!
 

Búsqueda con AlltheWeb

Varios

Esta página traducida:

Traducción al catalán, internostrum; traducción al portugués, universia.

Reciba un aviso de nuevos comentarios (por Bloglet).


Agregue este sitio a su lector de "feeds" (sindicación mediante el sistema Atom).

Sobre este sitio

Espacio dedicado a la programación lógica y la recuperación de información, con una atención especial al lenguaje Prolog y otros lenguajes afines, pertenecientes al paradigma lógico y declarativo. También se tratará de hablar de estos temas desde la perspectiva de la Biblioteconomía y la Documentación.

En esta página

27.2.06

Analizadores sintácticos y tokenización

Dentro del complejo y amplio ámbito de dominio del Procesamiento del Lenguaje Natural (PLN), una de las funciones esenciales de los analizadores sintácticos o parsers es el análisis de cadenas de tokens en busca de posibles errores sintácticos (recordemos que la sintaxis, entendida en sentido amplio, es aquella parte de la gramática que se ocupa de las normas que rigen la formalización de las palabras en estructuras mayores tales como las oraciones, así como de las relaciones que establecen entre si dichas palabras). Un token se puede definir como la unidad mínima de información con significado propio dentro de una secuencia de caracteres alfanuméricos. Estas cadenas de unidades mínimas de información o unidades léxicas, son generadas previamente por el módulo lexicográfico integrado en el parser, encargado de identificarlas dentro de un texto o secuencia ordenada de caracteres alfanuméricos. Por su parte, la tokenización es un proceso consistente en la descomposición, en forma de lista, de esas cadenas de tokens en sus unidades mínimas. Así, un programa de este tipo podría generar la siguiente lista de tokens a partir de la frase "¡Hola Mundo!":

[161, 72, 111, 108, 97, 32, 77, 117, 110, 100, 111, 33]

Donde cada uno de los números de la lista se corresponde con el carácter ASCII (American Standard Code for Information Interchange) correspondiente a cada una de las unidades mínimas de significación identificadas en la frase, en el mismo orden. Por supuesto es posible llevar a cabo el proceso inverso, y a partir de esa lista generar las cadenas de tokens que forman la frase en cuestión. La tokenización es por tanto el proceso básico que permite manejar el lenguaje natural escrito para su posterior procesamiento, en base a su descomposición en unidades mínimas de información con significado propio.

La mayor parte de los lenguaje de programación contemplan instrucciones específicas para llevar a cabo el proceso de tokenización de cadenas ordenadas de caracteres alfanuméricos, si bien es posible implementar alternativamente esta operación mediante otros procedimientos proporcionados por esos lenguajes.

Así, un programa que pretenda "leer" un texto, deberá en primer lugar "tokenizarlo", generando una lista de los tokens, o unidades léxicas mínimas con significado propio, identificados en ese texto. A continuación, procederá a identificar unidades mayores de significado propio (contemplando por ejemplo la presencia, como elemento separador, del carácter ASCII 36, que se corresponde con el espacio en blanco), lo que podríamos asimilar como "palabras", para, finalmente, acabar identificando otras unidades de significación de orden superior, frases u oraciones. Diferenciadas las oraciones del texto "leído", el parser procede a realizar el análisis sintáctico propiamente dicho, identificando para ello las partes constitutivas de dichas oraciones que, a tal fin, son comparadas con patrones previamente definidos de estructuras posibles, que dependerán de la lengua de escritura del texto, y del nivel de complejidad de análisis que se pretenda alcanzar, ya que contemplar todas las posibles estructuras de una lengua y sus numerosas variaciones, y representarlas mediante una serie de reglas, no es una tarea precisamente sencilla.

La detección de las variaciones de posición admitidas en cada lengua, en relación con el orden de las palabras, o análisis de las transformaciones, se realiza mediante procesos de análisis estructural que tratan de identificar la estructura profunda de una oración en relación con su estructura superficial. El análisis estructural, en base a la estructura superficial (2) de una oración y, cambiando el orden de determinadas palabras, trata de determinar su posible transformación a una estructura de tipo profundo (1):

(1) Estructura profunda: "Pedro come una manzana"
(2) Estructura superficial: "Come Pedro una manzana"

La implementación del proceso de tokenización, al margen de la utilización de instrucciones específicas que transforman directamente una cadena de caracteres alfanuméricos en una cadena de tokens, implica la utilización de otro tipo de instrucciones cuya función es la "lectura" individual, uno a uno, de los caracteres presentes en el canal o grupo activo de entrada de datos (input stream) que se halla especificado, que por lo general será bien el teclado del ordenador, que es el canal activo de entrada por defecto (al igual que el canal de salida de datos, output stream, por defecto es el monitor del ordenador), o bien un fichero de texto ubicado en la ruta que se indique.

Así, en el lenguaje Prolog existe el predicado predefinido name(?AtomOrInt, ?String). El argumento AtomOrInt es la variable que representa la cadena de caracteres alfanuméricos o "átomo" que se desea tokenizar, mientras que el argumento String es la variable que representa la lista resultante. El símbolo "?" indica que ambos argumentos son reversibles, es decir, que pueden funcionar tanto como variables de entrada de datos como variables de salida, si bien uno de ellos ha de estar necesariamente instanciado. Su modo de funcionamiento es el siguiente:

?- name('¡Hola Mundo!', X).

X = [161, 72, 111, 108, 97, 32, 77, 117, 110|...] [write]

X = [161, 72, 111, 108, 97, 32, 77, 117, 110, 100, 111, 33]

Yes

La indicación [write] simplemente expresa que, una vez que el intérprete proporciona la lista de tokens, incompleta como indica la barra vertical seguida de puntos suspensivos "|...", se ha tecleado el operador w para que ésta se muestre en toda su extensión, ya que, en este caso SWI-Prolog, muestra por defecto en pantalla una versión abreviada de las listas, cuando estas exceden determinada longitud (no obstante se pueden obtener listas completas utilizando el comando "w", tal y como se explica en esta página).

Por supuesto, existen más predicados para la manipulación de átomos, como se referencia en el apartado "Analysing and Constructing Atoms" del manual de SWI-Prolog.

Otra forma de tokenizar átomos en Prolog es utilizar el predicado get0/1 y get0/2 y algún tipo de algoritmo recursivo que vaya "recorriendo" todo el texto del canal activo de entrada de datos (un archivo externo, por ejemplo), y al tiempo introduzca los tokens resultantes, incluyendo los espacios en blanco (get/1 y get/2 no los leen), en una lista acumuladora, en tanto no se alcance determinado marcador de parada, definido previamente (para este fin suele aprovecharse el átomo end_of_file, que se corresponde con el final de texto). Este predicado realmente lee el byte correspondiente a cada carácter alfanumérico individual, asociándolo con su correspondiente código ASCII.

El analizador sintáctico, en base a los constituyentes de una oración (véanse los principios de la gramática generativa de Noam Chomsky), y mediante un número finito de reglas, trata de determinar la gramaticalidad o no de un número infinito de construcciones. Un analizador sintáctico trata de ver hasta que punto puede someterse un grupo de palabras a una estructura de reglas. Así por ejemplo, si tenemos la oración:

Pedro come una manzana

en primer lugar, y mediante un proceso de tokenización, se genera una lista de las palabras que contiene. De esta lista inicial de palabras, se puede diferenciar una sublista que se corresponda con el Sintagma Nominal (SN) de la oración, y si ésta puede concatenarse con otras sublistas que según determinadas reglas se verifica como Sintagma Verbal (SV), la oración se concluye que es gramatical. Lo que importa en los constituyentes es el orden de las palabras de la oración.

El analizador sintáctico realiza el análisis secuencialmente, palabra por palabra, partiendo de una lista inicial que, siguiendo con el ejemplo de la oración expuesta, sería:

[pedro,come,una,manzana]

El proceso de computación de las reglas del analizador sintáctico debe dar como resultado otra lista, que será una lista vacía [] si la oración inicial es gramatical (siempre en base a las reglas que tenga definidas el analizador). En definitiva, partiendo de la lista inicial de palabras, el analizador sintáctico comprueba si ésta se puede subdividir en dos sublistas, que se corresponden, respectivamente, con el SN y el SV de la oración.

Más información: El análisis sintáctico y el análisis semántico.

[1] comentarios | # | lista |


Pro·Log·[IR],

Publicación: Blogger | Estadísticas: eXTReMe Tracking

Se recomienda ver este sitio con Mozilla 1+, Firefox 0.8+ ó Netscape 7+. Si no queda más remedio, con IE 6+. Si lo desea, comunique cualquier problema al respecto. También será bien recibida cualquier sugerencia sobre el contenido. La fuente de letra preferente es Georgia. Se prohibe la utilización del diseño de la página salvo autorización expresa del autor. Los contenidos escritos son de uso libre, siempre que se cite la fuente.