A Family of Generalized LR Parsing Algorithms Using Ancestors Table

Hozumi TANAKA; K.G. SURESH; Koichi YAMADA

A Family of Generalized LR Parsing Algorithms Using Ancestors Table

Hozumi TANAKA, K.G. SURESH, Koichi YAMADA

Full Text Views

0

Cite this

Summary :

A family of new generalized LR parsing algorithms are proposed which make use of a set of ancestors tables introduced by Kipps. As Kipps's algorithm does not give us a method to extract any parsing results, his algorithm is not considered as a practical parser but as a recognizer. In this paper, we will propose two methods to extract all parse trees from a set of ancestors tables in the top vertices of a graph-structured stack. For an input sentence of length n, while the time complexity of the Tomita parser can exceed O(n³) for some context-free grammars (CFGs), the time complexity of our parser is O(n³) for any CFGs, since our algorithm is based on the Kipps's recognizer. In order to extract a parse tree from a set of ancestors tables, it takes time in order n². Some preliminary experimental results are given to show the efficiency of our parsers over Tomita parser.

Publication: IEICE TRANSACTIONS on Information Vol.E77-D No.2 pp.218-226

Publication Date: 1994/02/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Issue on Natural Language Processing and Understanding)

Category

Cite this

Copy

Hozumi TANAKA, K.G. SURESH, Koichi YAMADA, "A Family of Generalized LR Parsing Algorithms Using Ancestors Table" in IEICE TRANSACTIONS on Information, vol. E77-D, no. 2, pp. 218-226, February 1994, doi: .
Abstract: A family of new generalized LR parsing algorithms are proposed which make use of a set of ancestors tables introduced by Kipps. As Kipps's algorithm does not give us a method to extract any parsing results, his algorithm is not considered as a practical parser but as a recognizer. In this paper, we will propose two methods to extract all parse trees from a set of ancestors tables in the top vertices of a graph-structured stack. For an input sentence of length n, while the time complexity of the Tomita parser can exceed O(n³) for some context-free grammars (CFGs), the time complexity of our parser is O(n³) for any CFGs, since our algorithm is based on the Kipps's recognizer. In order to extract a parse tree from a set of ancestors tables, it takes time in order n². Some preliminary experimental results are given to show the efficiency of our parsers over Tomita parser.
URL: https://global.ieice.org/en_transactions/information/10.1587/e77-d_2_218/_p

Copy

@ARTICLE{e77-d_2_218,
author={Hozumi TANAKA, K.G. SURESH, Koichi YAMADA, },
journal={IEICE TRANSACTIONS on Information},
title={A Family of Generalized LR Parsing Algorithms Using Ancestors Table},
year={1994},
volume={E77-D},
number={2},
pages={218-226},
abstract={A family of new generalized LR parsing algorithms are proposed which make use of a set of ancestors tables introduced by Kipps. As Kipps's algorithm does not give us a method to extract any parsing results, his algorithm is not considered as a practical parser but as a recognizer. In this paper, we will propose two methods to extract all parse trees from a set of ancestors tables in the top vertices of a graph-structured stack. For an input sentence of length n, while the time complexity of the Tomita parser can exceed O(n³) for some context-free grammars (CFGs), the time complexity of our parser is O(n³) for any CFGs, since our algorithm is based on the Kipps's recognizer. In order to extract a parse tree from a set of ancestors tables, it takes time in order n². Some preliminary experimental results are given to show the efficiency of our parsers over Tomita parser.},
keywords={},
doi={},
ISSN={},
month={February},}

Copy

TY - JOUR
TI - A Family of Generalized LR Parsing Algorithms Using Ancestors Table
T2 - IEICE TRANSACTIONS on Information
SP - 218
EP - 226
AU - Hozumi TANAKA
AU - K.G. SURESH
AU - Koichi YAMADA
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E77-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 1994
AB - A family of new generalized LR parsing algorithms are proposed which make use of a set of ancestors tables introduced by Kipps. As Kipps's algorithm does not give us a method to extract any parsing results, his algorithm is not considered as a practical parser but as a recognizer. In this paper, we will propose two methods to extract all parse trees from a set of ancestors tables in the top vertices of a graph-structured stack. For an input sentence of length n, while the time complexity of the Tomita parser can exceed O(n³) for some context-free grammars (CFGs), the time complexity of our parser is O(n³) for any CFGs, since our algorithm is based on the Kipps's recognizer. In order to extract a parse tree from a set of ancestors tables, it takes time in order n². Some preliminary experimental results are given to show the efficiency of our parsers over Tomita parser.
ER -