jr@forcm5.UUCP (John Rogers) (03/04/84)
Hi. In the new issue of Dr. Dobb's Journal (DDJ), there's a review of a book entitled "Augmented Transition Networks." The review begins: "Confused by the title? Well, if you are not sure what an Augmented Transition Network is I'll try to explain. An Augmented Transition Network (ATN) is used in the design of interpreters, compilers, and editors as a method of factoring the input." The review goes on to imply that ATNs are somehow related to parsing, but doesn't give any more detail. Can anyone tell me what ATNs are? I've looked in my collection of compiler books, and every other place I can think of, and I can't find anything about them. HELP!!!! More information: the full citation for the book is "Augmented Transition Networks," edited by Leonard Bolc, published by Springer-Verlag, 1983, $29.00, 213 pages. The book contains four papers, with titles "The Planes Interpreter and Compiler for ATN Grammars," "An ATN Programming Environment," "Compiling ATN into MacLisp," and "Towards an Elastic ATN Implementation." The review is by Chuck Ballinger, and it's in the March 1984 issue of Dr. Dobb's Journal, on page 90. Thanks in advance... -- JR (John Rogers) UUCP: forcm5!jr, fortune!jr, proper!jr
blenko@rochester.UUCP (Tom Blenko) (03/06/84)
Augmented transition networks (ATN's) are an extension of finite state machine models for parsers. They were first applied by Bill Woods and others at BBN for parsing of natural language. A recursive transition networl (RTN) is just like a finite state machine, except that "pushes" of subnetworks are permissible transitions. Thus S: [NP] [VP] ----->SSub----->SPred NP: [Art] [Noun] +------>Det+------->HN | | -----------> VP: [Verb] [NP] -------->Mv+-------+>Vp | | --------> might represent a grammar in which a sentence (S) consists of a noun phrase (NP) followed by a verb phrase (VP). The NP transition succeeds if an optional article (Art) followed by a noun (Noun) can be read from input. Similarly, the VP transition succeeds if a verb is read from input, and an optional noun phrase can be "pushed". Clearly an RTN is no more powerful than a finite state parser, but it is easier to write grammars for! An ATN is an RTN extended to handle (virtually arbitrary) conditionals attached to the transitions. This was intended to capture some of the semantics (some would argue it's all syntax) of the language. For example, a part of a grammar might apply to prepositional phrases for "place where": these would check at the beginning of the phrase to make sure that the preposition was one of {to, from, at}. There is also a capability for storing values in registers on a "push". This is useful for handling relative clauses, for example, in the which the noun modified in the main sentence might be used as either the subject or object of the the relative clause. Tom
rentsch@unc.UUCP (Tim Rentsch) (03/07/84)
To find out about ATN's, a good place to start is:
Language as a Cognitive Process, Volume 1: Syntax
by Terry Winograd, Addison Wesley (I think), 1983
Lots of interesting stuff in this book.
Tim