JISE


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


Journal of Information Science and Engineering, Vol. 10 No. 3, pp. 369-385


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

  Retrieve PDF document (JISE_199403_04.pdf)