Please use this identifier to cite or link to this item: http://hdl.handle.net/10553/72949
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.
URI: http://hdl.handle.net/10553/72949
ISBN: 3-540-41687-0
978-3-540-41687-6
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

SCOPUSTM   
Citations

1
checked on Sep 20, 2020

WEB OF SCIENCETM
Citations

1
checked on Sep 20, 2020

Page view(s)

20
checked on Sep 20, 2020

Google ScholarTM

Check

Altmetric


Share



Export metadata



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