Please use this identifier to cite or link to this item:
Title: Practical nondeterministic DR(k) parsing on graph-structured stack
Authors: Fortes Gálvez, José 
Farre, J
Pérez Aguiar, Miguel Ángel 
UNESCO Clasification: 1203 Ciencia de los ordenadores
Issue Date: 2001
Journal: Lecture Notes in Computer Science 
Conference: 2nd International Conference on Intelligent Text Processing and Computaional Linguistics (CICLing 2001) 
Abstract: A new approach to parse context-free grammars is presented. It relies on discriminating-reverse, DR(k), parsers, with a Tomita-like nondeterminism-controlling graph-structured stack (GSS) algorithm.The advantage of this generalized discriminating-reverse (GDR) approach over GLR lies 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 can greatly reduce nondeterminism originating from limited parsing power, as it is typical of the restricted direct LR parsers (SLR, LALR) commonly used in Tomita's algorithm.Furthermore, relying on a DR parser allows a GSS that associates nodes to symbols instead of direct-LR states, and makes easier computation of the shared forest.Moreover, DR(k) parsers have been shown to be linear for LR(k) grammars, and the DR(k) parser efficiency has been practically found to be very similar to direct LR(k) parsers.The paper first presents the nondeterministic DR(k) generation algorithm (for non-LR(k) grammars). Then, it discusses the corresponding adaptation of the GSS algorithm and shows how the shared forest computation is naturally handled.
ISBN: 3-540-41687-0
ISSN: 0302-9743
DOI: 10.1007/3-540-44686-9_40
Source: Lecture Notes in Computer Science [ISSN 0302-9743], v. 2004, p. 411-422, (2001)
Appears in Collections:Actas de congresos
Show full item record


checked on Jul 25, 2021


checked on Jul 25, 2021

Page view(s)

checked on Jul 24, 2021

Google ScholarTM




Export metadata

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