Logic Grammars

ISBN-13: 9781461281887 / Angielski / Miękka / 2013 / 234 str.

Harvey Abramson; Veronica Dahl

Opis

Logic grammars have found wide application both in natural language processing and in formal applications such as compiler writing. This book introduces the main concepts involving natural and formal language processing in logic programming, and discusses typical problems which the reader may encounter, proposing various methods for solving them. The basic material is presented in depth; advanced material, involving new logic grammar formalisms and applications, is presented with a view towards breadth. Major sections of the book include: grammars for formal language and linguistic research, writing a simple logic grammar, different types of logic grammars, applications, and logic grammars and concurrency. This book is intended for those interested in logic programming, artificial intelligence, computational linguistics, Fifth Generation computing, formal languages and compiling techniques. It may be read profitably by upper-level undergraduates, post-graduate students, and active researchers on the above-named areas. Some familiarity with Prolog and logic programming would be helpful; the authors, however, briefly describe Prolog and its relation to logic grammars. After reading Logic Grammars, the reader will be able to cope with the ever-increasing literature of this new and exciting field.

Spis treści

0. Introduction and Historic Overview.- I. Grammars for Formal Languages and Linguistic Research.- 1. What are Logic Grammars.- 1. Logic Grammars — Basic Features.- 2. Grammar Symbols.- 3. Use of Variables and Unification.- 3.1. Unification.- 3.2. Derivation Graphs.- 3.3. Symbol Arguments: Producers and Consumers of Structure.- 4. Tests within Rules.- 5. Operators.- 6. Analysis and Generation.- 7. A Formal Language Example.- 2. Relation of Logic Grammars to Prolog.- 1. Basic Prolog Concepts.- 2. Prolog as a Language Recognizer.- 3. Prolog as a Structure Builder.- Bibliographic Commentary for Part I.- II. Getting Started: How to Write a Simple Logic Grammar.- 3. Step-by-Step Development of a Natural Language Analyser.- 1. Propositional Statements.- 2. Obtaining Representations for Propositional Statements.- 3. Syntactic and Semantic Agreement.- 4. Noun Phrases.- 5. Negative Sentences.- 6. Interrogative Clauses.- 4. Choosing Internal Representations for Natural Language.- 1. Logical Form for Querying Knowledge Represented in Logic.- 2. First-Order Logic Representations.- 2.1. Semantic Well Formedness.- 2.2. Ambiguity.- 2.3. Natural Language Determiners and Modifiers.- 2.3.1. Three-Branched Quantification.- 2.3.2. Quantifier Scoping.- 2.4. Negation.- 2.5. Meaning of Plural Forms.- 2.6. Representing Sets.- 3. Lambda-Calculus Representations.- 5. Developing a Logic Grammar for a Formal Application.- 1. An Analyzer for Logic Programs.- 2. Simple Lexical Analysis.- 3. Structural Representation of a Logic Program.- 4. “Compiling” Logic Programs.- 5. Compiling Proof Tree Generation into Rules.- Bibliographic Commentary for Part II.- III. Different Types of Logic Grammars — What Each Is Useful For.- 6. Basic Types of Logic Grammars.- 1. Metamorphosis Grammars.- 2. Definite Clause Grammars.- 3. Extraposition Grammars.- 4. Discussion.- 7. Building Structure.- 1. Parse Tree Construction.- 2. Meaning Representation Buildup.- 3. Automating Syntactic and Semantic Structure Buildup.- 8. Modifier Structure Grammars.- 1. Separation of Syntax and Semantics.- 2. Quantifier Rescoping.- 3. Coordination.- 4. Implementation.- 5. Discussion.- 9. Definite Clause Translation Grammars and their Applications.- 1. Definite Clause Translation Grammars.- 2. A Compiler.- 2.1. Introduction.- 2.2. Lexical Analysis.- 2.3. Between Lexical and Syntactic Analysis.- 2.4. Syntactic Analysis.- 2.5. Code Generation.- 2.5.1. The Target Machine.- 2.5.2. Code Generated for Statements.- 2.5.3. Code for Expressions.- 2.6. Assembly and Allocation.- 3. A Metagrammatical Extension of DCTG Notation.- 4. Grammatical Data Typing.- 4.1. The Natural Numbers.- 4.2. Lists.- 4.3. Trees.- 4.4. Infix and Prefix Notation.- 4.5. Comments on Grammatical Typing.- 10. Further Expressive Power — Discontinuous Grammars.- 1. The Discontinuous Grammar Family.- 2. Thinking in Terms of Skips — Some Examples.- 2.1. Coordination.- 2.2. Right Extraposition.- 2.3. Interaction between Different Discontinuous Rules.- 2.4. Avoiding Artifices through Straightforward Uses of Skips.- 2.5. Rules with More Than One Skip.- 2.6. DGs and Free Word Order Languages.- 2.6.1. Totally Free Word or Constituent Order.- 2.6.2. Lexically Induced Rule Format and Free Word Order.- 3. Static Discontinuity Grammars and Government-Binding Theory.- 3.1. Rendering Context-Free Simplicity with Type-0 Power.- 3.2. Government-Binding-Oriented Constraints.- 3.3. Definition.- 3.4. Implementation Considerations.- 3.5. Transporting the Static Discontinuity Feature into Logic Programming.- Bibliographic Commentary for Part III.- IV. Other Applications.- 11. Other Formalisms.- 1. Restriction Grammars.- 2. Puzzle Grammars.- 3. Discussion.- 12. Bottom Up Parsing.- 1. Introduction.- 2. Compiling Context-Free Rules.- Bibliographic Commentary for Part IV.- V. Logic Grammars and Concurrency.- 13. Parsing with Committment.- 1. Introduction.- 1.1. Sample Grammar.- 1.2. The One Character Lookahead Relation.- 2. Compilation to Sequential Logic Programs.- 3. Compilation to Concurrent Logic Program Clauses.- 4. Generalized Deterministic Grammars.- 5. Related Work.- 6. Parallel Parsing for Natural Language Analysis.- 6.1. Sample Grammar.- 6.2. Parallel Parsing Method.- Bibliographic Commentary for Part V.- Appendices.- I. Input/Output in Logic Grammars.- 1. Input of a Sentence.- II. Implementation of Logic Grammar Formalisms.- 1. SYNAL: Compiling Disc. Grammars to Prolog.- 2. A Short Interpreter for Static Discontinuity Grammars.- 3. Implementations of DCTGs.- 3.1. An Interpreter for Definite Clause Translation Grammars.- 3.2. Compiling Definite Clause Translation Grammars to Prolog.- 3.3. Typing DCTGs.- Literature.