(COMpiler for PArsing Schemata): Manual Resumido
Contents
1. gt S UNIVERSIDADE DA CORU A Departamento de Computaci n COMPAS COMpiler for PArsing Schemata Manual Resumido de Usuario CARLOS G MEZ RODR GUEZ MIGUEL A ALONSO 6 de diciembre de 2008 ndice 3 3 3 4 Compilaci n del c digo generado 8 Ejecuci n del c digo generado 9 9 4 oO 6 1 Ejecuci n mediante interfaz gr fico 6 2 Ejecuci n mediante l nea de comandos 7 Ejemplos proporcionados con la distribuci n 16 8 Construyendo nuevos esquemas de an lisis sint ctico 17 1 Introducci n COMPAS COMpiler for PArsing Schemata es un sistema que permite obtener au tom ticamente implementaciones eficientes de algoritmos de an lisis sint ctico a partir de especificaciones formales en forma de esquemas de an lisis sint ctico 6 La intenci n de este manual de usuario es proporcionar una gu a de uso del sistema incluyendo toda la informaci n necesaria para utilizarlo para transformar esquemas de an lisis sint ctico en implementaciones de los algoritmos de an lisis correspondientes as como para ejecutarlos sobre oraciones y gram ticas concretas Este manual est diri gido al uso pr ctico del software y no a la teor a subyacente Se presupone pues que el usuario que quiera dise ar e implementar analizadores con COMPAS debe estar previa mente familiarizado con la teor a del an lisis sint ctico en general y de los esquemas de an lisis sint ctico en particular Como referenc2. step OptEarleyInitter S gt alpha Ss gt alpha 0 0 S step OptEarleyScanner A gt alpha a beta i j Sarboll an yo eG eels ji A gt alpha a beta i jtl S arboll a J step OptEarleyCompleter A gt alpha B beta i j Sarboll B gt gamma J k Sarbol2 A gt alpha B beta i k arboll1 Sarbol2 step OptEarleyPredictor0 A gt alpha B beta i Jj Sarboll B gt B E r j a j r SSB step OptEarleyPredictorl A gt alpha B beta i j Sarboll B gt Di NR step OptEarleyPredictor2 A gt alpha B beta i Jj Sarboll B gt ED Bro CD j J 55B step OptEarleyPredictor3 A gt alpha B beta 1 j Sarboll B gt C D E gamma B gt C DE gamma j j 33B goal S gt alpha O length Sarbolfinal Para compilar este esquema ejecutamos generate bat c schemata earleyOptTree sch o c generatedparsers earleytree y obtenemos la siguiente salida sre sc sre sc sre sc ters sre sc ters sre sc ters sre sc ters Generating code for deductive step 1 generated file c generatedparsers earleytr SP_OptEarleyInitterStep java size 2392 characters Generating code for deductive step 2 generated file c generatedparsers earleytree srce sc SP_OptEarleyScannerStep java size 10583 characters Generating code for
3. arboll el error ser a Schema File schemata OptimizedEarleyWithTree sch parser sparser ParseException Encountered at line 38 column 1 Was expecting one of 1e L at parser sparser SchemaParser generateParseException SchemaParser java 826 Coso at launcher Main main Main java 94 Dici ndonos expl citamente que encontr un car cter donde esperaba encontrar un fin de tem o una coma continuaci n de tem e indic ndonos en qu l nea se encuentra el error Todos los errores de formato que podamos cometer en el esquema de entrada producen mensajes de alguno de estos dos tipos al ejecutar el compilador de esquemas 5 Compilaci n del c digo generado El contenido del directorio c generatedparsers earleytree tras la compi laci n anterior consiste en un subdirectorio src que contiene el c digo Java de la implementaci n completa y autocontenida del algoritmo de Earley que se ha generado y un fichero build xml que sirve para compilar mediante el sistema de construcci n ant Para compilar el c digo Java generado simplemente tenemos que situarnos en el directorio c generatedparsers earleytree y escribir ant Obteniendo una salida como sta Buildfile build xml init mkdir Created dir C generatedparsers earleytree build compile javac Compiling 45 source files to C generatedparsers earleytree build dist mkdir Created dir C ge
4. en un lugar donde pueda ir una element definition la interpretar como una expresi n regular que define el conjunto de cadenas asociado a un tipo de elemento que puede aparecer en los esquemas Cuando encuentre una cadena as donde pueda ir un element usar las expresiones regulares que aparezcan en esas definiciones de elemento adem s de las que se incluyan en el fichero de configuraci n element s txt del sistema para decidir a qu clase de elemento se refiere la cadena As la estructura general del fichero de esquema es la siguiente Una secci n opcional enmarcada entre los delimitadores begin_elements y end_elements donde se llevan a cabo definiciones de elementos Estas defi niciones son asociaciones de expresiones regulares con clases y m todos Java representando elementos que puedan aparecer en los esquemas bien elementos definidos por el usuario o predefinidos de los que se incluyen con COMPAS Una secci n opcional enmarcada entre los delimitadores begin_options y end_options que se utilia para parametrizar el analizador sint ctico Por defec to las opciones se pueden utilizar para parametrizar el tipo de agenda o de m qui 18 na deductiva que se utiliza en el c digo generado por ejemplo podemos poner option agendaClass agenda PriorityQueueAgenda para utilizar una cola de prioridad como agenda El contenido de las l neas de opci n tambi n es accesible mediante una sencilla API desde
5. cg204 compas grammars TelescopioGrammar Sentence el telescopio es bonito Grammar init time ms 9 Parsing time ms 1 Grammar init items 8 Total items 12 tems generated during parsing time 4 tem list S er NP VP 0 0 S bas bonito 3 4 nd of item list END OF TEST RESULTS ee H Donde se muestran la fecha y la hora a la que se ejecut el an lisis la gram tica y la frase utilizadas los tiempos de inicializaci n de la gram tica y de an lisis todos ellos mostrados en milisegundos y la cantidad de tems generados Las l neas BEGINNING OF TEST RESULTS y END OF TEST RESULTS sirven para diferenciar f cilmente los resultados de un experimento y el siguiente si se vuel can todos al mismo fichero especialmente si los datos se van a leer con alguna herramienta para su tratamiento autom tico PARSEFILE lt entrada gt lt salida gt Analiza l nea por l nea las frases contenidas en el fichero lt entrada gt y vuelca los resultados al fichero lt salida gt EXEC lt script gt Ejecuta un fichero de script que es un fichero que contiene una lista de rdenes v lidas para el interfaz de l nea de comandos de las implemen taciones generadas por COMPAS Es decir una lista de rdenes LOAD PARSE PARSEF ILE etc Este comando se puede utilizar para llevar a cabo experimentos sobre multitud de ficheros y gram ticas volcando los resultados a ficheros y pu diend
6. debemos hacer para utilizar el analizador es cargar una gram tica Para ello podemos teclear directamente la ruta al fichero de gram tica en el campo de texto Gram tica y a continuaci n pulsar Cargar Otra alternativa m s c moda en la mayor a de los casos es utilizar el bot n Examinar que abrir el di logo que se muestra en la figura 2 permitiendo seleccionar el fichero de gram tica Una vez oxi Gram tica Examinar Cargar Frase _ Mostrar s lo items meta Figura 1 Interfaz del analizador generado seleccionado un fichero su ruta aparecer en el campo Gram tica y podremos pulsar Cargar directamente para leer la gram tica En el directorio grammars de la distribuci n se incluyen diversas gram ticas que se pueden utilizar para las pruebas Por ejemplo una gram tica independiente del contexto muy sencilla es TelescopioGrammar una gram tica para probar con la oraci n ambigua Juan vio a un hombre con un telescopio En la figura B se muestra la ventana del programa despu s de cargar esta peque a gram tica de ejemplo En el rea de texto que ocupa la parte inferior izquierda de la ventana aparece informaci n de estado y mediciones relacionadas con la carga de la gram tica La funci n de esta rea de texto siempre va a ser mostrar informaci n de este tipo mientras que la que ocupa la parte inferior derecha de la
7. deductive step 3 generated file c generatedparsers earleytr SP_OptEarleyCompleterStep java size 12806 characters Generating code for deductive step 4 generated file c generatedparsers earleytr SP_OptEarleyPredictor0Step java size 5142 charac Generating code for deductive step 5 generated file c generatedparsers earleytr SP_OptEarleyPredictorlStep java size 5304 charac Generating code for deductive step 6 generated file c generatedparsers earleytr SP_OptEarleyPredictor2Step java size 5466 charac Generating code for deductive step 7 generated file c generatedparsers earleytr SP_OptEarleyPredictor3Step java size 6285 charac Generating code for item indexing hema s hema s hema s hema s hema s hema s hema s tep tep tep tep tep tep tep generated file c generatedparsers earleytree src schema item ItemHandler java size 85638 characters Generating code for deductive step indexing generated file c generatedparsers earleytree src schema step StepHandler java size 16099 characters Generating code for goal condition 8 generated file c generatedparsers earleytree src schema step SP_Goall java size 3225 characters Generating code for step factory generated file c generatedparsers earleytree src schema step StepFactory java size 833 characters Copying common files copy
8. successfully completed La salida nos informa de los ficheros que han sido generados as como de su tama o N tese que no aparecen mencionados todos los ficheros que se obtienen como salida de la compilaci n sino s lo aqu llos que se generan espec ficamente para cada esquema Otros ficheros que son gen ricos y simplemente se copian no se mencionan expl citamente en esta salida Asimismo si existe alg n error en el fichero de esquema la salida del compilador proporcionar informaci n detallada acerca del error til para corregirlo Por ejemplo si nos hubi semos saltado una coma en el paso deductivo OptEarleyCompleter escribi ndolo de la siguiente manera step OptEarleyCompleter A gt alpha B beta i j Sarboll B gt gamma jJ k Sarbol2 A gt alpha B beta i k S arboll Sarbol2 donde falta la coma entre j y Yoarbol1 obtendr amos el siguiente mensaje de error Schema File schemata OptimizedEarleyWithTree sch parser sparser ParseException La cadena j Sarboll no se corresponde con ninguno de los formatos definidos para elementos at parser sparser SchemaParser Element SchemaParser java 470 242 at launcher Main main Main java 94 Que como vemos nos apunta a la parte del esquema que hemos escrito mal Si dej ramos sin escribir el corchete que cierra el item A gt alpha B beta i j
9. ventana mostrar los resultados de los an lisis sint cticos es decir los tems obtenidos La informaci n que se muestra al cargar la gram tica es la siguiente Preparando algoritmo para gram tica este mensaje se muestra cuan do el fichero de gram tica ha sido le do con xito y se va a utilizar la gram tica para instanciar los pasos deductivos 18 pasos deductivos instanciados en 250 ms se muestra tras instan ciar los pasos deductivos indicando cu ntas instancias se han creado y el tiempo invertido en la operaci n 8 tems computados en 90 ms se muestra tras la llamada que se hace a la m quina deductiva para calcular todos los items posibles antes de analizar frases 10 Te hmm Buscar en TT cal El E E Ci element grammar C parser C schema test Nombre de archivo Archivos de tipo Todos los archivos gt Figura 2 Di logo para seleccionar un fichero de gram tica En este caso se precalculan ocho tems correspondientes a la ejecuci n de los pasos INITTER y PREDICTOR del algoritmo de Earley Gram tica preparada indica que el proceso de carga de la gram tica ha terminado con xito y que ya se pueden analizar frases con ella N tese que en el caso de gram ticas grandes como la gram tica del corpus Susanne incluida en la distribuci n utilizadas con algoritmos donde se precalculen muchos tems como el algoritmo Left Corner este mensaje y el anterior pued
10. I 10 1002 spe 904 4 Java Runtime Environment http www java com 19 5 G Sampson The Susanne corpus release 3 1994 6 Klaas Sikkel Parsing Schemata A Framework for Specification and Analysis of Parsing Algorithms Texts in Theoretical Computer Science An EATCS Series Springer Verlag Berlin Heidelberg New York 1997 20
11. P N Juan VP V vio PP Prep a NP Det un 12 Interfaz para el analizador generado 3 loj x Gram tica C GeneratedParsers TelescopioGrammar Examinar Cargar Frase Juan vio a un hombre con un telescopio Analizar v Mostrar s lo items meta Preparando algoritmo para gram tica items finales 18 pasos deductivos instanciados en 250 ms RO Leo ol 8 items computados en 90 ms IS NP P 0 8 S NP NQJuan VP vio PP Prep ay NP Det un Gram tica preparada ltemHandler restaurado en 0 ms 82 items computados en 10 ms Figura 4 Estado de la interfaz tras analizar una frase N hombre PP Prep con NP Det un S NP VP 0 8 S NP N Juan VP V vio N hombre PP Prep con NP Det un N telescopio PP Prep a NP Det un N telescopio Sino hubi semos marcado Mostrar s lo items meta habr amos obtenido una lista completa de los 82 items presentes en el ItemHandler tras la ejecuci n del algoritmo tems obtenidos S NP VP 0 0 S INP N 0 0 NP ce av VP V PP PP 1 8 VP V vio PP Prep a NP Det un N hombre PP Prep con NP Det un N telescopio S NP VP 0 8 S NP N Juan VP V vio PP Prep a NP Det un N hombre PP Prep con NP Det un N telescopio La lista de tems aparece en e
12. a gram tica EBNF que todo fichero de esquema debe seguir se muestra en la figura B donde se ha utilizado la notaci n est ndar que representa los constructos 17 Schema ElementDefinitionList OptionList StepName StepDescription goal GoalDescription ElementDefinitionList begin_elements ElementDefinition end_elements ElementDefinition element_definition OptionList begin_options Option end_options Option option key value StepName step ID StepDescription Antecedent Separator Conditions Consequent GoalDescription Antecedent Antecedent ItemDescription Separator Consequent ItemDescription ItemDescription ElementList ElementList ElementWrapper ElementWrapper ElementWrapper Element Conditions ElementList Element element Figura 5 EBNF grammar for parsing schema files opcionales entre corchetes los que se repiten cero o m s veces entre llaves y el texto literal mediante letra negrita o entrecomillado Como se puede ver existen dos s mbolos en la gram tica element y element_definition que no est n definidos Esto se debe a que su definici n podr variar dependiendo de los elementos notacionales definidos por el usuario Cuando el compilador de esquemas encuentre una cadena cualquiera sin espacios ni comas y que no pueda ser confundida con otros elementos del fichero
13. del sistema Normalmente las instalaciones de Java se encargan autom ticamente de incluir la m quina virtual en el PATH La sintaxis para ejecutar el script bajo Windows es generate lt schemaFile gt o lt outputDir gt g lt gClass gt y en sistemas Unix es generate sh lt schemaFile gt o lt outputDir gt g lt gClass gt donde El par metro obligatorio schemaFile representa la ruta absoluta o relativa al fichero de esquema de an lisis sint ctico que se quiere compilar Se proporcionan varios esquemas de ejemplo en el directorio schemata El par metro opcional outputDi r representa la ruta absoluta o relativa al di rectorio en el que se escribir el c digo generado y todos los ficheros asociados necesarios para compilarlo y ejecutarlo En el caso de que no se especifique este ltimo par metro su valor por defecto ser la ruta relativa generated El par metro opcional gClass es el nombre cualificado es decir incluyendo paquete de la clase de gram ticas que se usar para los ficheros de esquema que no especifiquen una Por defecto este par metro toma el valor grammar Con textFreeGrammar correspondiendo a una clase para gram ticas independientes del contexto A modo de ejemplo supongamos que tenemos el esquema que genera rboles sint cti cos seg n el algoritmo de Earley en un fichero c schemata OptimizedEarleyWithTree sch Aqu se muestra el fichero con todas las definiciones d
14. e los elementos que aparecen en el esquema aunque estas definiciones se podr an omitir si est n en el fichero de definiciones globales elements txt begin_elements element Symbol nonGroundFromString A RT Za ho z element RuleWrapper fromString A Za z gt A Za z element IntElement nonGroundIntElement i n element StringPosition nonGroundFromString i n element IntElement groundiIntElement 0 9 4 element StringPosition groundFromString 0 9 element SumOfIntegersExpression fromString 0 9i k element SumOfPositionsExpression fromString 0 9i k element SymbolSequence fromString alpha element SymbolSequence fromString beta element SymbolSequence fromString gamma element Dot fromString element Symbol fromString S lement SentenceLengthExpression fromString length element unification Term groundFromString empty element unification Term nonGroundFromString Sarbol1l element unification Term nonGroundFromString Sarbol2 element unification Term nonGroundFromString Sarbolfinal element unification TermConstructorExpression fromString A Za z0 9 gt element unification TermConstructorExpression addTreeExpressionFromString su A Za z0 9 gt 7 element unification TermConstructorExpression fromString A Za z0 9 3 end_elements
15. el c digo generado de manera que las clases definidas por el usuario pueden ser parametrizadas con estas opciones Una serie de pasos deductivos expresados en el formato step NombreDelPasoDeductivo Antecedentel Antecedente2 AntecedenteN Condiciones Laterales Consecuente Una serie de metas o tems finales expresados en el formato goal temFinal El sistema compilar a c digo Java cualquier fichero de esquema que se ajuste a este formato N tese que las definiciones de elementos de los ficheros de esquema pueden hacer referencia no s lo a clases incluidas en la distribuci n de COMPAS sino tambi n a clases Java definidas por el propio usuario proporcionando un mecanismo de extensibilidad que permite que cualquier tipo de objeto pueda aparecer en un esquema Agradecimientos Parcialmente financiado por MEC y FEDER TIN2004 07246 C03 HUM2007 66607 C04 Xunta de Galicia PGIDITO7SIN005206PR PGIDITO5PXIC 10501PN PGIDITO5PXIC30501PN INCITEO8PXIB302179PR INCITEO8E1R104022ES Rede Ga lega de Procesamento da Linguaxe e Recuperaci n de Informaci n Axudas para a Consolidaci n e Estruturaci n de Unidades de Investigaci n Xunta de Galicia Referencias 1 Apache Ant http 7 ant apache org 2 COMPAS COMpiler for PArsing Schemata website 3 Carlos G mez Rodr guez Jes s Vilares and Miguel A Alonso A compiler for parsing schemata Software Practice and Experience 2008 DO
16. en tardar segundos en aparecer Una vez terminada de cargar la gram tica ya podemos utilizar el algoritmo de an lisis sint ctico para analizar frases Para ello basta con teclear la frase que se desea analizar en el campo Frase y pulsar Analizar Los tems obtenidos como resultado se mostrar n en el rea de texto de la parte inferior derecha de la ventana Antes de pulsar Analizar puede ser interesante cambiar la opci n de la casilla Mostrar s lo tems meta Si esta casilla no est marcada el rea de texto mostrar todos los tems que se obtengan en el proceso deductivo de an lisis sint ctico mientras que si est marcada s lo aparecer n los tems finales es decir los que cumplan las condiciones de meta goa1 que representan an lisis sint cticos completos para la oraci n de entrada Si analizamos la frase Juan vio a un hombre con un telescopio con la casilla Mostrar s lo tems meta la ventana nos queda tal y como se muestra en la figura f 11 Interfaz para el analizador generado i loj xj Gram tica CiGeneratedParsersiTelescopioGrammar Examinar Cargar Frase Analizar 7 Mostrar s lo items meta Preparando algoritmo para gram tica 18 pasos deductivos instanciados en 250 ms 8 items computados en 90 ms Gram tica preparada Figura 3 Estado de la interfaz tras cargar la gram tica La informaci n de estado q
17. ia b sica sobre este formalismo se recomienda consultar 6 Para una descripci n de alto nivel del sistema COMPAS que incluye una introducci n a los esquemas de an lisis sint ctico v ase 3 La web de COMPAS donde se puede consultar informaci n actualizada sobre el sistema es 2 2 Condiciones de uso El sistema COMPAS se distribuye como software libre puede ser redistribuido y o modificado bajo los t rminos de la Licencia P blica General GNU GNU General Public License versi n 3 publicada por la Free Software Foundation Este programa se distribuye con la esperanza de que sea til pero SIN NINGUNA GARANT A incluso sin la garant a impl cita de COMERCIABILIDAD o IDONEIDAD PARA UN PROP SITO EN PARTICULAR Vea la Licencia P blica General GNU para obtener m s detalles El texto de la licencia se puede encontrar en la distribuci n de COMPAS o bien en http www gnu org licenses 3 Requisitos del sistema El sistema COMPAS est escrito en lenguaje Java y por lo tanto se puede ejecutar en cualquier sistema para el que haya disponible una m quina virtual Java JVM est ndar En la fecha de escritura de este manual estos sistemas incluyen Windows 98 2000 XP Vista Linux Mac OS X y Solaris Los requisitos para la ejecuci n del sistema son los siguientes Debe estar instalado un entorno de ejecuci n Java JRE que implemente la versi n 1 4 o superior de las APIs de Java 2 Standard Edition J2SE 4 A
18. l funcionar sobre la m quina virtual Java el sistema podr ejecutarse en cualquier plataforma que disponga de dicho JRE El compilador no tiene requisitos significativos de memoria y CPU por lo que puede funcionar en cualquier sistema capaz de ejecutar el mencionado JRE Los requisitos de memoria y CPU del c digo generado ser n diferentes para cada algoritmo y variar n seg n el tipo de gram ticas y de oraciones que se analicen Es necesario un compilador de lenguaje Java para compilar las implementaciones generadas y obtener versiones ejecutables Aunque no es estrictamente necesario es recomendable para mayor comodidad tener instalado el sistema de construcci n Apache Ant 1 que permitir compilar con mayor facilidad el c digo generado 4 Compilaci n de un esquema El compilador de esquemas de an lisis sint ctico viene precompilado en esta distri buci n en el directorio build el c digo fuente completo tambi n se incluye en la distribuci n en el directorio src Con el prop sito de facilitar el uso del compilador de esquemas se han proporcio nado dos scripts que lo ejecutan bajo sistemas Windows y UNIX generate bat y generate sh En ambos casos para ejecutar el compilador debemos situarnos primero en el directorio build que contiene estos scripts Para que los scripts funcionen el directorio que contiene los ejecutables de la m quina virtual Java JRE debe formar parte de la variable de entorno PATH
19. l orden en que han sido generados pero esto no implica necesariamente que los tems meta aparezcan al final de hecho en este caso concreto el ltimo tem es final pero el pen ltimo no y el otro tem final aparece m s arriba en la lista En situaciones en las que s lo interesen los tems meta por lo tanto ser interesante marcar la opci n Mostrar s lo tems meta para no tener que buscarlos entre el resto de tems generados 13 6 2 Ejecuci n mediante l nea de comandos Si en lugar de utilizar el interfaz gr fico queremos hacer uso del interfaz de l nea de comandos para ejecutar nuestro algoritmo de an lisis tendremos que hacer cd c generatedparsers earleytree build y a continuaci n java test ParserConsole Con lo cual se abrir una l nea de comandos en la que podemos teclear distintas rdenes para utilizar nuestro analizador Si introducimos HELP obtendremos una lista de los comandos disponibles Valid commands LOAD lt path to grammar file gt PARSE fsn lt sentence gt EXEC lt script file to execute gt DUMP fn lt path to file to dump results to gt PARSEFILE lt file to parse gt lt file to dump results to gt EXIT La funci n de los comandos es la siguiente LOAD lt fichero gram tica gt Carga la gram tica del fichero dado del mismo modo que se pod a hacer con el campo de texto gram tica en el interfaz gr fico La consola nos proporcionar
20. la misma informaci n sobre el progreso de la carga de la gram tica que aparec a en la parte izquierda de dicho interfaz PARSE fsn lt oraci n gt Analiza sint cticamente la oraci n dada Si no se especifica ninguna opci n en el campo sn el programa mostrar la lista de todos los tems generados en el an lisis Si se especifica alguna de las opciones el comportamiento es el siguiente e Opci n f se muestran s lo los items meta e Opci n n no se muestran tems simplemente se dan estad sticas sobre el n mero de tems generados en el an lisis y el tiempo invertido en l e Opci n s opci n silenciosa no se muestra nada por la consola N tese que los resultados se guardan aunque no se muestren y pueden volcarse a un fichero m s adelante DUMP fs lt fichero gt Vuelca los resultados de la ltima oraci n analizada a un fichero Siempre se escriben en dicho fichero resultados estad sticos sobre tiempo de ejecuci n y n mero de tems generados Adicionalmente y de forma an loga al comando PARSE E e Si no se especifica opci n f ni s se vuelca la lista completa de tems generados en el an lisis e Opci n n no se vuelca la lista de tems 14 e Opci n f se vuelcan s lo los tems finales Los ficheros generados con el comando DUMP tienen el siguiente aspecto BEGINNING OF TEST RESULTS Test executed at Fri Dec 05 17 11 18 GMT 2008 Grammar home c cg
21. nalidad til para tareas de investigaci n como experimentos en los que haya que analizar un gran n mero de oraciones A continuaci n veremos c mo podemos ejecutar el algoritmo que hemos generado a partir del esquema Earley tanto mediante el interfaz gr fico como con la l nea de comandos 6 1 Ejecuci n mediante interfaz gr fico Para ejecutar el interfaz gr fico que nos permitir probar el algoritmo de Earley hacemos cd c generatedparsers earleytree build y a continuaci n java test Parserlnterface Con lo cual se nos abrir una sencilla ventana como la de la figura 1 permitiendo ejecutar el analizador sint ctico generado N tese que el interfaz de usuario es intencionadamente sencillo pues su finalidad es simplemente la de facilitar al dise ador de algoritmos de an lisis sint ctico la prueba y prototipado de diferentes esquemas En un sistema de procesamiento del lenguaje natural real el an lisis sint ctico se ejecuta en background entregando su salida a o interaccionando con un analizador sem ntico que nos proveer a del significado de las frases a analizar y que a su vez entregar a su salida a o interaccionar a con otros m dulos de an lisis del lenguaje Para este tipo de interacciones o para experimentos complejos que requieran el an lisis de grandes cantidades de oraciones es m s adecuado el interfaz basado en l nea de comandos que se describe en la siguiente subsecci n Lo primero que
22. neratedparsers earleytree dist jar Building jar C generatedparsers earleytree dist MyProject 20050619 jar BUILD SUCCESSFUL Total time 5 seconds En el caso de no tener instalado el sistema de compilaci n ant que se puede descargar gratuitamente de http ant apache org el c digo generado tambi n puede compilarse a mano mediante cualquier compilador de Java 6 Ejecuci n del c digo generado La compilaci n del c digo generado mediante la herramienta ant genera dos di rectorios m s dentro de C generatedparsers earleytree adem s del src que ya ten amos el directorio build que contiene los bytecodes de las clases Java que implementan el algoritmo de Earley y el directorio di st que contiene las mismas clases empaquetadas en un fichero jar Java Archive Para ejecutar el c digo generado COMPAS proporciona dos interfaces distintos un interfaz gr fico y uno basado en l nea de comandos El interfaz gr fico es el m s c modo y sencillo de usar y por lo tanto adecuado para hacer pruebas y ejecuciones puntuales de algoritmos El interfaz de l nea de comandos proporciona funcionalidad m s avanzada como analizar muchas oraciones de un mismo fichero con un solo comando o incluso ejecutar miniprogramas scripts que pueden contener distintas rdenes de an lisis sint ctico referidas a diferentes ficheros Por lo tanto el interfaz de l nea de comandos es el m s completo proporcionando funcio
23. normal de Chomsky nvgrammar Peque a gram tica de juguete que sirve para analizar oraciones de la forma nombre verbo toytag trees xml Una gram tica de adjunci n de rboles sencilla con frases nomi nales y verbales testtag Gram ticas de adjunci n de rboles autom ticamente generadas que pueden ser utilizadas para probar el rendimiento de los analizadores para este formalismo Esquemas de an lisis CYKRecognizer sch Un analizador CYK para gram ticas independientes del con texto en forma normal de Chomsky CYKVariant sch Una manera diferente de expresar el mismo analizador CYK denotando las reglas de la gram tica mediante tems 16 CYKAnyGrammarkRecognizer sch Lo mismo que CYKRecognizer pero este es quema hace referencia a una clase de gram ticas que se encarga de transformar la gram tica de entrada a la forma normal de Chomsky autom ticamente si es que no cumple ya las restricciones de esta forma normal CYKWithTree sch Analizador CYK que genera rboles sint cticos para las oracio nes SimpleEarleyRecognizer sch Un reconocedor de tipo Earley tal como aparece descrito en el libro de esquemas de an lisis sint ctico de Sikkel 6 OptimizedEarleyRecognizer sch Una versi n del reconocedor Earley que incorpo ra una optimizaci n mediante t cnicas de unrolling para que la indexaci n de tems resulte un poco m s r pida OptimiedEarleyWithTree sch Un analizador estilo Earley
24. o repetir dichos experimentos cuando se desee o con distintos analizadores ya que todos los analizadores generados por COMPAS tienen la misma interfaz de l nea de comandos EXIT Comando utilizado para salir de la interfaz de l nea de comandos del analizador 15 7 Ejemplos proporcionados con la distribuci n La distribuci n de COMPAS incluye diferentes ejemplos de esquemas de an lisis y de gram ticas que se pueden utilizar para probar el sistema o como punto de partida para la elaboraci n de esquemas propios Son los siguientes Gram ticas SusanneGrammar Gram tica completa del ingl s extra da del corpus Susanne 5 SusanneChomsky La misma gram tica en forma normal de Chomsky para su uso en analizadores de tipo CYK SusanneTestSetTerminals txt Conjunto de oraciones de prueba generadas au tom ticamente para la gram tica Susanne aviso esto NO es una gram tica aun que por conveniencia se incluya en el directorio correspondiente a gram ticas TelescopioGrammar Gram tica muy simple para la oraci n ambigua Juan vio a un hombre con un telescopio que se puede ver en el ejemplo anterior TelescopioGrammarChomsky La misma gram tica transformada a forma normal de Chomsky Parentesis Gram tica que define el lenguaje de las cadenas de par ntesis equilibra das o lenguaje de Dyck donde los par ntesis se representan mediante las palabras Ly R ParenChomsky La misma gram tica en forma
25. que genera rboles sint cticos para las oraciones LCStandard sch Un analizador de tipo left corner ste es el analizador llamado LC descrito en 6 En esta implementaci n se utilizan tems para representar las relaciones left corner usadas por el algoritmo LCSimplifiedItems sch Un analizador left corner optimiado ste es el esquema que se llama sLC en 6 LCWithPredicates sch Una implementaci n alternativa del analizador left corner donde se usan predicados en lugar de tems para representar las relaciones left corner TopDown sch Un analizador descendente simple e ineficiente EarleyN VPforXTAG sch Un analizador para gram ticas de adjunci n de rboles adaptado para su uso con la gram tica inglesa XTAG incluyendo unificaci n de estructuras de rasgos y varias caracter sticas espec ficas para esta gram tica Lyon sch Analizador sint ctico con correcci n de errores de Lyon que usa una cola de prioridad como agenda Construyendo nuevos esquemas de an lisis sint ctico Hasta el momento se ha mostrado el uso del sistema COMPAS mediante la compila ci n de los esquemas de ejemplo que se incluyen en su distribuci n En esta secci n se describe c mo crear un fichero de esquema compilable mediante COMPAS La notaci n que COMPAS utiliza para describir los esquemas es muy sencilla coinci diendo pr cticamente con la notaci n formal con la que se suelen definir en la teor a Concretamente l
26. ue aparece en el rea de texto izquierda es la siguiente ItemHandler restaurado en 0 ms este mensaje indica que la clase encarga da de almacenar tems ItemHandler ha sido restaurada al estado en que estaba inmediatamente despu s de cargar la gram tica Esta restauraci n de estado se hace siempre antes de analizar una frase pues por un lado no nos interesa que los tems que se calcularon en an lisis anteriores sigan en el conjunto de tems pudiendo producir resultados incorrectos pero por otro lado s nos interesa que est n inicialmente presentes los tems que se precalculan al cargar la gram tica sin tener que calcularlos otra vez De ah que almacenemos estos tems en memoria recuper ndolos r pidamente antes de cada an lisis 82 tems computados en 10 ms Este mensaje se muestra una vez termi nado el an lisis cosa que puede llevar un tiempo significativo dependiendo obviamente de la gram tica frase y algoritmo utilizados Informa del tiempo de ejecuci n del algoritmo y del n mero total de tems generado Este c mputo de tems incluye tambi n los que se calculan al cargar la gram tica y que han sido simplemente copiados En el rea de texto de la derecha se nos muestran los tems finales obtenidos de la ejecuci n del algoritmo que en este caso contienen los dos rboles sint cticos v lidos que el algoritmo de Earley obtiene para la frase de entrada tems finales S NP VP 0 8 S N
Download Pdf Manuals
Related Search