A Shift First Strategy for Generalized LR Parsing

Yong-Seok LEE; Hideto TOMABECHI; Jun-ichi AOE

A Shift First Strategy for Generalized LR Parsing

Yong-Seok LEE, Hideto TOMABECHI, Jun-ichi AOE

Full Text Views

0

Cite this

Summary :

Tomita's parsing method (GLR) is a practical and successful parsing method for natural language. However, one difficulty in the GLR is that interleaved constraint processing of syntax and semantics in parallel is not trivial during parsing, because it uses the precompiled table for a fast real-time parsing. In this paper, we present a method which makes the GLR adaptable to interleaved parsing while making some limitation on its generality. For interleaved parsing, the conflicts of the LR parsing table must be resolved at the parse time. The shift-reduce conflict among the above conflicts is the most serious one for interleaved parsing because of the lack of knowledge for the conflict resolution at the parse time. Therefore, we concentrate on resolving a shift-reduce conflict by introducing a grammar which is called a shift-first LR (k) grammar. Our method for this is that the conflict resolution is delayed by the shift-first strategy which makes an unconditional choice of shift actions in the case of a shift-reduce conflict. Then, a delayed resolution that resolves the conflict, is made. Depending on the decision of the resolution, the pseudo parsing, which parses symbols in the LR parser stack, proceeds. Our experiments showed that our parser is efficient while attaining the interleaved parsing at real time.

Publication: IEICE TRANSACTIONS on Information Vol.E77-D No.10 pp.1162-1169

Publication Date: 1994/10/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Artificial Intelligence and Cognitive Science

Cite this

Copy

Yong-Seok LEE, Hideto TOMABECHI, Jun-ichi AOE, "A Shift First Strategy for Generalized LR Parsing" in IEICE TRANSACTIONS on Information, vol. E77-D, no. 10, pp. 1162-1169, October 1994, doi: .
Abstract: Tomita's parsing method (GLR) is a practical and successful parsing method for natural language. However, one difficulty in the GLR is that interleaved constraint processing of syntax and semantics in parallel is not trivial during parsing, because it uses the precompiled table for a fast real-time parsing. In this paper, we present a method which makes the GLR adaptable to interleaved parsing while making some limitation on its generality. For interleaved parsing, the conflicts of the LR parsing table must be resolved at the parse time. The shift-reduce conflict among the above conflicts is the most serious one for interleaved parsing because of the lack of knowledge for the conflict resolution at the parse time. Therefore, we concentrate on resolving a shift-reduce conflict by introducing a grammar which is called a shift-first LR (k) grammar. Our method for this is that the conflict resolution is delayed by the shift-first strategy which makes an unconditional choice of shift actions in the case of a shift-reduce conflict. Then, a delayed resolution that resolves the conflict, is made. Depending on the decision of the resolution, the pseudo parsing, which parses symbols in the LR parser stack, proceeds. Our experiments showed that our parser is efficient while attaining the interleaved parsing at real time.
URL: https://global.ieice.org/en_transactions/information/10.1587/e77-d_10_1162/_p

Copy

@ARTICLE{e77-d_10_1162,
author={Yong-Seok LEE, Hideto TOMABECHI, Jun-ichi AOE, },
journal={IEICE TRANSACTIONS on Information},
title={A Shift First Strategy for Generalized LR Parsing},
year={1994},
volume={E77-D},
number={10},
pages={1162-1169},
abstract={Tomita's parsing method (GLR) is a practical and successful parsing method for natural language. However, one difficulty in the GLR is that interleaved constraint processing of syntax and semantics in parallel is not trivial during parsing, because it uses the precompiled table for a fast real-time parsing. In this paper, we present a method which makes the GLR adaptable to interleaved parsing while making some limitation on its generality. For interleaved parsing, the conflicts of the LR parsing table must be resolved at the parse time. The shift-reduce conflict among the above conflicts is the most serious one for interleaved parsing because of the lack of knowledge for the conflict resolution at the parse time. Therefore, we concentrate on resolving a shift-reduce conflict by introducing a grammar which is called a shift-first LR (k) grammar. Our method for this is that the conflict resolution is delayed by the shift-first strategy which makes an unconditional choice of shift actions in the case of a shift-reduce conflict. Then, a delayed resolution that resolves the conflict, is made. Depending on the decision of the resolution, the pseudo parsing, which parses symbols in the LR parser stack, proceeds. Our experiments showed that our parser is efficient while attaining the interleaved parsing at real time.},
keywords={},
doi={},
ISSN={},
month={October},}

Copy

TY - JOUR
TI - A Shift First Strategy for Generalized LR Parsing
T2 - IEICE TRANSACTIONS on Information
SP - 1162
EP - 1169
AU - Yong-Seok LEE
AU - Hideto TOMABECHI
AU - Jun-ichi AOE
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E77-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 1994
AB - Tomita's parsing method (GLR) is a practical and successful parsing method for natural language. However, one difficulty in the GLR is that interleaved constraint processing of syntax and semantics in parallel is not trivial during parsing, because it uses the precompiled table for a fast real-time parsing. In this paper, we present a method which makes the GLR adaptable to interleaved parsing while making some limitation on its generality. For interleaved parsing, the conflicts of the LR parsing table must be resolved at the parse time. The shift-reduce conflict among the above conflicts is the most serious one for interleaved parsing because of the lack of knowledge for the conflict resolution at the parse time. Therefore, we concentrate on resolving a shift-reduce conflict by introducing a grammar which is called a shift-first LR (k) grammar. Our method for this is that the conflict resolution is delayed by the shift-first strategy which makes an unconditional choice of shift actions in the case of a shift-reduce conflict. Then, a delayed resolution that resolves the conflict, is made. Depending on the decision of the resolution, the pseudo parsing, which parses symbols in the LR parser stack, proceeds. Our experiments showed that our parser is efficient while attaining the interleaved parsing at real time.
ER -