Please use this identifier to cite or link to this item:
Title: Towards a discriminating-reverse Tomita-like parser with reduced nondeterminism
Authors: Fortes Gálvez, José 
Farré, Jacques
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.
ISSN: 1135-5948
Source: Procesamiento del lenguaje natural [ISSN 1135-5948], (26), p. 111-118
Appears in Collections:Artículos
Show full item record

Page view(s)

checked on Dec 10, 2022

Google ScholarTM



Export metadata

Items in accedaCRIS are protected by copyright, with all rights reserved, unless otherwise indicated.