Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.10 No.3, pp.369-385 (September 1994)
A New Algorithm for Deterministic Parsing and
Its Application to Grammar and Style Ghecking

Rey-Long and Von-Wun Soo
Institute of Computer Science
National Tsing Hua University
Hsinchu, Taiwan, R.O.C.

In this paper, the applicability of determinism to grammar and style checking is investigated. In grammar checking, a deterministic parser is better than a nondeterministic parser in that its parsing failure directly reflects the existence of grammatical errors. In style checking, determinism is one of the criteria for checking the readability of a sentence. A sentence that cannot be deterministically parsed might not be easily understood by human beings either. However, since contemporary algorithms for deterministic parsing have weaknesses in efficiency and extensibility, we propose a new algorithm to perform grammar and style checking. Its basic data structures and parsing operators come from Marcus' parsing while the method for rule activation is modified from LR parsing. The universal feature instantiation principles in Generalized Phrase Structure Grammar are incorporated to direct the flow of both syntactic and thematic information during parsing. No deterministic parsing rules (as in Marcus' parsing) and parsing tables (as in LR parsing) are constructed before parsing. Instead, a general conflict resolution mechanism is employed to resolve ambiguities during parsing. We show how the algorithm improves the efficiency of grammar checking and the performance of style checking.

Keywords: deterministic parsing; Marcus' parsing; LR parsing; conflict resolutlion; generalized phrase structure grammar

Received December 3, 1992; revised March 5, 1994.
Communicated by Wen-Hsiang Tsai.