Paper: Context-Freeness Of The Language Accepted By Marcus' Parser

ACL ID P87-1017
Title Context-Freeness Of The Language Accepted By Marcus' Parser
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1987

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. 1. In~u~on While Marcus [4] does not use phrase mucture rules as base grammar in his parser, he points out some correspondence between the use of a base rule and the way packets are acuvated to parse a constmcu Chamlak [2] has also assumed some phrase structure base ~ 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 IX(k.0 context-free grammars. Similarly, in ...