@ agnasg

parsers

17-10-2010 2:27 PM

Un parser es un programa (o parte de un programa) que analiza un archivo (o una entrada en general) y toma acciones de acuerdo al contenido que encuentra. Un parser forma parte de un compilador, pues el primer paso es analizar la entrada y almacenarla en estructuras que al  final permitirán generár código, o puede ejecutar acciones inmediatamente en caso de que sea un script (un programa que debe ejecutarse de inmediato como php o lua, lo que se llama lenguajes interpretados).

Un parser puede ser  requerido para limpiar un código fuente o para modificarlo de alguna forma, incluyendo encriptarlo u ofuscarlo.  Esto es justamente lo que estoy haciendo esta vez. Yo he hecho parsers desde que estudié lenguajes de programación, y si bien todos tienen sus peculiaridades, básicamente se reduce a lo mismo: identificar patrones y mantener el estado del parser, esto es, saber qué cosa se está procesando en este momento y cómo afecta eso el procesamiento futuro. Por ejemplo, si el programa encuentra un comentario que en PHP, C, C++ y otros lenguajes del mismo estilo puede comenzar con //  (en PHP además con #) eso significa que el resto de la línea debe ser ignorada. Si se encuentra un /* se debe ignorar hasta el próximo */. Y así sucesivamente.

Algunos parsers son simples como el que estoy haciendo en este momento que me va a permitir ofuscar código fuente PHP (para que el programa no pueda ser modificado, al menos fácilmente). Los parsers de los compiladores no son tan simples, porque después de identificar las instrucciones del lenguaje deben generar un código intermedio que se ejecutará posteriormente. Por ello el parser debe encargarse de generar ciertas estructuras que van a permitir el procesamiento posterior del compilador.

Un parser es necesario para procesar el lenguaje “scripting” o guión del juego. La primera regla del diseño de juegos es separar la lógica de los distintos motores que lo conforman (motor gráfico; motor de inteligencia artificial, etc). Esta es la arquitectura que ha probado ser más eficiente para el diseño y definición de un juego: en vez de codificar las descripciones y acciones de un sitio en el juego dentro del motor del juego, se define un lenguaje de definición de sitios, que incluya la definición de las acciones que el jugador puede ejecutar y las acciones que los psi ejecutarán. El motor del juego simplemente debe ejecutar este lenguaje. De esta forma se separa el motor del juego de la definición del juego y los diseñadores pueden dedicarse al contenido  sin preocuparse de nada más.

Esta separación entre la definición del juego y el motor del juego ha sido utilizada exitosamente en los juegos MUD. La codebase LPMud utiliza esta arquitectura (a eso se debe su popularidad). BatMud (el MUD que estoy jugando en estos momentos) está diseñado utilizando esta codebase.

La definición se guarda en archivos como cualquier programa para que el motor la lea a tiempo de ejecución. Hay infinidad de sintáxis, todas incompatibles entre sí, porque cada programador quiere incorporar ideas y conceptos propios. Algunas describen una ubicación en el juego en un archivo, otras almacenan varias ubicaciones en el mismo archivo. Por ejemplo, un conjunto de ubicaciones lucen de la siguiente forma:

bosque.def
casa.def
lago.def
pozo.def
pueblo.def

Donde cada archivo guarda la definición del sitio que está describiendo o definiendo. Por ejemplo el archivo bosque.def tiene algo como lo siguiente:


short() {
return "Un lugar en el bosque";
}
long(str)
{

write(“Este es un lugar rodeado de árboles por todas partes. El camino luce amarillo\n”);
write(“por la alfombra de hojas en el suelo.\n”);
write(” Hacia el este se ve una casa.\n”);
write(” Hay un lago al oeste de aqui.\n”);
}

Los que conocen el lenguaje inform descubrirán inmediatamente las similitudes para describir un “room” o ubicación. La rutina “short” presenta la descripción corta del sitio. La rutina “long” presenta una descripción más detallada. Es lo que se despliega al  ejecutar el comando “examinar” o ver. Estos archivos son el alimento para el parser que es el que se encarga de interpretar estos comandos y ejecutar las acciones según los comandos que ejecute el jugador.

EL parser se implementa de diversas formas: yo las he probado todas. El más antiguo enfoque es usar el duo maravillosos lex y yacc (buscarlo en google aparecen miles de enlaces). lex se encarga de generar un programa de análisis lexicográfico que permite identificar los distintos tokens en los que se compone el programa. Cada tokens es una pieza diferente del lenguaje: identificadores (que pueden ser variables o palabras claves del lenguaje), simbolos (+, -, *, /, etc), números y otros componentes. yacc por el otro lado genera un parser que dado los tokens y una gramática va a generar el código ejecutable o las acciones descritas en el archivo de definición.

Ambos programas (lex y yacc) tiene a su vez un archivo de definición. Para lex el archivo es algo como lo siguiente (tomado del parser de mi juego aventura gráfica):


"object" { return(OBJECT); }
"break" { return(BREAK); }
"if" { return(IF); }
"while" { return(WHILE); }
"else" { return(ELSE); }
{L}({L}|{D})* { return(IDENTIFIER); }
'(\\.|[^\\'])+' { return(CONSTANT); }
{D}+{E}{FS}? { return(CONSTANT); }
{D}*"."{D}+({E})?{FS}? { return(CONSTANT); }
{D}+"."{D}*({E})?{FS}? { return(CONSTANT); }
{D}* { return(CONSTANT); }
{I}* { return(CONSTANT); }
\"(\\.|[^\\"])*\" { return(STRING_LITERAL); }
"&&" { return(AND_OP); }
"||" { return(OR_OP); }
"<=" { return(LE_OP); } ">=" { return(GE_OP); }
"==" { return(EQ_OP); }
"!=" { return(NE_OP); }

El programa devuelve el valor indicado ({return (OBJECT);}) cuando encuentra alguno de los patrones en la columna de la izquierda. Por ejemplo, si encuentra la palabra “object” devuelve el identificador OBJECT (que es un número único). Si encuentra {L}({L}|{D})* devuelve IDENTIFIER. Esto último es una expresión regular, la L representa una letra, la D representa un dígito, el * representa 0 o más veces. El | indica el “o” lógico (por ejemplo cuando dices nos vemos el lunes “o” el martes. Es una contrucción lógica). Entonces esto significa que debe devolver un identificador cuando encuentra una letra seguida de una letra o un número 0 o más veces. El yacc requiere un archivo similar para representar la gramática.

Hoy en día (para mi juego de ficción interactiva y) para nunsoot estoy utilizando un parser escrito a mano: sin usar yacc ni lex. Así están programador inform y los LPMuds, y ahora entiendo por qué: mantener y mejorar los archivos de la gramática y el analizador lexicográficos es bien complicado. Además no estoy seguro si hay problemas de licenciamiento detrás de ellos.

Ahora me dispongo en las próximas semanas revisar el código del parser para nunsoot (que va a ser el mismo que utilizaré para panicput) y tengo que confesar que no lo hago con mucho entusiamo: es la parte más complicada del juego. Pero claro con una ventaja igualmente grandísima: facilidad el desarrollo del contenido del juego enormemente.

Los MUDs tienen más de 30 años de inventados pero todos estos conceptos son utilizados por los juegos modernos como World of Warcraft.