Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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@linc.cis .upenn.edu 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 .
