TAILIEUCHUNG - Báo cáo khoa học: "DETERMINISTIC LEFT TO RIGHT PARSING OF TREE ADJOINING LANGUAGES*"

We define a set of deterministic bottom-up left to right parsers which analyze a subset of Tree Adjoining Languages. The LR parsing strategy for Context Free Grammars is extended to Tree Adjoining Grammars (TAGs). We use a machine, called Bottom-up Embedtied Push Down Automaton (BEPDA), that recognizes in a bottom-up fashion the set of Tree Adjoining Languages (and exactly this se0. Each parser consists of a finite state control that drives the moves of a Bottom-up Embedded Pushdown Automaton. . | DETERMINISTIC LEFT TO RIGHT PARSING OF TREE ADJOINING LANGUAGES Yves Schabes DepL of Computer Information Science University of Pennsylvania Philadelphia PA 19104-6389 USA schabes@ . Abstract We define a set of deterministic bottom-up left to right parsers which analyze a subset of Tree Adjoining Languages. The LR parsing strategy for Context Free Grammars is extended to Tree Adjoining Grammars TAGs . We use a machine called Bottom-Up Embedded Push Down Automaton BEPDA that recognizes in a bottom-up fashion the set of Tree Adjoining Languages and exactly this set . Each parser consists of a finite state control that drives the moves of a Bottom-Up Embedded Pushdown Automaton. The parsers handle deterministically some context-sensitive Tree Adjoining Languages. In this paper we informally describe the BEPDA then given a parsing table we explain the LR parsing algorithm. We then show how to construct an LR 0 parsing table no lookahead . An example of a context-sensitive language recognized deterministically is given. Then we explain informally the construction of SLR l parsing tables for BEPDA. We conclude with a discussion of our parsing method and current work. 1 Introduction LR k parsers for Context Free Grammars Knuth 1965 consist of a finite state comrol constructed given a CFG that drives deterministically with k lookahead symbols a push down stack while scanning the input from left to right. It has been shown that they recognize exacdy the set of languages recognized by deterministic push down automata. LR k parsers for CFGs have been proven useful for compilers as well as recently for natural language processing. For natural language processing although LR k parsers are not powerful enough The first author is partially supported by Darpa grant N0014-85-K0018 ẠRO grant DAALŨ3-89-C-0031PRI NSF grant-IRI84-10413 A02. We are extremely grateful to Bernard Lang and David Weir for their valuable suggestions. K. Vijay-Shanker Dept of Computer .

• Báo cáo khoa học
• DETERMINISTIC LEFT TO RIGHT PARSING
• TREE ADJOINING LANGUAGES
• Yves Schabes
• scientific reports
• model language
• process natural language
• Dialog Control
• Natural Language System
• Dialog Control in a Natural Language System
• Expanding the Horizons
• Natural Language Interfaces
• Phil Hayes
• PROSPECTS OR PRACTICAL
• NATURAL LANGUAGE SYSTEMS
• Workshops
• NATURAL LANGUAGE
• INTERACTION WITH MACHINES
• Long Papers
• COMPUTER INTEBFACE DESIGN MURRAY TUROFF DEPARTMENT OF COMPUTER
• IiVFORMATION SCIENCE IIEW JERSEY INSTITUTE OF TECHNOLOGY
• EVALUATION OF NATURAL LANGUAGE
• INTERFACES TO DATABASE SYSTEMS
• A PANEL DISCUSSION
• database query system
• J
• Norwood Crout
• INTERFACES TO DATA BASE SYSTEMS
• Bozena Henisz
• INTERPRETING NATURAL LANGUAGE
• DATABASE UPDATES
• S
• Jermld Kaplan Jim David
• TRANSPORTABLE NATURAL LANGUAGE
• INTERFACES TO DATABASES
• Gary G
• Hendrlx and William H
• Lewis
• DATABASES THEORETICAL
• TECHNICAL ISSUES
• TRANSPORTABLE NATURAL LANGUAGE INTERFACES
• PROBLEMS AND TECHNIQUES
• Barbara J
• Grosz
• THEORETICAL TECHNICAL ISSUES
• NATURAL LANGUAGE ACCESS TO DATABASES
• R
• Petrick
• Domain Independent
• Database Access Systems
• ISSUES IN NATURAL LANGUAGE
• ACCESS TO DATABASES
• A LOGIC PROGRAMMING PERSPECTIVE
• Sharon C
• Salveter David Maier
• PLANNING NATURAL LANGUAGE
• EXPRESSIONS REFERRING
• Douglas E
• Appelt
• THE TEXT SYSTEM
• NATURAL LANGUAGE GENERATION
• Kathleen R
• M
• MENTING A DATABASE
• KNOWLEDGE REPRESENTATION
• THE KEY TO THE SELECTION PROBLEM
• E
• Jeffrey Conklin David D
• McDonald
• A KNOWLEDGE ENGINEERING
• NATURAL LANGUAGE UNDERSTANDING
• Stuart C
• Shapiro
• NATURAL LANGUAGE TEXTS
• NECESSARILY GRAMMATICAL
• EVEN COMPLETE
• UNGRAMHATICALITY
• EXTRA GRAMMATICALITY
• NATURAL LANGUAGE UNDERSTANDING SYSTEMS
• Taxonomy
• Descriptions
• Individuals in Natural
• Language Understanding
• The Use of Ooject Special Knowledge
• Natural Language Processing
• Mark H
• Bursteln