A speeding-up method of parsing-stack operations for LR parsers

Author

Hayashi, Yoshitaka ; Mochizuki, Hisatoshi ; Shishibori, Masami ; Aoe, Jun-Ichi

Author_Institution

Dept. of Inf. Sci. & Intelligent Syst., Tokushima Univ., Japan

Volume

1

fYear

1996

fDate

14-17 Oct 1996

Firstpage

619

Abstract

This paper presents a new method of LR parsing based on the distinction of stack states and non-stack states. Non-stack states are states which do not need to be pushed into the LR parsing stack and stack states are states to be pushed into it. By using some of the properties based on the stack-controlling LR parser defined, the parsing speed and the size of parsing tables can be improved, and the improvement includes the traditional method eliminating unit productions. By empirical observations for variety of programming languages, the efficiency is verified. An extension of the method to the generalized LR parsers for natural language is also discussed

Keywords

computational linguistics; context-free grammars; natural languages; programming languages; trees (mathematics); LR parsers; natural language; parsing-stack operations; programming languages; speeding-up method; stack states; syntax trees; Computer languages; Information science; Intelligent systems; Natural languages; Production; Stacking; Vocabulary;

fLanguage

English

Publisher

ieee

Conference_Titel

Systems, Man, and Cybernetics, 1996., IEEE International Conference on

Conference_Location

Beijing

ISSN

1062-922X

Print_ISBN

0-7803-3280-6

Type

conf

DOI

10.1109/ICSMC.1996.569864

Filename

569864