|Title:||Towards a discriminating-reverse Tomita-like parser with reduced nondeterminism||Authors:||Fortes Gálvez, José
|UNESCO Clasification:||1203 Ciencia de los ordenadores||Issue Date:||2000||Journal:||Procesamiento de Lenguaje Natural||Abstract:||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||Source:||Procesamiento del lenguaje natural [ISSN 1135-5948], (26), p. 111-118||URL:||http://dialnet.unirioja.es/servlet/articulo?codigo=1011593|
|Appears in Collections:||Artículos|
checked on Dec 10, 2022
Items in accedaCRIS are protected by copyright, with all rights reserved, unless otherwise indicated.