Registro:
| Documento: | Tesis de Grado |
| Título: | Extensión del algoritmo de Earley a gramáticas MGIG, con aplicación como SAT-solver |
| Título alternativo: | An extension of Earley's algorith to MGIG grammars, with an application as SAT-solver |
| Autor: | Gutiérrez, Agustín Santiago |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2023-09-12 |
| Fecha de defensa: | 2016-12-06 |
| Fecha en portada: | 2016 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Director: | Castaño, José |
| Idioma: | Español |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000466_Gutierrez |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000466_Gutierrez.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000466_Gutierrez |
| Ubicación: | Dep.COM 000466 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Gutiérrez, Agustín Santiago. (2016). Extensión del algoritmo de Earley a gramáticas MGIG, con aplicación como SAT-solver. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000466_Gutierrez |
Resumen:
El algoritmo de Earley es un algoritmo de parsing no determinístico general, capaz de reconocer eficientemente cualquier gramática libre de contexto. Es bien sabido que estas gramáticas no pueden expresar muchos lenguajes de interés, como aquellos que impliquen reconocer variables de un lenguaje de programación previamente declaradas, o en general aquellos cuya definición incorpore restricciones de interdependencias cruzadas entre tokens, como es el caso del lenguaje de instancias satisfacibles del problema SAT. Con el objetivo de modelar algunos lenguajes con ese tipo de restricciones, se propone una extensión de las gramáticas libres de contexto, las MGIG. Las MGIG son un nuevo formalismo de gramática, basado en las GIG, que extiende las gramáticas libres de contexto utilizando una estructura de datos auxiliar llamada multistack, que es manipulada durante una leftmost-derivation y permite modelar ciertas restricciones cruzadas. El algoritmo de Earley se modifica acorde a la nueva gramática, incorporando la estructura de datos a los ítems que genera el algoritmo y modificando sus pasos para reconocer las MGIG. El objetivo principal de esta tesis radica en la implementación de un algoritmo de reconocimiento del lenguaje generado por una MGIG, basado en el algoritmo de Earley. Una vez implementado, verificamos el desempeño del mismo con diferentes parámetros y variantes posibles sobre el ejemplo motivador de SAT, para compararlo con otros enfoques existentes para resolver el problema SAT.
Abstract:
The Earley parser is a general non-deterministic algorithm that efficiently parses any given context free grammar. It is a well known fact that these grammars cannot express many languages of interest, such as those that imply the recognition of previously declared variables in a programming language, or more generally, any language such that its definition involves crossing dependencies among tokens, such as the language of satisfiable instances of SAT. With the aim of modeling some languages having such crossing dependencies, we propose an extension of context-free grammars, the MGIG. MGIG are a new grammar formalism, based on the previously existing GIG, that extends context free grammars by using an auxiliary data structure called a multistack, which is manipulated during a leftmost derivation, and enables the modeling of certain crossing dependencies. Earley’s algorithm is modified according to the new grammar, by incorporating the data structure to the items generated by the algorithm, and by modifying its operations in order to recognize an MGIG. The main aim of this thesis is the implementation of a recognition algorithm for MGIG, based on the Earley parser. Once implemented, we verify its performance under different sets of parameters on the motivating example of the SAT language, in order to compare it with other existing SAT-solvers.
Citación:
---------- APA ----------
Gutiérrez, Agustín Santiago. (2016). Extensión del algoritmo de Earley a gramáticas MGIG, con aplicación como SAT-solver. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000466_Gutierrez
---------- CHICAGO ----------
Gutiérrez, Agustín Santiago. "Extensión del algoritmo de Earley a gramáticas MGIG, con aplicación como SAT-solver". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2016.https://hdl.handle.net/20.500.12110/seminario_nCOM000466_Gutierrez
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000466_Gutierrez.pdf
Distrubución geográfica
