Identificador persistente para citar o vincular este elemento: http://hdl.handle.net/10553/56747
Título: Towards a discriminating-reverse Tomita-like parser with reduced nondeterminism
Autores/as: Fortes Gálvez, José 
Farré, Jacques
Clasificación UNESCO: 1203 Ciencia de los ordenadores
Fecha de publicación: 2000
Publicación seriada: Procesamiento de Lenguaje Natural
Resumen: A new approach to generalized parsing for context-free grammars is presented, which uses an underlying discriminating-reverse, DR(k), parser with a Tomita-like nondeterminism-controlling graph-structured stack, GSS, algorithm. The advantage of the new generalized discriminating-reverse, GDR, approach over GLR would lie on the possibility of using DR(k) parsers, which combine full LR(k) parsing power with a small number of states even for k > 1. This may allow to greatly reduce nondeterminism originating from limited parsing power (as it is typical of the restricted form of (direct) LR parsers currently used in Tomita algorithm) and to a further simplification of the GSS by associating nodes to symbols instead of direct-LR states. Moreover, DR(k) parsing time complexity has been shown to be linear for LR(k) grammars, and DR(k) parser efficiency has been practically found to be very similar to direct LR(k) parsers. The paper shows the nondeterministic DR(k) generation algorithm (for non-LR(k) grammars) and the corresponding adaptation of the GSS algorithm.
URI: http://hdl.handle.net/10553/56747
ISSN: 1135-5948
Fuente: Procesamiento del lenguaje natural [ISSN 1135-5948], (26), p. 111-118
URL: http://dialnet.unirioja.es/servlet/articulo?codigo=1011593
Colección:Artículos
Vista completa

Google ScholarTM

Verifica


Comparte



Exporta metadatos



Los elementos en ULPGC accedaCRIS están protegidos por derechos de autor con todos los derechos reservados, a menos que se indique lo contrario.