Bottom-Up Parsing Extending Context-Freeness in a Process Grammar Processor

BOTTOM-UP PARSING EXTENDING CONTEXT-FREENESS IN A PROCESS GRAMMAR PROCESSOR Massimo Marino Department of Linguistics - University of Pisa Via S. Maria 36 1-56100 Pisa - ITALY Bitnet: massimom@icnucevm.cnuce.cnr.it ABSTRACT A new approach to bottom-up parsing that extends Augmented Context-Free Grammar to a Process Grammar is formally presented. A Process Grammar (PG) defines a set of rules suited for bottom-up parsing and conceived as processes that are applied by a P G Processor. The matching phase is a crucial step for process application, and a parsing structure for efficient matching is also presented. The PG Processor is composed of a process scheduler that allows immediate constituent analysis of structures, and behaves in a non-deterministic fashion. On the other side, the PG offers means for implementing spec~c parsing strategies improving the lack of determinism innate in the processor. 1. INTRODUCTION Bottom-up parsing methods are usually preferred because of their property of being driven from both the input's syntactic/semantic structures and reduced constituents structures. Different strategies have been realized for handling the structures construction, e.g., parallel parsers, backtracking parsers, augmented context- free parsers (Aho et al., 1972; Grishman, 1976; Winograd, 1983). The aim of this paper is to introduce a new approach to bottom-up parsing starting from a well known and based framework - parallel bottom-up parsing in immediate constituent analysis, where all possible parses are considered - making use of an Augmented Phrase-S tructure Grammar (APSG). In such environment we must perform efficient searches in the graph the parser builds, and limit as much as possible the building of structures that will not be in the final parse tree. For the efficiency of the search we introduce a Parse Graph Structure, based on the def'mition of adjacency of the subtrees, that provides an easy method of evaluation for deciding at any step whether a matching process can be accomplished or not. The control of the parsing process is in the hands of an APSG called Process Grammar fPG), where grammar rules are conceived as processes that are applied whenever proper conditions, detected by a process scheduler, exist. This is why the parser, called PG Processor, works following a non- deterministic parallel strategy, and only the Process Grammar has the power of altering and constraining this behaviour by means of some Kernel Functions that can modify the control structures of the PG Processor, thus 299 improving determinism of the parsing process, or avoiding construction of useless structures. Some of the concepts introduced in this paper, such as some definitions in Section 2, are a development from Grishman (1976) that can be also an introductory reading regarding the description of a parallel bottom-up parser which is, even if under a different aspect, the core of the PG Processor. 2. PARSE GRAPH STRUCTURE The Parse Graph Structure (PGS) is built by the parser while applying grammar rules. If s = a a a2... a is an input string the initial PGS is composed by a set of terminal nodes <0,$>, <l,aa>, <2,a2> ..... <n,a >, …

Content truncated to 500 words