A method is presented for obtaining a simple deterministic pushdown transducer which acts as a parser for simple chain grammars. It is shown that a simple deterministic grammar can be constructed which covers the simple chain grammar. To obtain both the simple deterministic pushdown transducer and the cover result, a new type of parse is introduced which differs from the left and right parses which are common for the usual one pass no back-tracking parsing algorithms. For the simple chain grammars this parse, the so-called left part parse, follows from a simple left part property which is satisfied by the grammatical trees of simple chain grammars.
|Name||Lecture Notes in Computer Science|
|Conference||Fifth Colloquium on Automata, Languages and Programming 1978|
|Period||17/07/78 → 21/07/78|
- HMI-SLT: Speech and Language Technology