Search

Arabic is the main language of Al-Quran. Nowadays, many people are studying the Language of Al-Quran, called Quran Arabic. For the beginners, it is important for them to understand the syntactic relationship in a sentence found in the Qur'an. If they do not understand enough, the interpretation will be different and wrong. It will turn into dangerous because Al-Quran is a source of guidance for Muslims’ life. Dependency parsing is very important for linguistic research, especially for rich languages such as the Arabic Language. This study aims to build dependency parsing, in order to make it easier to get to understand syntactic relationship information in sentences. This study uses a parsing method called deterministic parsing, which the method used is shift-reduce parsing with the Easy-First parsing algorithm. The evaluation used labeled attachment score calculation. The score generated from the evaluation was 69.7, beforehand, the comparison both the system results and the gold standard have been done. 62 sentences found the correct head and relation in each word. The number of words found to be wrong is not more than 3 words in one sentence. Evaluation scores produced are not exorbitant due to the complicated tagset used and lacking test sentences.

We introduce a new parser generator, called Berry–Sethi Parser (BSP), for ambiguous regular expressions (RE). The generator constructs a deterministic finite-state transducer that recognizes an input string, as the classical Berry–Sethi algorithm does, and additionally outputs a linear representation of all the syntax trees of the string; for infinitely ambiguous strings, a policy for selecting representative sets of trees is chosen. To construct the transducer, the RE symbols, including letters, parentheses and other metasymbols, are distinctly numbered, so that the corresponding language becomes locally testable. In this way a deterministic position automaton can be constructed, which recognizes and translates the input into a compact DAG representation of the syntax trees. The correctness of the construction is proved. The transducer operates in a linear time on the input. Its descriptive complexity is analyzed as a function of established RE parameters: the alphabetic width, the number of null string symbols and the height of the RE tree. A condition for checking RE ambiguity on the transducer graph is stated. Experimental results of running the parser generator and the parser on a large RE collection are presented. The POSIX RE disambiguation criterion has also been applied to the parser.

Parser combinators offer a concise and fast way to produce reasonably efficient parsers. The combinator libraries themselves can be small and provide an elegant application of functional programming techniques. They are one of the success stories in functional programming that are also ported to many other languages. In this paper, we illustrate that we can make the parser combinators more general by modeling them as a tagless domain specific language. The idea is to replace the ordinary combinators by a set of type constructor classes. By making different implementations of this class we can assign various interpretations of one and the same grammar specification. The set of type classes makes the DSL type-safe and extendable without needing to change existing parts and implementations. This enables us to make multiple interpretations, views, of the specified grammar. In this paper we show views for deterministic parsing, nondeterministic parsing, generating possible parse trees produced by the grammar without needing the corresponding input, generating inputs accepted by the grammar, adapting the grammar rules such that the parser combinators can handle left-recursion and so on. This makes our multi-view parser combinators more powerful than the existing approaches.

Regular languages (RL) are the simplest family in Chomsky’s hierarchy. Thanks to their simplicity they enjoy various nice algebraic and logic properties that have been successfully exploited in many application fields. Practically all of their related problems are decidable, so that they support automatic verification algorithms. Also, they can be recognized in real-time. Context-free languages (CFL) are another major family well-suited to formalize programming, natural, and many other classes of languages; their increased generative power w.r.t. RL, however, causes the loss of several closure properties and of the decidability of important problems; furthermore they need complex parsing algorithms. Thus, various subclasses thereof have been defined with different goals, spanning from efficient, deterministic parsing to closure properties, logic characterization and automatic verification techniques. Among CFL subclasses, so-called structured ones, i.e., those where the typical tree-structure is visible in the sentences, exhibit many of the algebraic and logic properties of RL, whereas deterministic CFL have been thoroughly exploited in compiler construction and other application fields. After surveying and comparing the main properties of those various language families, we go back to operator precedence languages (OPL), an old family through which R. Floyd pioneered deterministic parsing, and we show that they offer unexpected properties in two fields so far investigated in totally independent ways: they enable parsing parallelization in a more effective way than traditional sequential parsers, and exhibit the same algebraic and logic properties so far obtained only for less expressive language families.

We investigate the possibility of the deterministic parsing (that is, parsing without backtracking) of languages described by (generalized) P colony automata. We define a subclass of these computing devices satisfying a property which resembles the LL(k) property of context-free grammars, and study the possibility of parsing the characterized languages using a k symbol lookahead, as in the LL(k) parsing method for context-free languages.

Usually unsupervised dependency parsers try to optimize the probability of a corpus by revising the dependency model that is assumed to have generated the corpus. In this paper we explore a different view in which a dependency structure is, among other things, a partial order on the nodes in terms of centrality or saliency. Under this assumption we directly model centrality and derive dependency trees from the ordering of words. The result is an approach to unsupervised dependency parsing that is very different from standard ones in that it requires no training data. The input words are ordered by centrality, and a parse is derived from the ranking using a simple deterministic parsing algorithm, relying on the universal dependency rules defined by Naseem et al. (Naseem, T., Chen, H., Barzilay, R., Johnson, M. 2010. Using universal linguistic knowledge to guide grammar induction. In Proceedings of Empirical Methods in Natural Language Processing, Boston, MA, USA, pp. 1234–44.). Our approach is evaluated on data from twelve different languages and is remarkably competitive.

Many parsing techniques assume the use of a packed parse forest to enable efficient and accurate parsing. However, they suffer from an inherent problem that derives from the restriction of locality in the packed parse forest. Deterministic parsing is one solution that can achieve simple and fast parsing without the mechanisms of the packed parse forest by accurately choosing search paths. We propose new deterministic shift-reduce parsing and its variants for unification-based grammars. Deterministic parsing cannot simply be applied to unification-based grammar parsing, which often fails because of its hard constraints. Therefore, this is developed by using default unification, which almost always succeeds in unification by overwriting inconsistent constraints in grammars.

This new parser generator for ambiguous regular expressions (RE) formally extends the Berry-Sethi (BS) algorithm into a finite-state device that specifies the syntax tree(s). We extend the local testability property of the marked RE’s from terminal strings to linearized syntax trees. The generator supports disambiguation, i.e., selecting a preferred tree in case of ambiguity. The selection is parametric with respect to the Greedy or POSIX criterion. The parser is proved correct and has linear-time complexity. The generator is available as an interactive SW tool (on GitHub - see http://github.com/breveglieri/ebs/README).

It is not always possible to find a global parse for an input sentence owing to problems such as errors of a sentence, incompleteness of lexicon and grammar. Partial parsing is an alternative approach to respond to these problems. Partial parsing techniques try to recover syntactic information efficiently and reliably by sacrificing completeness and depth of analysis. One of the difficulties in partial parsing is how the grammar might be automatically extracted. In this paper we present a method of automatically extracting partial parsing rules from a tree-annotated corpus using the decision tree method. Our goal is deterministic global parsing using partial parsing rules, in other words, to extract partial parsing rules with higher accuracy and broader expansion. First, we define a rule template that enables to learn a subtree for a given substring, so that the resultant rules can be more specific and stricter to apply. Second, rule candidates extracted from a training corpus are enriched with contextual and lexical information using the decision tree method and verified through cross-validation. Last, we underspecify non-deterministic rules by merging substructures with ambiguity in those rules. The learned grammar is similar to phrase structure grammar with contextual and lexical information, but allows building structures of depth one or more. Thanks to automatic learning, the partial parsing rules can be consistent and domain-independent. Partial parsing with this grammar processes an input sentence deterministically using longest-match heuristics, and recursively applies rules to an input sentence. The experiments showed that the partial parser using automatically extracted rules is not only accurate and efficient but also achieves reasonable coverage for Korean.

This paper presents an efficient parsing method for Korean using statistical information extracted from a corpus. Structural ambiguity commonly occurs while deciding dependency relations between words in Korean sentences. To resolve the ambiguity, lexical association between words plays an important role in figuring out the correct dependency. Our parser uses statistical co-occurrence data to compute the lexical association. In addition, we define the global association table (GAT) which enables a global management of the associations. Using the GAT, the parser has an overall configuration of dependency relations between words, thus can analyze a sentence almost deterministically. That is, our system can be viewed as a semi-deterministic parser, which is controlled not by the condition-action rule but by the association value between phrases. Furthermore, the unknown grammatical case of a noun phrase caused by the auxiliary postposition in Korean can be effectively resolved using lexical co-occurrences in our system.

The increasing use of multicore processors has deeply transformed computing paradigms and applications. The wide availability of multicore systems had an impact also in the field of compiler technology, although the research on deterministic parsing did not prove to be effective in exploiting the architectural advantages, the main impediment being the inherent sequential nature of traditional LL and LR algorithms. We present PAPAGENO, an automated parser generator relying on operator precedence grammars. We complemented the PAPAGENO-generated parallel parsers with parallel lexing techniques, obtaining near-linear speedups on multicore machines, and the same speed as Bison parsers on sequential execution.

A uniquely parsable array grammar (UPAG) introduced by Yamamoto and Morita is a special kind of isometric array grammar (IAG) in which parsing can be performed without backtracking. Hence, we can use a UPAG as an efficient syntactic pattern recognition mechanism, if the pattern set is properly described by a UPAG. In this paper, we investigate the problem of describing and recognizing the set of all connected patterns using a UPAG formalism. As for the recognition of connected patterns, Beyer showed an efficient algorithm that operates on cellular automata. We show that his algorithm can be expressed very simply in the UPAG framework, and give two kinds of simple UPAGs that generate the set of all connected patterns.

Complex languages are often modularized into sublanguages and the compiler is accordingly organized as a set of separate modules. Modularization (called federalization) is beneficial for beating complexity, for maintenance, and for reuse. Focusing on syntax analysis, we consider the decomposition of a grammar into deterministic subgrammars. We study three conditions for determinism in grammar partitioning: first using homogeneous modules of the LR(1) or LL(1) kind; then using heterogeneous modules (LR(1) or LL(1)). Federalization slightly decreases the generality of LR(1) parsers, but not of LL(1) ones, and it allows to handle some grammars which are not LALR(1). Experimental results show that LR(1) federal automata have fewer (up to 60%) states than monolithic LR(1) automata. Criteria for modularization, practical experiences and hints to semantic decomposition issues conclude the paper.

A partially ordered multiset or pomset is a generalization of a string in which the total order has been relaxed to a partial order. Strings are often used as a model for sequential computation; pomsets are a natural model for parallel and distributed computation. By viewing pomsets as a generalization of strings, the question is raised whether concepts from language theory can be generalized to pomsets. An important area in the theory of languages is parsing theory. This paper develops the fundamentals of a parsing theory for pomsets, called PLR parsing. It is based on the LR-parsing technique, which is the most powerful deterministic parsing technique in language theory. The basic algorithm in the class of PLR parsing algorithms, the PLR(0) algorithm is explained in detail.

This paper describes an implementation of a deterministic parsing system, described in Nordgard (1993). The syntax of “heuristic rules” and how the rules interact with the basic operations of the parser constitute the bulk of the article. The implementation is written in Medley Interlisp, and the system can be run on Sun or Xerox workstations.

One obstacle to the implementation of modular extensions to programming languages lies in the problem of parsing extended languages. Specifically, the parse tables at the heart of traditional LALR(1) parsers are so monolithic and tightly constructed that, in the general case, it is impossible to extend them without regenerating them from the source grammar. Current extensible frameworks employ a variety of solutions, ranging from a full regeneration to using pluggable binary modules for each different extension. But recompilation is time-consuming, while the pluggable modules in many cases cannot support the addition of more than one extension, or use backtracking or non-deterministic parsing techniques. We present here a middle-ground approach that allows an extension, if it meets certain restrictions, to be compiled into a parse table fragment. The host language parse table and fragments from multiple extensions can then always be efficiently composed to produce a conflict-free parse table for the extended language. This allows for the distribution of deterministic parsers for extensible languages in a pre-compiled format, eliminating the need for the “source code” grammar to be distributed. In practice, we have found these restrictions to be reasonable and admit many useful language extensions.

This paper presents a two-step dependency parser to parse Chinese deterministically. By dividing a sentence into two parts and parsing them separately, the error accumulation can be avoided effectively. Previous works on shift-reduce dependency parser may guarantee the greedy characteristic of deterministic parsing less. This paper improves on a kind of deterministic dependency parsing method to weaken the greedy characteristic of it. During parsing, both forward and backward parsing directions are chosen to decrease the unparsed rate. Support vector machines are utilized to determine the word dependency relations and in order to solve the problem of long distance dependency, a group of combined global features are presented in this paper. The proposed parser achieved significant improvement on dependency accuracy and root accuracy.

A rough set-based semi-naive Bayesian classification method is applied to dependency parsing, which is an important task in syntactic structure analysis of natural language processing. Many parsing algorithms have emerged combined with statistical machine learning techniques. The rough set-based classifier is embedded with Nivre's deterministic parsing algorithm to conduct dependency parsing task on a Chinese corpus. Experimental results show that the method has a good performance on dependency parsing task. Moreover, the experiments have justified the effectiveness of the classification influence.

In Japanese dependency parsing, Kudo's relative preference-based method (Kudo and Matsumoto, 2005) outperforms both deterministic and probabilistic CKY-based parsing methods. In Kudo's method, for each dependent word (or chunk) a log-linear model estimates relative preference of all other candidate words (or chunks) for being as its head. This cannot be considered in the deterministic parsing methods. We propose an algorithm based on a tournament model, in which the relative preferences are directly modeled by one-on-one games in a step-ladder tournament. In an evaluation experiment with Kyoto Text Corpus Version 4.0, the proposed method outperforms previous approaches, including the relative preference-based method.

Parsing models have many applications in AI, ranging from natural language processing (NLP) and computational music analysis to logic programming and computational learning. Broadly conceived, a parsing model seeks to uncover the underlying structure of an input, that is, the various ways in which elements of the input combine to form phrases or constituents and how those phrases recursively combine to form a tree structure for the whole input. During the last fifteen years, a major shift has taken place from rule-based, deterministic parsing to corpus-based, probabilistic parsing. A quick glance over the NLP literature from the last ten years, for example, indicates that virtually all natural language parsing systems are currently probabilistic. The same development can be observed in (stochastic) logic programming and (statistical) relational learning. This trend towards probabilistic parsing is not surprising: the increasing availability of very large collections of text, music, images and the like allow for inducing statistically motivated parsing systems from actual data.

The major problems in parsing English conjunctions and comparatives are ambiguities of scoping and ellipsis. Scoping ambiguities occur when a parser cannot deterministically detect boundaries of constituents, while ellipsis ambiguities occur when a parser cannot deterministically detect missing components. Since simple lookahead mechanisms cannot collect adequate information to resolve these ambiguities, a parsing strategy that only employs such mechanisms will need to backtrack each time it makes incorrect assumptions. In this paper, we extend the Wait-And-See strategy to parse conjunctions and comparatives deterministically and simultaneously. Several mechanisms, such as bottom-up preparsing, suspension, and pattern matching, are implemented. The bottom-up preparsing accesses the dictionary and recognizes isolated sentence fragments which can be determined without ambiguities. The suspension, which is different from Marcus’s attention shifting, allows the parser to suspend temporally at ambiguous points and continue to parse the rest of the sentence until it obtains the necessary information to resolve the ambiguities. Pattern matching uses the concept of symmetry to detect missing components (the ellipses) in the two conjoined or compared sentence fragments.

The paper extends the notion of context-free LL(k) grammars to CD grammar systems using two different derivation modes, examines some of the properties of the resulting language families, and studies the possibility of parsing these languages deterministically, without backtracking.

This paper presents a three-step dependency parser to parse Chinese deterministically. By dividing a sentence into several parts and parsing them separately, it aims to reduce the error propagation coming from the greedy characteristic of deterministic parsing. Experimental results showed that compared with the deterministic parser which parsed a sentence in sequence, the proposed parser achieved extremely significant improvement on dependency accuracy.

This paper presents a deterministic parsing algorithm for projective dependency grammar. In a bottom-up way the algorithm finds the local optimum dynamically. A constraint procedure is made to use more structure information. The algorithm parses sentences in linear time and labeling is integrated with the parsing. This parser achieves 63.29% labeled attachment score on the average in CoNLL-X Shared Task.

Recently proposed deterministic classifier-based parsers (Nivre and Scholz, 2004; Sagae and Lavie, 2005; Yamada and Mat-sumoto, 2003) offer attractive alternatives to generative statistical parsers. Deterministic parsers are fast, efficient, and simple to implement, but generally less accurate than optimal (or nearly optimal) statistical parsers. We present a statistical shift-reduce parser that bridges the gap between deterministic and probabilistic parsers. The parsing model is essentially the same as one previously used for deterministic parsing, but the parser performs a best-first search instead of a greedy search. Using the standard sections of the WSJ corpus of the Penn Treebank for training and testing, our parser has 88.1% precision and 87.8% recall (using automatically assigned part-of-speech tags). Perhaps more interestingly, the parsing model is significantly different from the generative models used by other well-known accurate parsers, allowing for a simple combination that produces precision and recall of 90.9% and 90.7%, respectively.

Deterministic parsing guided by treebank-induced classifiers has emerged as a simple and efficient alternative to more complex models for data-driven parsing. We present a systematic comparison of memory-based learning (MBL) and support vector machines (SVM) for inducing classifiers for deterministic dependency parsing, using data from Chinese, English and Swedish, together with a variety of different feature models. The comparison shows that SVM gives higher accuracy for richly articulated feature models across all languages, albeit with considerably longer training times. The results also confirm that classifier-based deterministic parsing can achieve parsing accuracy very close to the best results reported for more complex parsing models.

This paper addresses efficient parsing in the context of logical inference for the purpose of using logic programming languages in compiler writing. A bottom-up, deterministic parsing mechanism is formulated for "bounded right context" grammars, a subclass of LR(k) grammars with characteristics amenable to declarative parser specification. A working parser generator for λProlog is described, although the basic parsing mechanism is applicable to logic programming in general.

In contrast to the usual depth-first derivations of context-free (CF) grammars, breadth-first derivations (also in combination with depth-first ones) yield a class of augmented context-free grammars (ACF) (also termed multi-breadth-depth grammars) endowed with greater generative capacity, yet manageable. The inadequacy of CF grammars to treat distant dependencies is overcome by the new model. ACF grammars can be classified with respect to their disposition, a concept related to the data structure needed to parse their strings. For such augmented CF grammars we consider the LL(k) condition, that ensures top-down deterministic parsing. We restate the condition as an adjacency problem and we prove that it is decidable for any disposition. The deterministic linear-time parser differs from a recursive descent parser by using instead of a LIFO stack a more general data structure, involving FIFO queues and LIFO stacks in accordance with the disposition. ACF grammars can be also viewed as a formalized version of ATN (Augmented Transition Networks).

The suitability of different parsing methods for different languages is an important topic in syntactic parsing. Especially lesser-studied languages, typologically different from the languages for which methods have originally been developed, pose interesting challenges in this respect. This article presents an investigation of data-driven dependency parsing of Turkish, an agglutinative, free constituent order language that can be seen as the representative of a wider class of languages of similar type. Our investigations show that morphological structure plays an essential role in finding syntactic relations in such a language. In particular, we show that employing sublexical units called inflectional groups, rather than word forms, as the basic parsing units improves parsing accuracy. We test our claim on two different parsing methods, one based on a probabilistic model with beam search and the other based on discriminative classifiers and a deterministic parsing strategy, and show that the usefulness of sublexical units holds regardless of the parsing method. We examine the impact of morphological and lexical information in detail and show that, properly used, this kind of information can improve parsing accuracy substantially. Applying the techniques presented in this article, we achieve the highest reported accuracy for parsing the Turkish Treebank.

This paper describes an approach for determining the minimum, maximum, and average times to parse sentences acceptable by a deterministic parser. These quantities are presented in the form of symbolic formulas, called time-formulas. The variables in these formulas represent not only the length of the input string but also the time to perform elementary operations such as pushing, popping, subscripting, iterating, etc. By binding to the variables actual numerical values corresponding to a given compiler-machine configuration, one can determine the execution time for that configuration. Time-formulas are derived by examining the grammar rules and the program representing the algorithm one wishes to analyze. The approach is described by using a specific grammar that defines simple arithmetic expressions. Two deterministic parsers are analyzed: a top-down recursive descent LL(1) parser, and a bottom-up SLR(1) parser. The paper provides estimates for the relative efficiencies of the two parsers. The estimates applicable to a specific machine, the PDP-10, are presented and substantiated by benchmarks. Finally, the paper illustrates the proposed approach by applying it to the analyses of parsers for a simple programming language.

It has previously been claimed that a deterministic model of the human sentence parsing mechanism provides an explanation for the existence of, and some of the properties of, the subjacency constraint on natural languages. The present paper argues that the empirical arguments offered in support of these claims are flawed, and that in any case the explanatory relationship between determinism and subjacency is weak.

Described is a method for syntactic error recovery that is compatible with deterministic parsing methods and that is able to recover from many errors more quickly than do other schemes because it performs global context recovery. The method relies on fiducial symbols, which are typically reserved key words of a language, to provide mileposts for error recovery. The method has been applied to LL(1) parsers, for which a detailed algorithm is given, and informally proved correct. The algorithm will always recover and return control to the parser if the text being analyzed satisfies only minimal requirements: that it contains one or more occurrences of fiducial symbols following the point at which an error is detected. Tables needed for error recovery have been automatically generated, along with parsing tables, by a parser constructor for the LL(1) grammars. A theoretical characterization of fiducial symbols is given, and the utility of this characterization in practice is discussed. It has been applied to a grammar for the programming language Pascal to aid in selection of a set of fiducial symbols. The error recovery scheme has been tested on a set of student-written Pascal program texts and is compared with other error recovery strategies.

This paper presents a model for deterministic parsing which was designed to simplify the task of writing and understanding a deterministic grammar. While retaining structures and operations similar to those of Marcus' PARSIFAL parser [Marcus 80] the grammar language incorporates the following changes. (1) The use of productions operating in parallel has essentially been eliminated and instead the productions are organized into sequences. Not only does this improve the understandability of the grammar, it is felt that this organization corresponds more closely to the task of performing the sequence of buffer transformations and attachments required to parse the most common constituent types. (2) A general method for interfacing between the parser and a semantic representation system is introduced. This interface is independent of the particular semantic representation used and hides all details of the semantic processing from the grammar writer. (3) The interface also provides a general method for dealing with syntactic ambiguities which arise from the attachment of optional modifiers such as prepositional phrases. This frees the grammar writer from determining each point at which such ambiguities can occur.

This chapter is concerned with a family of deterministic parsing techniques based on a method first described by Knuth [1965]. These parsers, and the grammars acceptable to them, share most of the desirable properties of the LL(k) family [Chapter 2.B.]. In addition, the class of LR(k)-parsable grammars is probably the largest class accepted by any currently practical parsing technique. The techniques with which we are mostly concerned are, in order of increasing power, LR(0), SLR(1), LALR(1) and LR(1). Collectively, we call these four techniques the LR family [McKeeman 1970] [Aho 1974].

MLR, an extended LR parser, is introduced, and its application to natural language parsing is discussed. An LR parser is a shift-reduce parser which is deterministically guided by a parsing table. A parsing table can be obtained automatically from a context-free phrase structure grammar. LR parsers cannot manage ambiguous grammars such as natural language grammars, because their parsing tables would have multiply-defined entries, which precludes deterministic parsing. MLR, however, can handle multiply-defined entries, using a dynamic programming method. When an input sentence is ambiguous, the MLR parser produces all possible parse trees without parsing any part of the input sentence more than once in the same way, despite the fact that the parser does not maintain a chart as in chart parsing. Our method also provides an elegant solution to the problem of multi-part-of-speech words such as "that". The MLR parser and its parsing table generator have been implemented at Carnegie-Mellon University.

Marcus' original deterministic parsing included almost no part-of-speech ambiguity. In this paper, the addition of part-of-speech ambiguity to a deterministic parser written in Prolog is described. To handle this ambiguity, it was necessary to add no special mechanisms to the parser. Instead the grammar rules were made to enforce agreement, and reject ungrammatical sentences. The resulting system is very effective and covers many examples of ambiguity.

This paper assesses two new approaches to deterministic parsing with respect to the analysis of unbounded dependencies (UDs). UDs in English are highly locally (and often globally) ambiguous. Several researchers have argued that the difficulty of UDs undermines the programme of deterministic parsing. However, their conclusion is based on critiques of various versions of the Marcus parser which represents only one of many possible approaches to deterministic parsing. We examine the predictions made by a LR(1) deterministic parser and the Lexicat deterministic parser concerning the analysis of UDs. The LR(1) technique is powerful enough to resolve the local ambiguities we examine. However, the Lexicat model provides a more psychologically plausible account of the parsing of UDs, which also offers a unified account of the resolution of local and global ambiguities in these constructions.

Publisher Summary Lexical ambiguity and especially part-of-speech ambiguity is the source of much non-determinism in parsing. The chapter states that handling lexical ambiguity is a major test for deterministic parsing. It presents many cases of ambiguity that can be resolved in a simple way. This is possible because of the constraints imposed on English by number agreement and word order. Many cases of the seemingly difficult problems of lexical ambiguity can be easily resolved in a deterministic parser, because it uses more information to make decisions. In parsing English, one of the major causes of non-determinism is part-of-speech ambiguity. If a word can be two parts of speech, then a non-deterministic parser may have to explore both possibilities. The chapter explores lexical ambiguity considering both simple and complex examples.

Methods of describing the syntax of programming languages in ways that are more flexible and natural than conventional BNF descriptions are considered. These methods involve the use of ambiguous context-free grammars together with rules to resolve syntactic ambiguities. It is shown how efficient LR and LL parsers can be constructed directly from certain classes of these specifications.

Recently strict deterministic grammars and languages have been introduced [9,10,11]. This family of languages is quite fundamental in the study of the mathematical properties of deterministic languages and in dealing with some classical families of grammars such as LR(k) and bounded right context grammars [7,8,14]. These grammars are closely related to LR(0) grammars [1,12,13,14], in fact each strict deterministic grammar is also LR(0). In the present paper, we consider the question of how to parse strict deterministic grammars. We introduce part of a more general theory called "characteristic LR(k) parsing". This actually produces parsers which are tuned to the characteristics of a particular family of grammars. We apply the theory to the family of strict deterministic grammars and we get parsers which are as fast as canonical LR(k) parsers but are substantially smaller. They are not necessarily minimal but we postpone any discussion of minimality to the sequel.The techniques used in the present discussion are quite general [5]. For instance, the study in [3] is similar in spirit to our technique. The optimization techniques for LR(k) parsers in [2] do not work in the case k = 0 without modification. After modifying those methods for k = 0, it can be shown that our parsers cannot be produced by those techniques. This fact has its positive aspect in that our parsers may be smaller and its negative aspect in that error detection may be delayed.The present paper is divided into the present introduction and three sections. In the remainder of this introduction, some basic definitions of strict deterministic and LR(k) parsing are given. We have tried to follow [1] as much as possible in order to minimize the amount of new material to be absorbed. The order of the results is the order needed to prove that the characteristic parser works. In Section III, we apply the theory of Section II to strict deterministic parsing. A simple example shows that the new parsers can be unboundedly smaller than the canonical LR(0) parser.The present paper is meant to be an extended abstract and no proofs are included.The rest of the introduction is concerned with notational conventions for the technical concepts needed.

To support incremental interpretation, any model of human sentence processing must not only process the sentence incrementally, it must to some degree restrict the number of analyses which it produces for any sentence prefix. Deterministic parsing takes the extreme position that there can only be one analysis for any sentence prefix. Experiments with an incremental statistical parser show that performance is severely degraded when the search for the most probable parse is pruned to only the most probable analysis after each prefix. One method which has been extensively used to address the difficulty of deterministic parsing is lookahead, where information about a bounded number of subsequent words is used to decide which analyses to pursue. We simulate the effects of lookahead by summing probabilities over possible parses for the lookahead words and using this sum to choose which parse to pursue. We find that a large improvement is achieved with one word lookahead, but that more lookahead results in relatively small additional improvements. This suggests that one word lookahead is sufficient, but that other modifications to our left-corner parsing model could make deterministic parsing more effective.

"A Theory of Syntactic Recognition for Natural Language" makes use of the hypothesis that the syntax of any natural language can be parsed by a mechanism which operates "strictly deterministically" in that it does not simulate a nondeterministic machine. Basing his research strictly on English, Marcus sets forth some principles of processing that interact to offer explanations for some fundamental properties of language. He shows that language should have a certain design in order to be efficiently processed by the system he has constructed; specifically, rules should have certain locality properties, left-right asymmetries, and hierarchic structures that enter into rule types in special ways.Included in this volume are sections on the Determinism Hypothesis, Historical Perspective, the Grammar Interpreter, Structure of Grammar, Capturing Linguistic Generalizations, The Grammar Interpreter and Chomsky's Constraints, Parsing Relative Clauses, Parsing Noun Phrases, Differential Diagnosis and Garden Path Sentences, and the Necessity of Some Semantic/Syntactic Interactions.