On Formalizations of Marcus’ Parser

ON FORMALIZATIONS OF MARCUS' PARSER R. Nozoboor-Farshi Dept. of Computing Science, University of Alberta, Edmonton, Canada T6G 2H1 Abstract: LR(k,t), BCP(m,n) and LRRL(k) grammars, and their relations to Marcus parsing are discussed. 1. Introduction In his 1JCA1-83 paper [1], R.C. Berwick suggested that the stripped down version of Marcus' parser [4] (i.e., with no features or transformations) can be formally characterized by LR(k,t) parsers [7,8]. Berwick's COLING-84 paper [2] seems to suggest that Marcus-style parsers may be adequately formalized by bounded context parsable BCP(m,n) grammars[8,9]. In this paper we show that both classes of LR(k,t) and BCP(m,n) grammars are inadequate means to formalize Marcus' mechanism even when it is applied to parsing bare context-free grammars. We briefly describe a new class of unambiguous context-free grammars, LRRL(k), for which deterministic non-canonical bottom-up table driven parsers are generated automatically. These parsers employ k-symbol fully reduced right context in making parsing decisions. LRRL(k) grammars include as a subset tho;;e context-free grammars that arc parsablc by Marcus' partially top°down method. 2. Operation of Marcus' parser Let us first recall that Marcus' parser has two data structures: a pushdown stack which holds the constructs yet to be completed, and a finite size buffer which holds the lookahead symbols. The lookaheads can be completed constructs as well as bare terminals. I n addition, the parser has three basic operations: (1) Attach: attaches a constituent in the buffer to the current active node (stack top). (2) Create (push): creates a new active node, i.e., when the parser decides thai Ihe first constituent(s) in the buffer begin a new higher constituent, a new node of the specified type is created and pushed on the stack. However the create operation has a second mode in which the newly created node is first attached to the old active node, and then pushed on the stack. Marcus indicates this by use of "attach a new node of 'type' to active node" in the grammar rules. Following Ritchie [6], we use a shorter notation: 'cattach' for this second mode. (3) Drop (pop): pops the top node of the stack (CAN). However if this node is not attached to a higher level node, it will be dropped in the first position of the window defined on the buffer. Marcus uses different notations, namely "drop" and "drop into buffer", in the grammar to indicate the etTect of drop operations. This suggests that a grammar writer must be aware of the attachment of the current active node. Here, we adhere to his provision about differentiating between these two modes of drop operations. However we feel that there is no need for such a provision since PARSIFAl_. (the grammar interpreter) can take care of that by inserting an unattached node into the buffer, and the grammar can test the contents of the buffer to see if such insertion has taken place. The three basic operations plus "attention shift" and "restore buffer" (forward and backward window movements on the buffer) are sufficient for parsing some context-free grammars …

Content truncated to 500 words