tailieunhanh - Báo cáo khoa học: "CONTEXT-FRKFNESS OF THE LANGUAGE ACCEPTED BY MARCUS' PARSER"

In this paper, we prove that the set of sentences parsed by M~cus' parser constitutes a context-free language. The proof is carried out by construing a deterministic pushdown automaton that recognizes those smngs of terminals that are parsed successfully by the Marcus pa~er. | CONTEXT-FREENESS OF THE LANGUAGE ACCEPTED BY MARCUS PARSER R. Nozohoor-Faxshi School of Computing Science Simon Fraser Universit Burnaby British Columbia Canada V5A 1S6 ABSTRACT In this paper we prove that the set of sentences parsed bv Marcus parser constitutes a context-free language. The proof is carried out bv constructing a deterministic pushdown automaton that recognizes those strings of terminals that are parsed successfully by the Marcus parser. 1. Inơoduction While Marcus 4J does not use phrase structure rules as base grammar in his parser be points out some correspondence between the use of a base rule and the way packets are activated to parse a construct Charniak 2 has also assumed some phrase structure base grammar in implementing a Marcus style parser that handles ungrammatical situations. However neither has suggested a type for such a grammar or the language accepted by the parser. Berwick 1 relates Marcus parser to LR k t context-free grammars. Similarly in 5 and 6 we have related this parser to LRRựk grammars. Inevitably these raise the question of whether the string set parsed by Marcus parser is a context-free language. In this paper we provide the answer for the above question by showing formally that the set of sentences accepted by Marcus parser constitutes a context-free language. Our proof is based on simulating a simplified version of the parser by a pushdown automaton. Then some modifications of the PDA are suggested in order to ascertain that Marcus parser regardless of the structures it puts on the input sentences accepts a context-free set of sentences. Furthermore since the resulting PDA is a deterministic one it confirms the determinism of die language parsed by this parser. Such a proof also provides a justification for assuming a context-free underlying grammar in automatic generation of Marcus type parsers as discussed in 5 and 5 . 2. Assumption of a finite size buffer Marcus parser employs two data structures a pushdown stack .