Chart parsing

This paper presents a method for parsing associative Lambek grammars based on graphtheoretic properties. Connection graphs, which are a simplified version of proof-nets, are actually a mere conservative extension of the earlier method of syntactic connexion, discovered by Ajduckiewicz [1935]. The method amounts to find alternating spanning trees in graphs. A sketch of an algorithm for finding such a tree is provided. Interesting properties of time-complexity for this method are expected.

8p buncha_1 08-05-2013 47 1   Download

Natural language systems based on Categorial Unification Grammar (CUG) have mainly employed bottomup parsing algorithms for processing. Conventional prediction techniques to improve the efficiency of the • parsing process, appear to fall short when parsing CUG. Nevertheless, prediction seems necessary when parsing grammars with highly ambiguous lexicons or with noncanonical categorial rules. In this paper we present a lexicalist prediction technique for CUG and show thai this may lead to considerable gains in efficiency for both bottom-up and top-down parsing. ...

6p buncha_1 08-05-2013 51 1   Download

This paper presents an algorithm for incremental chart parsing, outlines how this could be embedded in an interactive parsing system, and discusses w h y this might be useful. Incremental parsing here means that input i8 analysed in a piecemeal fashion, in particular allowing arbitrary changes of previous input without exhaustive reanalysis. Interactive parsing means that the analysis process is prompted immediately at the onset of new input, and possibly that the system then m a y interact with the user in order to resolve problems that occur. ...

8p buncha_1 08-05-2013 37 1   Download

Currently several grammatical formalisms converge towards being declarative and towards utilizing context-free phrase-structure grammar as a backbone, e.g. L F G and PATR-II. Typically the processing of these formalisms is organized within a chart-parsing framework. The declarative character of the formalisms makes it important to decide upon an overall optimal control strategy on the part of the processor. In particular, this brings the ruleinvocation strategy into criticalfocus: to gain maximal processing efficiency, one has to determine the best way of putting the rules to use.

8p buncha_1 08-05-2013 50 1   Download

We describe GLP, a chart parser that will be used as a SYNTAX module of the Erlangen Speech Understanding System. GLP realizes an agenda-based multiprocessing scheme, which allows easily to apply various parsing strategies in a transparent way. We discuss which features have been incorporated into the parser in order to process speech data, in particular the ability to perform direction independent island parsing, to handle gaps in the utterance and its hypothesis scoring scheme.

3p buncha_1 08-05-2013 36 3   Download

In this paper, we present a novel approach to integrate speech recognition and rulebased machine translation by lattice parsing. The presented approach is hybrid in two senses. First, it combines structural and statistical methods for language modeling task. Second, it employs a chart parser which utilizes manually created syntax rules in addition to scores obtained after statistical processing during speech recognition. The employed chart parser is a unification-based active chart parser. It can parse word graphs by using a mixed strategy instead of being bottom-up or top-down only.

9p bunthai_1 06-05-2013 49 2   Download

An open problem in dependency parsing is the accurate and efficient treatment of non-projective structures. We propose to attack this problem using chart-parsing algorithms developed for mildly contextsensitive grammar formalisms. In this paper, we provide two key tools for this approach. First, we show how to reduce nonprojective dependency parsing to parsing with Linear Context-Free Rewriting Systems (LCFRS), by presenting a technique for extracting LCFRS from dependency treebanks.

9p bunthai_1 06-05-2013 38 1   Download

The Context-Free backbone of some natural language analyzers produces all possible CF parses as some kind of shared forest, from which a single tree is to be chosen by a disambiguation process that may be based on the finer features of the language. We study the structure of these forests with respect to optimality of sharing, and in relation with the parsing schema used to produce them. In addition to a theoretical and experimental framework for studying these issues, the main results presented are: sophistication in chart parsing schemata (e.g.

9p bungio_1 03-05-2013 55 2   Download

We argue for the usefulness of an active chart as the basis of a system that searches for the globally most plausible explanation of failure to syntactically parse a given input. We suggest semantics-free, grammarindependent techniques for parsing inputs displaying simple kinds of ill-formedness and discuss the search issues involved.

8p bungio_1 03-05-2013 37 2   Download

A general device for handling nondeterminism in stack operations is described. The device, called a Graph-structured Stack, can eliminate duplication of operations throughout the nondeterministic processes. This paper then applies the graph-structured stack to various natural language parsing methods, including ATN, LR parsing, categodal grammar and principlebased parsing. The relationship between the graphstructured stack and a chart in chart parsing is also discussed.

9p bungio_1 03-05-2013 46 2   Download

There has recendy been a revival of interest in Categorial Grammars (CG) among computational linguists. The various versions noted below which extend pure C G by including operations such as functional composition have been claimed to offer simple and uniform accounts of a wide range of natural language (NL) constructions involving bounded and unbounded "movement" and coordination "reduction" in a number of languages. Such grammars have obvious advantages for computational applications, provided that they can be parsed efficiently.

8p bungio_1 03-05-2013 47 2   Download

A specialized transition network mechanism, the interruptable transition n e t w o r k (ITN) is used to p e r f o r m the last of three stages in a m u l t i p r o c e s s o r s y n t a c t i c parser. This approach can be seen as an exercise in implementing a parsing procedure of the active chart parser family. Most of the ATN parser implementations use the left-to-right top-down chronological backtracking control structure (cf. Bates, 1978 for discussion).

5p bungio_1 03-05-2013 48 1   Download

By exploring the relationship between parsing and deduction, a new and more general view of chart parsing is obtained, which encompasses parsing for grammar formalisms based on unification, and is the basis of the Earley Deduction proof procedure for definite clauses. The efficiency of this approach for an interesting class of grammars is discussed. 1. I n t r o d u c t i o n The aim of this paper is to explore the relationship between parsing and deduction. The basic notion, which goes back to Kowaiski (Kowalski, 1980} and Colmerauer {Colmeraucr, 1978), h'zs seen a very...

8p bungio_1 03-05-2013 34 0   Download

MCHART is a flexible, modular chart parsing framework I have been developing (in Lisp) at Edinburgh, whose initial design characteristics were largely determined by pedagogical needs. PSG is a gr---n-tical theory developed by Gerald Gazdar at Sussex, in collaboration with others in both the US and Britain, most notably Ivan Sag, Geoff Pull,--, and Ewan Klein. It is a notationally rich context free phrase structure grumm~r, incorporating meta-rules and rule schemata to capture generalisations.

6p bungio_1 03-05-2013 45 1   Download

Some linguistic constraints cannot be effectively resolved during parsing at the location in which they are most naturally introduced. This paper shows how constraints can be propagated in a memoizing parser (such as a chart parser) in much the same way that variable bindings are, providing a general treatment of constraint coroutining in memoization. Prolog code for a simple application of our technique to Bouma and van Noord's (1994) categorial grammar analysis of Dutch is provided.

8p bunmoc_1 20-04-2013 35 2   Download

We describe an efficient bottom-up parser that interleaves syntactic and semantic structure building. Two techniques are presented for reducing search by reducing local ambiguity: Limited leftcontext constraints are used to reduce local syntactic ambiguity, and deferred sortal-constraint application is used to reduce local semantic ambiguity. We experimentally evaluate these techniques, and show dramatic reductions in both number of chart edges and total parsing time.

7p bunmoc_1 20-04-2013 40 4   Download

We present an implemented unification-based parser for relational grammars developed within the s t r a t i f i e d f e a t u r e g r a m m a r (SFG) framework, which generalizes Kasper-Rounds logic to handle relational grammar analyses. We first introduce the key aspects of SFG and a lexicalized, graph-based variant of the framework suitable for implementing relational grammars. We then describe a head-driven chart parser for lexicalized SFG.

8p bunmoc_1 20-04-2013 38 2   Download

be used for efficiency by providing a best-first search heuristic to order the parsing agenda. This paper proposes an agenda-based probabilistic chart parsing algorithm which is both robust and efficient. The algorithm, 7)icky 1, is considered robust because it will potentially generate all constituents produced by a pure bottom-up parser and rank these constituents by likelihood. The efficiency of the algorithm is achieved through a technique called probabilistic prediction, which helps the algorithm avoid worst-case behavior. ...

8p bunmoc_1 20-04-2013 36 2   Download

A language processor is to find out a most promising sentence hypothesis for a given word lattice obtained from acoustic signal recognition. In this paper a new language processor is proposed, in which unification granunar and Markov language model are integrated in a word lattice parsing algorithm based on an augmented chart, and the island-driven parsing concept is combined with various preference-first parsing strategies defined by different construction principles and decision rules.

6p bunmoc_1 20-04-2013 46 2   Download

Efficient syntactic and semantic parsing for ambiguous context-free languages are generally characterized as complex, specialized, highly formal algorithms. In fact, they are readily constructed from straightforward recursive Iransition networks (RTNs). In this paper, we introduce LR-RTNs, and then computationally motivate a uniform progression from basic LR parsing, to Earley's (chart) parsing, concluding with Tomita's parser. These apparently disparate algorithms are unified into a single implementation, which was used to automatically generate all the figures in this paper. 1.

8p bunmoc_1 20-04-2013 55 2   Download