CAAD

Comunidad de Aventuras Conversacionales y Relatos Interactivos
Fecha actual 18 Dic 2018 14:47

Todos los horarios son UTC + 1 hora




Nuevo tema Responder al tema  [ 13 mensajes ] 
Autor Mensaje
 Asunto:
NotaPublicado: 07 Feb 2007 11:11 
Desconectado
Samudio
Samudio
Avatar de Usuario

Registrado: 09 Mar 2004 16:16
Mensajes: 5304
Ubicación: Coruña
jalbam escribió:
Eso que dices de analizadores lexicos tiene bastante complicacion por lo que se ve, la verdad (solo hace falta leerlo en la wikipedia para pederse con explicaciones que no entiendo sobre automatas de pila, etc). Seria interesante aprenderlo, asi que no olvides publicar explicaciones bien claras a medida que lo vayas haciendo :)


Ya que yo sé algo de eso, me salgo un poco del tema general del hilo para hacerte una brevísima explicación orientativa de cómo es el tema de los analizadores léxicos. Si esto genera un offtopic significativo, siempre lo puede mover un administrador a otro hilo.

Los analizadores léxicos que seguramente has visto por ahí, y donde aparece el tema de los autómatas, son los que se utilizan para el análisis léxico de programas en lenguajes de programación. Lo único que hacen estos analizadores es distinguir cada palabra que aparece en un programa y determinar qué tipo de elemento léxico representa, es decir, si se trata de un número, un string, un nombre (que podría ser de función, de variable o lo que sea, en eso el analizador léxico no se mete), un paréntesis abierto, etc.

Para ello los analizadores léxicos se basan en expresiones regulares, que son algo que seguramente ya habrás visto por ahí. La teoría de los autómatas surge por debajo porque los autómatas finitos son una implementación de las expresiones regulares. Pero en la práctica, si quieres hacer un analizador léxico para un lenguaje de programación, no necesitas saber teoría de autómatas. Basta con coger uno de los muchísimos generadores de analizadores léxicos que hay (lex, flex, o los que vienen como parte de generadores de compiladores como javacc, antlr...) y decirle cómo son las expresiones regulares de los diferentes elementos de tu lenguaje. Así que si quieres hacer algo así te recomiendo que simplemente te leas la documentación de uno de estos sistemas, pues los autómatas sólo te hacen falta si quieres hacer un generador de analizadores léxicos (o si tienes curiosidad por conocerlos).

Este tipo de analizadores léxicos que he comentado pueden servirnos a nosotros para proporcionar, por ejemplo, un lenguaje de scirpting para un motor de aventuras. Sin embargo, para analizar el lenguaje natural no se utilizan. En procesamiento del lenguaje natural también se usan analizadores léxicos, que son los que determinan si una palabra es sustantivo, verbo, singular, plural, etc. Sin embargo, para tratar con lenguaje natural las expresiones regulares se quedan muy cortas, porque no conocemos la forma de todas las palabras, e incluso si la conociésemos eso no nos bastaría para distinguir la preposición "sobre" del sustantivo "sobre" o del presente de subjuntivo del verbo sobrar "sobre", por ejemplo.

En aplicaciones "serias" de lenguaje natural, lo que se suele utilizar para esto son unos analizadores léxicos entrenados mediante modelos estadísticos, sobre todo los llamados modelos de Markov ocultos (HMM's). Estos analizadores se basan en el contexto de las palabras para determinar a qué categoría pertenecen, y obtienen una proporción de aciertos que ronda el 96% en español o el 98% en inglés.

En las aventuras, yo nunca he visto utilizar una cosa de éstas. Normalmente, por lo que yo sé, se hace un análisis léxico bastante ad hoc: conocemos unos cuantos verbos, conocemos unos cuantos sustantivos, y lo demás lo articulamos a partir de ahí. Además, normalmente el análisis léxico y el sintáctico están mezclados, no en dos fases diferenciadas (la única excepción que conozco a esto es TADS).

Por lo que yo sé, en Superglús y en AGE se hace un análisis sintáctico ad-hoc y "flexible", buscando las palabras que se consideren relevantes e ignorando muchas veces el resto. En Inform se hace un análisis sintáctico estricto, buscando que las frases se ajusten a algo que se llama "gramática", pero que no es lo que se suele llamar una gramática en teoría de lenguajes formales (o lo es, pero con muchas restricciones, siendo - que me corrijan si me equivoco - más restrictiva que las expresiones regulares). En TADS, por otra parte, por lo que he visto se utilizan gramáticas "de verdad", el parser interno tiene una gramática independiente del contexto ampliable y modificable. TADS además sí que diferencia el análisis léxico del sintáctico.

En fin, parafraseando a Aznar, "menudo coñazo les he soltado". :D

_________________
Actúa siempre de tal modo que las decisiones de tu voluntad pudiesen servir como preceptos de una legislación universal (E. Kant)


Arriba
 Perfil  
 
 Asunto:
NotaPublicado: 07 Feb 2007 11:45 
Desconectado
Enano Maluva
Enano Maluva
Avatar de Usuario

Registrado: 04 Sep 2006 13:08
Mensajes: 37
Ubicación: Cambrils (Tarragona)
Muchas gracias, Al-Khwarizmi. Ahora me ha quedado mas claro :)

Aunque sigo perdiendome en conceptos como "generadores de compiladores" (en google no encuentro la explicacion exacta de lo que son) o automatas finitos, notacion BNF, lenguajes formales, diferencia entre analizador sintactico o gramatico, lenguajes libres de contexto, etc. Pero es mas debido a mis propias limitaciones para entender todo eso que a otra cosa :) Se ve que todo esto es un amplio mundo por aprender y bastante complicado (o eso parece).

A parte de un analizador lexico que analiza la orden que el jugador envia tambien es necesario otro analizador lexico para interpretar el lenguaje del parser con el que se ha hecho la aventura, ¿no? (distinguiendo ordenes del parser, variables, texto, etc).

Saludos y gracias ;)

_________________
------
Juan Alba Maldonado


Arriba
 Perfil  
 
 Asunto:
NotaPublicado: 07 Feb 2007 12:13 
Desconectado
Guionista
Guionista
Avatar de Usuario

Registrado: 09 Oct 2006 13:51
Mensajes: 385
Ubicación: mundo
Al-Khwarizmi escribió:
En fin, parafraseando a Aznar, "menudo coñazo les he soltado". :D


Espero que no sea off-topic, porque la teoría de autómatas y lenguajes formales me encanta.
Para empezar, estoy de acuerdo contigo (tal y como le expliqué a lilith en respuesta a un comentario que me hizohizo hace unos dias), los analizadores léxicos y sintácticos reconocen lenguajes independientes al contexto, y parece que en nuestro caso solo son útiles para el desarrollo de nuevos lenguajes de programación para crear aventuras por ejemplo.
Los lenguajes independientes del contexto son los que se definen con un autómata con pila. Es decir, tiene memoria y recuerdan su propio estado con una pila, por lo que, por ejemplo, podemos analizar y controlar palabras y signos que contengan grupos de paréntesis y llaves que estén correctamente anidadas (paréntesis o grupos de objetos, arrays, etc), cosa que se hace muy a menudo en los lenguajes de programación, pero no se suele utilizar en el lenguaje natural.
Por esta razón, este tipo de analizadores son demasiado complejos y potentes en nuestro caso, el parseo de frases en lenguaje natural.
Para esto último, podemos utilizar un autómata determinista con estado pero sin pila, que simplemente reconoce sucesiones de letras en un orden determinado (palabras), pero para esto no es necesario utilizar ninguna librería o similar, sino que lo podemos hacer "a mano": iterando cada palabra y buscando qué verbo o nombre es, controlando el estado de nuestra frase a mano. De todas formas, puede ser útil utilizar árboles para optimizar estas búsquedas en vez de hacerlas iterativas, todo dependerá de los recursos (memoria y micro) donde corras tu analizador. Si alguien se mete a picar algo de esto, estaré encantado de contrastar opiniones.


Arriba
 Perfil  
 
 Asunto:
NotaPublicado: 07 Feb 2007 12:33 
Desconectado
Guionista
Guionista
Avatar de Usuario

Registrado: 09 Oct 2006 13:51
Mensajes: 385
Ubicación: mundo
jalbam escribió:
Muchas gracias, Al-Khwarizmi. Ahora me ha quedado mas claro :)

Aunque sigo perdiendome en conceptos como "generadores de compiladores" (en google no encuentro la explicacion exacta de lo que son)


No son generadores de compiladores, sino generadores de analizadores sintacticos y lexicos. Si quieres ver algo de esto, te recomiendo http://www.antlr.org. Aqui tienes un buen manual en castellano que te explica que son todo esto de los analizadores: www.lsi.us.es/~troyano/documentos/guia.pdf

jalbam escribió:
o automatas finitos,

Los autómatas son definiciones matemáticas de algorítmos que reconocen lenguajes, en la wiki viene mejor explicado http://es.wikipedia.org/wiki/Aut%C3%B3mata_finito

jalbam escribió:
notacion BNF, lenguajes formales, diferencia entre analizador sintactico o gramatico, lenguajes libres de contexto, etc. Pero es mas debido a mis propias limitaciones para entender todo eso que


No creo que sean tus limitaciones. Es un tema bastante complicado (esa asignatura la suspendí, y no suelo suspender :oops: ). Si te lees la guia de antlr, te ayudará bastante a entenderlo todo, viene todo muy bien explicado.
jalbam escribió:
a otra cosa :) Se ve que todo esto es un amplio mundo por aprender y bastante complicado (o eso parece).

A parte de un analizador lexico que analiza la orden que el jugador envia tambien es necesario otro analizador lexico para interpretar el lenguaje del parser con el que se ha hecho la aventura, ¿no?
(distinguiendo ordenes del parser, variables, texto, etc).
Saludos y gracias ;)

Efectivamente! Por eso los parsers de aventuras conversaciones tienen 2 parsers: uno para parsear el codigo fuente de la aventura y otro para parsear las ordenes que introduce el jugador.
Si vas a crear un parser, necesitar un lenguaje (o pseudolenguaje) para definir tus aventuras. Pero no es necesario crear un compilador (y por tanto, utilizar analizadores sintácticos y léxicos) para esto, pues creo que es una tarea titánica (aunque Inform es así, incluso más: tiene su propia máquina virtual!), así que puedes crearte un intérprete que analice la definición de tu aventura en tu lenguaje y la ejecute directamente sin necesidad de compilar.
Puedes apoyarte en otros sub-lenguajes, como por ejemplo Beanshell (el que utiliza Al-Khwarizmi en AGE), OGNL (el que utilizo yo) o cualquier otro, por ejemplo Phyton, que tiene intérpretes en varios lenguajes.


Arriba
 Perfil  
 
 Asunto:
NotaPublicado: 07 Feb 2007 12:36 
Desconectado
Samudio
Samudio
Avatar de Usuario

Registrado: 09 Mar 2004 16:16
Mensajes: 5304
Ubicación: Coruña
betopica escribió:
Es decir, tiene memoria y recuerdan su propio estado con una pila, por lo que, por ejemplo, podemos analizar y controlar palabras y signos que contengan grupos de paréntesis y llaves que estén correctamente anidadas (paréntesis o grupos de objetos, arrays, etc), cosa que se hace muy a menudo en los lenguajes de programación, pero no se suele utilizar en el lenguaje natural.
Por esta razón, este tipo de analizadores son demasiado complejos y potentes en nuestro caso, el parseo de frases en lenguaje natural.


Bueno, en realidad esta afirmación no es exacta. Realmente, el parseo "decente" de frases en lenguaje natural es mucho más complicado que el de lenguajes de programación. En el mundo del procesamiento del lenguaje natural fuera de las aventuras de texto, nadie piensa en analizar lenguaje natural con algo más simple que los lenguajes independientes del contexto. Más bien es al revés, los lenguajes independientes del contexto son lo más sencillo que se utiliza para lenguaje natural, y a menudo se utilizan lenguajes más potentes, porque el lenguaje natural no cumple la propiedad de independencia del contexto (que los lenguajes de programación sí, además de cumplir también la propiedad de no ser ambiguos, que simplifica mucho el parsing).

Así pues, si para las aventuras hasta ahora no se han utilizado apenas analizadores basados en lenguajes independientes del contexto (con la excepción de TADS, como digo) no es porque parsear lenguaje natural sea fácil; sino simplemente porque los diseñadores de sistemas de desarrollo de aventuras han considerado que no merece la pena el esfuerzo de hacer un parser complejo, cuando en última instancia lo que el jugador puede hacer siempre va a estar limitado por las acciones que haya considerado el programador de la aventura. En otras palabras, se usan parsers rudimentarios porque de poco te vale tener un parser del copón que te devuelve toda una estructura semántica para la frase, si luego aunque entiendas perfectamente la frase le vas a decir al jugador "no puedes hacer eso" porque ha pedido trepar a un árbol y no tenías tiempo de programar la cima. Si las aventuras tuviesen los presupuestos de los MMORPGS o los juegos 3D, otro gallo cantaría, supongo. :)

_________________
Actúa siempre de tal modo que las decisiones de tu voluntad pudiesen servir como preceptos de una legislación universal (E. Kant)


Arriba
 Perfil  
 
 Asunto:
NotaPublicado: 07 Feb 2007 12:52 
Desconectado
Guionista
Guionista
Avatar de Usuario

Registrado: 09 Oct 2006 13:51
Mensajes: 385
Ubicación: mundo
Al-Khwarizmi escribió:
betopica escribió:
Es decir, tiene memoria y recuerdan su propio estado con una pila, por lo que, por ejemplo, podemos analizar y controlar palabras y signos que contengan grupos de paréntesis y llaves que estén correctamente anidadas (paréntesis o grupos de objetos, arrays, etc), cosa que se hace muy a menudo en los lenguajes de programación, pero no se suele utilizar en el lenguaje natural.
Por esta razón, este tipo de analizadores son demasiado complejos y potentes en nuestro caso, el parseo de frases en lenguaje natural.


Bueno, en realidad esta afirmación no es exacta. Realmente, el parseo "decente" de frases en lenguaje natural es mucho más complicado que el de lenguajes de programación. En el mundo del procesamiento del lenguaje natural fuera de las aventuras de texto, nadie piensa en analizar lenguaje natural con algo más simple que los lenguajes independientes del contexto. Más bien es al revés, los lenguajes independientes del contexto son lo más sencillo que se utiliza para lenguaje natural, y a menudo se utilizan lenguajes más potentes, porque el lenguaje natural no cumple la propiedad de independencia del contexto (que los lenguajes de programación sí, además de cumplir también la propiedad de no ser ambiguos, que simplifica mucho el parsing).


Bueno, cuando me refería al parseo del lenguaje natural, me refería al rudimentario sistema de comunicación entre el jugador y la aventura, que básicamente es: verbo + objeto1 + objeto2, adornado con algunas palabras como artículos, preposiciones y adverbios que a veces suelen ser ignorados. Un parseo más potente como el que dices sería muy complejo y quizá hasta inútil por excesivo: ¿para qué sirve necesitamos saber qué es el complemento directo, indirecto, o el sujeto y predicado? Debería ser la leche tener un sistema tan potente.. ¿quizá para Inform 9?
Por cierto, me voy a mirar TADS a ver cómo parsea las órdenes, que me has picado la curiosidad.


Arriba
 Perfil  
 
 Asunto:
NotaPublicado: 07 Feb 2007 15:30 
Desconectado
Grafista
Grafista
Avatar de Usuario

Registrado: 15 Ene 2005 22:26
Mensajes: 780
ok, se puede seguir aqui esta buena conversacion.


Arriba
 Perfil  
 
 Asunto:
NotaPublicado: 07 Feb 2007 15:31 
Desconectado
Implementador
Implementador
Avatar de Usuario

Registrado: 10 Mar 2004 21:40
Mensajes: 1444
Ubicación: Nímgar, Ciudad Lunar
betopica escribió:
Bueno, cuando me refería al parseo del lenguaje natural, me refería al rudimentario sistema de comunicación entre el jugador y la aventura, que básicamente es: verbo + objeto1 + objeto2, adornado con algunas palabras como artículos, preposiciones y adverbios que a veces suelen ser ignorados. Un parseo más potente como el que dices sería muy complejo y quizá hasta inútil por excesivo: ¿para qué sirve necesitamos saber qué es el complemento directo, indirecto, o el sujeto y predicado?


Para poder interactuar CORRECTAMENTE con los PSIs en lugar de los apaños que se han estado haciendo hasta ahora.

Algo de comprensión del significado de la frase es imprescindible para poder intentar tratar de responder adecuadamente 'desde un PSI'. La gramática de Inform no sirve para eso.


Arriba
 Perfil  
 
 Asunto:
NotaPublicado: 08 Feb 2007 01:26 
Desconectado
Guionista
Guionista
Avatar de Usuario

Registrado: 03 Nov 2004 17:15
Mensajes: 300
Ubicación: ... muy lejos de todo lo que se hace llamar social...
jalbam escribió:
Aunque sigo perdiendome en conceptos como "generadores de compiladores" (en google no encuentro la explicacion exacta de lo que son) o automatas finitos, notacion BNF, lenguajes formales, diferencia entre analizador sintactico o gramatico, lenguajes libres de contexto, etc. Pero es mas debido a mis propias limitaciones para entender todo eso que a otra cosa :) Se ve que todo esto es un amplio mundo por aprender y bastante complicado (o eso parece).


En realidad no te pierdes de gran cosa. Yo he programado varios interpretes y compiladores utilizando lex (un analizador lexicográfico) y yacc (un generador de compiladores) y su última encarnación llamado bison, y de verdad acelera mucho el trabajo, pero se puede convertir en una pesadilla. Ultimamente estoy programando estas cosas a pie. Es más trabajo, pero resulta muy divertido.

_________________
Slds,

/\+++++/\
< agnas >
\/+++++\/
http://www.micronosis.com/


Arriba
 Perfil  
 
 Asunto:
NotaPublicado: 08 Feb 2007 11:39 
Desconectado
Samudio
Samudio
Avatar de Usuario

Registrado: 09 Mar 2004 16:16
Mensajes: 5304
Ubicación: Coruña
agnas escribió:
En realidad no te pierdes de gran cosa. Yo he programado varios interpretes y compiladores utilizando lex (un analizador lexicográfico) y yacc (un generador de compiladores) y su última encarnación llamado bison, y de verdad acelera mucho el trabajo, pero se puede convertir en una pesadilla. Ultimamente estoy programando estas cosas a pie. Es más trabajo, pero resulta muy divertido.


Bueno, es que por suerte lex y yacc/bison no son "lo último" en generación de compiladores. Ahora hay soluciones muchísimo más sencillas de usar.

Yo usé yacc/bison durante la carrera, y me pareció una cosa bastante infernal, porque en teoría estás escribiendo una gramática pero en la práctica tienes que estar pensando en el algoritmo de parsing LR (que es el que usan) en todo momento, para escribir las reglas tal como el algoritmo las "quiere" y resolver conflictos. Y como quieras dar mensajes de error con sentido cuando falle el análisis, ya tienes que irte a los estados del autómata, con lo cual al final el nivel de abstracción que proporciona yacc acaba siendo mínimo.

Pero ahora yacc/bison no creo que lo use ya nadie, porque existe otra generación de generadores de compiladores basados en algoritmos no LR que hacen la cosa mucho más fácil. Se ha producido un cambio de tendencia en favor de generadores tipo LL(k), de los cuales el más conocido seguramente sea ANTLR. Yo no he usado ANTLR, pero he usado JavaCC (una versión sólo para java, a los que usáis C os convendrá más ANTLR) y doy fe de que el tiempo de desarrollo es un orden de magnitud menor que en yacc. Con las gramáticas LL sólo hay un par de cosas a evitar, pero que están muy bien definidas (léase recursividad izquierda), y si se produce algún conflicto todos se arreglan de la misma manera: aumentando el lookahead. No hay que pensar nunca en reducciones ni en estados, y escribir mensajes de error es sencillísimo hasta el punto de que él mismo te da automáticamente mensajes del tipo: "Se esperaba X, se encontró Y", porque un parser LL sabe en todo momento qué cosas podrían venir después de lo que está leyendo.

Por otra parte, si se quiere sacrificar algo de eficiencia para obtener más sencillez todavía que en los generadores LL(k), también existen generadores de compiladores basados en algoritmos generales de parsing, es decir, que aceptan cualquier gramática. Tú les das la gramática, cualquier gramática, y simplemente funcionan. Se habla de ellos en: http://www.acm.org/crossroads/xrds7-5/bison.html

En mi experiencia práctica, creo que el paso anterior, LL(k), ya es suficientemente sencillo, y es el que suelo usar. Los algoritmos generales también pueden ser interesantes. Lo que hoy en día no usaría ni de broma es yacc/bison. Creo que tuvo su época pero ya pasó, la verdad. Puede ser un poco más eficiente que un parser LL(k), pero hoy en día a poca gente le puede importar esa diferencia de eficiencia, y en las aplicaciones donde realmente se quiere exprimir el último milisegundo de CPU tampoco va uno a usar yacc, porque puede conseguir más eficiencia con un parser ad hoc. Así que si queréis mirar sistemas de éstos, os aconsejo que echéis un ojo a ANTLR o JavaCC.

_________________
Actúa siempre de tal modo que las decisiones de tu voluntad pudiesen servir como preceptos de una legislación universal (E. Kant)


Arriba
 Perfil  
 
 Asunto:
NotaPublicado: 12 Feb 2007 13:42 
Desconectado
Enano Maluva
Enano Maluva
Avatar de Usuario

Registrado: 04 Sep 2006 13:08
Mensajes: 37
Ubicación: Cambrils (Tarragona)
Muchas gracias por compartir vuestros conocimientos, que no son pocos :)

Es un tema muy interesante, aunque entre mas indago y me informo mas me doy cuenta que se todavia menos, hehehe. Es muy amplio y parece todo un mundo.

De todas formas, es una suerte que para programar una aventura algo decente tampoco es necesario crear un parser tan potente. Si no, seria una lastima :)

_________________
------
Juan Alba Maldonado


Arriba
 Perfil  
 
 Asunto:
NotaPublicado: 12 Feb 2007 15:42 
Desconectado
Guionista
Guionista
Avatar de Usuario

Registrado: 09 Oct 2006 13:51
Mensajes: 385
Ubicación: mundo
jalbam escribió:
Muchas gracias por compartir vuestros conocimientos, que no son pocos :)

Es un tema muy interesante, aunque entre mas indago y me informo mas me doy cuenta que se todavia menos, hehehe. Es muy amplio y parece todo un mundo.



Bueno, si estas pensando en hacer un lenguaje para crear aventuras tipo yasmina, te recomiendo que utilices algún interprete de algún lenguaje ya existente que corra bajo php y que se pueda modificar o reutilizar. La verdad es que cuanto más trabajo te ahorres, ¡mejor! :)


Arriba
 Perfil  
 
 Asunto:
NotaPublicado: 11 Jul 2007 16:17 
Desconectado
Grafista
Grafista
Avatar de Usuario

Registrado: 15 Ene 2005 22:26
Mensajes: 780
Hola!
no he podido hacer andar ANTLR para que genere codigo en C.
Debo bajar un runtime o algo asi, pero me pierdo en el repositorio, :-(


¿Alguno ha probado?

_________________
INFSP7 - Canal de Noticias INFSP

Porque donde está tu tesoro, allí también estará tu corazón.


Arriba
 Perfil  
 
Mostrar mensajes previos:  Ordenar por  
Nuevo tema Responder al tema  [ 13 mensajes ] 

Todos los horarios son UTC + 1 hora


¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 1 invitado


No puede abrir nuevos temas en este Foro
No puede responder a temas en este Foro
No puede editar sus mensajes en este Foro
No puede borrar sus mensajes en este Foro

Buscar:
Saltar a:  
cron
Desarrollado por phpBB® Forum Software © phpBB Group
Traducción al español por Huan Manwë para phpBB-Es.COM