A SHIFT-FIRST STRATEGY FOR INTERLEAVED LR PARSING

Tomita's parsing method (GLR) is a practical and successful parsing me thod 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 f or a fast real-time parsing. In this paper, we present a method which makes the GLR adaptable to interleaved ed parsing while making some li mitation on its generality. For interleaved parsing, the conflicts of the LR parsing table must be resolved at the parse time. The shift-red uce conflict among the above conflicts is the most serious one for int erleaved parsing because of the lack of knowledge for the conflict res olution at the parse time. Therefore, we concentrate on resolving a sh ift-reduce conflict by introducing a grammar which is called a shift-f irst LR(k) grammar. Our method for this is that the conflict resolutio n is delayed by the shift-first strategy which makes an unconditional choice of shift actions in the case of a shift-reduce conflict.