DOC PREVIEW
UMBC CMSC 331 - Parsing with ATNs

This preview shows page 1-2-3-4-5 out of 16 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

23Parsing with ATNsThis chapter shows how to write a nondeterministic parser as an embedded lan-guage. The first part explains whatATN parsers are, and how they representgrammar rules. The second part presents anATN compiler which uses the nonde-terministic operators defined in the previous chapter. The final sections present asmallATN grammar, and show it in action parsing sample input.23.1 BackgroundAugmented Transition Networks, or ATNs, are a form of parser described byBill Woods in 1970. Since then they have become a widely used formalism for ◦parsing natural language. In an hour you can write anATN grammar which parsesinteresting English sentences. For this reason, people are often held in a sort ofspell when they first encounter them.In the 1970s, some people thought thatATNs might one day be componentsof truly intelligent-seeming programs. Though few hold this position today,ATNshave found a niche. They aren’t as good as you are at parsing English, but theycan still parse an impressive variety of sentences.ATNs are useful if you observe the following four restrictions:1. Use them in a semantically limited domain—in a front-end to a particulardatabase, for example.2. Don’t feed them very difficult input. Among other things, don’t expectthem to understand wildly ungrammatical sentences the way people can.305306 PARSING WITH ATNS3. Only use them for English, or other languages in which word order deter-mines grammatical structure. ATNs would not be useful in parsing inflectedlanguages like Latin.4. Don’t expect them to work all the time. Use them in applications where it’shelpful if they work ninety percent of the time, not those where it’s criticalthat they work a hundred percent of the time.Within these limits there are plenty of useful applications. The canonical exampleis as the front-end of a database. If you attach anATN-driven interface to sucha system, then instead of making a formal query, users can ask questions in aconstrained form of English.23.2 The FormalismTo understand what ATNs do, we should recall their full name: augmented transi-tion networks. A transition network is a set of nodes joined together by directedarcs—essentially, a flow-chart. One node is designated the start node, and someother nodes are designated terminal nodes. Conditions are attached to each arc,which have to be met before the arc can be followed. There will be an inputsentence, with a pointer to the current word. Following some arcs will cause thepointer to be advanced. To parse a sentence on a transition network is to find apath from the start node to some terminal node, along which all the conditionscan be met.ATNs add two features to this model:1. ATNs have registers—named slots for storing away information as the parseproceeds. As well as performing tests, arcs can modify the contents of theregisters.2. ATNs are recursive. Arcs may require that, in order to follow them, theparse must successfully make it through some sub-network.Terminal nodes use the information which has accumulated in the registers tobuild list structures, which they return in much the same way that functions returnvalues. In fact, with the exception of being nondeterministic,ATNs behave a lotlike a functional programming language.TheATN defined in Figure 23.1 is nearly the simplest possible. It parses noun-verb sentences of the form “Spot runs.” The network representation of thisATN isshown in Figure 23.2.What does thisATN do when giventhe input(spot runs)? The first nodehasone outgoing arc, a cat, or category arc, leading to node s2. It says, effectively,23.2 THE FORMALISM 307(defnode s(cat noun s2(setr subj *)))(defnode s2(cat verb s3(setr v *)))(defnode s3(up ‘(sentence(subject ,(getr subj))(verb ,(getr v)))))Figure 23.1: A very small ATN.Figure 23.2: Graph of a small ATN.you can follow me if the current word is a noun, and if you do, you must storethe current word (indicated by *)inthesubj register. So we leave this node withspot stored in the subj register.There is always a pointer to the current word. Initially it points to the firstword in the sentence. When cat arcs are followed, this pointer is moved forwardone. So when we get to node s2, the current word is the second, runs. Thesecond arc is just like the first, except that it is looking for a verb. It finds runs,stores it in register v, and proceeds to s3.The final node, s3, has only a pop, or terminal, arc. (Nodes with pop arcs havedashed borders.) Because we arrive at the pop arc just as we run out of input, wehave a successful parse. The pop arc returns the backquoted expression within it:(sentence (subject spot)(verb runs))AnATN corresponds to the grammar of the language it is designed to parse. Adecent-sizedATN for parsing English will have a main network for parsing sen-308 PARSING WITH ATNStences, and sub-networks for parsing noun-phrases, prepositional phrases, modi-fier groups, and so on. The need for recursion is obvious when we consider thatnoun-phrasesmaycontain prepositionalphrases which may contain noun-phrases,ad infinitum, as in“the key on the table in the hall of the house on the hill”23.3 NondeterminismAlthough we didn’t see it in this small example, ATNs are nondeterministic. Anode can have several outgoing arcs, more than one of which could be followedwith a given input. For example, a reasonably goodATN should be able to parsebothimperativeanddeclarativesentences. Thus the first node could have outgoingcat arcs for both nouns (in statements) and verbs (in commands).What if the first word of the sentence is “time,” which is both a noun and averb? How does the parser know which arc to follow? WhenATNs are describedas nondeterministic, it means that users can assume that the parser will correctlyguess which arc to follow. If some arcs lead only to failed parses, they won’t befollowed.In reality the parser cannot look into the future. It simulates correct guessingby backtracking when it runs out of arcs, or input. But all the machinery ofbacktracking is inserted automaticallyinto the codegeneratedbytheATN compiler.We can writeATNs as if the parser really could guess which arcs to follow.Like many (perhaps most) programs which use nondeterminism,ATNs usethe depth-first implementation. Experience parsing English quickly teaches onethat any given sentence has a slew of legal parsings, most of them junk. On aconventional single-processor machine, one is better off trying to get good parsesquickly.


View Full Document

UMBC CMSC 331 - Parsing with ATNs

Documents in this Course
Semantics

Semantics

14 pages

Java

Java

12 pages

Java

Java

31 pages

V

V

46 pages

Semantics

Semantics

11 pages

Load more
Download Parsing with ATNs
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Parsing with ATNs and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Parsing with ATNs 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?