This work is Volume II of a two-volume monograph on the theory of deterministic parsing of context-free grammars. Volume I, "Languages and Parsing" (Chapters 1 to 5), was an introduction to the basic concepts of formal language theory and context-free parsing. Volume II (Chapters 6 to 10) contains a thorough treat ment of the theory of the two most important deterministic parsing methods: LR(k) and LL(k) parsing. Volume II is a continuation of Volume I; together these two volumes form an integrated work, with chapters, theorems, lemmas, etc. numbered consecutively. Volume II begins with Chapter 6 in which the classical con structions pertaining to LR(k) parsing are presented. These include the canonical LR(k) parser, and its reduced variants such as the LALR(k) parser and the SLR(k) parser. The grammarclasses for which these parsers are deterministic are called LR(k) grammars, LALR(k) grammars and SLR(k) grammars; properties of these grammars are also investigated in Chapter 6. A great deal of attention is paid to the rigorous development of the theory: detailed mathematical proofs are provided for most of the results presented.

presupposition fails, we now give a short introduction into Unification Grammar. Since all implementations discussed in this volume use PROLOG (with the exception of BlockjHaugeneder), we felt that it would also be useful to explain the difference between unification in PROLOG and in UG. After the introduction to UG we briefly summarize the main arguments for using linguistic theories in natural language processing. We conclude with a short summary of the contributions to this volume. UNIFICATION GRAMMAR 3 Feature Structures or Complex Categories. Unification Grammar was developed by Martin Kay (Kay 1979). Martin Kay wanted to give a precise defmition (and implementation) of the notion of 'feature'. Linguists use features at nearly all levels of linguistic description. In phonetics, for instance, the phoneme b is usually described with the features 'bilabial', 'voiced' and 'nasal'. In the case of b the first two features get the value +, the third (nasal) gets the value -. Feature value pairs in phonology are normally represented as a matrix. bilabial: + voiced: + I nasal: - [Feature matrix for b.] In syntax features are used, for example, to distinguish different noun classes. The Latin noun 'murus' would be characterized by the following feature-value pairs: gender: masculin, number: singular, case: nominative, pred: murus. Besides a matrix representation one frequently fmds a graph representation for feature value pairs. The edges of the graph are labelled by features. The leaves denote the value of a feature.

How does a parser, a device that imposes an analysis on a string of symbols so that they can be interpreted, work? More specifically, how does the parser in the human cognitive mechanism operate? Using a wide range of empirical data concerning human natural language processing, Bradley Pritchett demonstrates that parsing performance depends on grammatical competence, not, as many have thought, on perception, computation, or semantics. Pritchett critiques the major performance-based parsing models to argue that the principles of grammar drive the parser; the parser, furthermore, is the apparatus that tries to enforce the conditions of the grammar at every point in the processing of a sentence. In comparing garden path phenomena, those instances when the parser fails on the first reading of a sentence and must reanalyze it, with occasions when the parser successfully functions the first time around, Pritchett makes a convincing case for a grammar-derived parsing theory.

Parsing, the syntactic analysis of language, has been studied extensively in computer science and computational linguistics. Computer programs and natural languages share an underlying theory of formal languages and require efficient parsing algorithms. This introduction reviews the theory of parsing from a novel perspective. It provides a formalism to capture the essential traits of a parser that abstracts from the fine detail and allows a uniform description and comparison of a variety of parsers, including Earley, Tomita, LR, Left-Corner, and Head-Corner parsers. The emphasis is on context-free phrase structure grammar and how these parsers can be extended to unification formalisms. The book combines mathematical rigor with high readability and is suitable as a graduate course text.

In Marcus (1980), deterministic parsers were introduced. These are parsers which satisfy the conditions of Marcus's determinism hypothesis, i.e., they are strongly deterministic in the sense that they do not simulate non determinism in any way. In later work (Marcus et al. 1983) these parsers were modified to construct descriptions of trees rather than the trees them selves. The resulting D-theory parsers, by working with these descriptions, are capable of capturing a certain amount of ambiguity in the structures they build. In this context, it is not clear what it means for a parser to meet the conditions of the determinism hypothesis. The object of this work is to clarify this and other issues pertaining to D-theory parsers and to provide a framework within which these issues can be examined formally. Thus we have a very narrow scope. We make no ar guments about the linguistic issues D-theory parsers are meant to address, their relation to other parsing formalisms or the notion of determinism in general. Rather we focus on issues internal to D-theory parsers themselves.

This second edition of Grune and Jacobs’ brilliant work presents new developments and discoveries that have been made in the field. Parsing, also referred to as syntax analysis, has been and continues to be an essential part of computer science and linguistics. Parsing techniques have grown considerably in importance, both in computer science, ie. advanced compilers often use general CF parsers, and computational linguistics where such parsers are the only option. They are used in a variety of software products including Web browsers, interpreters in computer devices, and data compression programs; and they are used extensively in linguistics.

Parsing technology is concerned with finding syntactic structure in language. In parsing we have to deal with incomplete and not necessarily accurate formal descriptions of natural languages. Robustness and efficiency are among the main issuesin parsing. Corpora can be used to obtain frequency information about language use. This allows probabilistic parsing, an approach that aims at both robustness and efficiency increase. Approximation techniques, to be applied at the level of language description, parsing strategy, and syntactic representation, have the same objective. Approximation at the level of syntactic representation is also known as underspecification, a traditional technique to deal with syntactic ambiguity. In this book new parsing technologies are collected that aim at attacking the problems of robustness and efficiency by exactly these techniques: the design of probabilistic grammars and efficient probabilistic parsing algorithms, approximation techniques applied to grammars and parsers to increase parsing efficiency, and techniques for underspecification and the integration of semantic information in the syntactic analysis to deal with massive ambiguity. The book gives a state-of-the-art overview of current research and development in parsing technologies. In its chapters we see how probabilistic methods have entered the toolbox of computational linguistics in order to be applied in both parsing theory and parsing practice. The book is both a unique reference for researchers and an introduction to the field for interested graduate students.

* The first book focused solely on data parsing, a task commonly deemed Perl’s greatest strength * Couples an introduction to data parsing concepts and techniques with practical instruction regarding the key Perl modules capable of facilitating often complex parsing tasks * The author, Christopher Frenz, is a bioinformaticist and expert on Perl and scientific computing