Sentence Disambiguation by a Shift-Reduce Parsing Technique

1. Introduction

For natural language proce11sing systems to be useful , they must assign the same interpretation to a given sentence that a native speaker would, since that is precisely the behavior users will expect. Consider, for example, the case of ambiguous sen­ tences. Native speakers of English show definite and consistent preferences for certain readings of syntactically ambiguous sen­ tences [Kimball , 1973, Frazier and Fodor, 1978, Ford t:t al., 1982] . A user of a natural-language-processing system would naturally expect it to reflect the same preferences. Thus, such systems must model in some way the lingui1tic performance as well as the lir~gui1tic competence of the native speaker.

This idea is certainly not new in the artificial-intelligence lit.erature. The pioneering work of Marcus [Marcus, 1980] is per­ haps the best known example of linguistic-performance modeling in AI. Starting from the hypothesis that "deterministic" parsing of English is possible, he demonstrated that certain performance constraints, e.g., the difficulty of parsing garden-path sentences, could be modeled. His claim about deterministic parsing was The interpreter cannot use some general rule to take a nondeterministic grammar specification and im­ pose arbitrary constraints to convert it to a deter­ ministic specification (unless, of course, there is a general rule which will always lead to the correct decision in such a case). [Marcus, 1980, p.14]

·This research was supported by the Defense Advanced Research Projects Systems Command . The views and conclusions contained in this document are t hose of the author and should not be interpreted as representatiYe of t he offi cial policies, either expressed or implied, of the Defense Advanced

Agency under Contract N00031l·80-C·0575 wi th the Naval Electronic Research Project· Agency or the United States government .

We have developed and implemented a parsing system that., given a nondeterministic grammar, forces disambiguation in just the manner Marcus rejected (i .e. through general rules); it. thereby exhibits the same preference behavior that psycholin­ guists have attributed to native speakers of English for a cer­ tain range of ambiguities. These include structural ambiguities [Frazier and Fodor, 1978, Frazier and Fodor, 1980, Wanner, 1980] and lexical preferences [Ford. eta/., 1982], as well as the garden­ path sentences as a side effect . The parsing system is based on the shift.-reduce scheduling technique of Pereira [forthcoming] .

Our parsing algorithm is a slight variant of LALR(1) pars­ ing, and , as such, exhibits the three conditions postulated by Marcus for a deterministic mechanism: it is data-driven, reflects expectations, and has look-ahead. Like Marcus's parser, our parsing syst.em is deterministic . Unlike Marcus's parser, the grammars used by our parser can be ambiguous.

2. The Phenomena to be Modeled

The parsing system was designed to manifest preferences among structurally distinct parses of ambiguous sentences. It does this by building just one parse tree- rather than build­ ing mul t iple parse trees and choosing among them. Like the Marcus parsing system, ours does not do disambiguation requir­ ing "extensive semantic processing," but, in contrast to Marcus, it does handle such phenomena as PP-attachment insofar as there exist a priori preferences for one attachment over another. By a priori we mean preferences that are exhibited in contexts where pragmat ic or plausibility considerations do not tend to favor one reading over the other. Rather than make such value judgments ourselves, we defer to the psycholinguistic literature ( specificall~· [Frazier and Fodor, 1978], [Frazier and Fodor, 1980] and [Ford et a/., 1982]) for our examples.

The parsing system models the following phenomena:

Right Association constituents are "attached low." For instance, in the sen­ tence Joe bought the book that I had been trying to obtain for Su8an.

the preferred reading is one in which the prepositional phrase "for Susan" is associated with "to obtain" rather than "bought."

Minimal Attachment

On the other hand, higher attachment is preferred in cer­ tain cases such as

Joe bought the book for Su8an.

in which "for Susan" modifies "the book" rather than "bought." Frazier and Fodor (1978] note that these are cases in which the higher attachment includes fewer nodes in the parse tree. Our analysis is somewhat different.

Lexical Preference

Ford et a/. [1982] present evidence that attachment preferences depend on lexical choice. Thus, the preferred reading for

The woman wanted the dreu on that rack.

has low attachment of the PP, whereas

The woman po8itioned the dreu on that rack.

has high attachment.

Garden-Path Sentence11

Grammatical sentences such as

The horu raced pa&t the barn fell.

seem actually to receive no parse by the nat.ive speaker until some sort of "conscious parsing" is done. Following ~!arcus (Marcus, 1980], we take this to be a hard failure of the human sentence-processing mechanism.

It will be seen that all these phenomena are handled in our parser by the same general rules. The simple context-free gram­ mar used1 (see Appendix I) allows both parses of the ambiguous sentences as well as one for the garden-path sentences. The par­ ser disambiguates the grammar and yields only the preferred struct.ure. The actual output of the parsing system can be found in Appendix II of (Shieber, 1983].

3. The Parsing System

The parsing system we use is a shift-reduce parser. Shift­ reduce parsers [Abo and Johnson, 1974] are a very general class of bottom-up parsers characterized by the following architecture. They incorporate a a tack for holding constituents built up during the parse and a ahr/1-redure table for guiding the parse. At each step in the parse, the table is used for deciding between two basic types or operations: the ·hift operation, which adds the next word in the sentence (with its preterminal category) to the top of the stack, and the reduce operation, which temoves several elements from the top or the stack and replaces them with a new element- for instance, removing an NP and a VP from the top of the stack and replacing them with an S. The 8tate of the parser is also updated in accordance with the shift-reduce table at each stage. The combination of the stack, input, and state of the parser will be called a configuration and will be notated as, for example, where the stack contains the nonterminals NP and V, the input contains the lexical item Mary and the parser is in state 10.

lwe make no claims as to the accuracy or the sample grammar . h is obviously a gross simplification of English syntax . hs role is merely to show that the parsing system is able to disambiguate the sentences under consideration correctly.

By way of example, we demonstrate the operation of the parser (using the grammar of Appendix I) on the oft-cited sen­ tence "John loves Mary." Initially the stack is empty and no input has been consumed. The parser begins in state 0.

As elements are shifted to the stack, they are replaced by their preterminal category. 2 The shift-reduce table for the grammar of Appendix I states that in state 0, with a proper noun as the next word in the input, the appropriate action is a shift. The new configuration, therefore, is

The next operation specified is a reduction of the proper noun to a noun phrase yielding

NP 11/ovea Mary

2

The verb and second proper noun are nbw shifted, in accordance with the shift-reduce table, exhausting the input, and the proper noun is then reduced to an NP.

Finally, the verb and noun phrase on the top or the stack are reduced to a VP

which is in turn reduced, together with the subject NP, to an S.

This final configuration is an accepting configuration, since all tbC' input bas been consumed and an S derived. Thus the sen­ tence is grammatical in the grammar of Appendix I, as expected.

2But see Section 3.2 for an exception.

3.1 Differences from the Standard LR Techniques

The shift-reduce table mentioned above is generated automatically from a context-free grammar by the standard al­ gorithm [Aho and Johnson, 1974). The parsing alogrithm differs, however , from the standard LALR(l) parsing algorithm in two ways . First, instead of assigning preterminal symbols to words as they are shifted, the algorithm allows the assignment to be delayed if the word is ambiguous among preterminals. When the word is used in a reduction, the appropriate preterminal 1s assigned.

Second, and most importantly, since true LR parsers exist only for unambiguous grammars, the normal algorithm for deriv­ ing LALR( 1) shift-reduce tables yields a table that may specify conflict ing actions under certain configurations. It is through the choice made from the options in a conflict that the preference behavior we desire is engendered.

3.2 Preterminal Delaying

One key advantage of shift-reduce parsing that is critical in our system is the fact that decisions about the structure to be assigned to a phrase are postponed as long as possible. In keeping with this general principle, we extend the algorithm to allow the assignment of a preterminal category to a lexical item to be deferred until a decision is forced upon it, so to speak, by an encompassing reduction. For instance, we would not want. to decide on the preterminal category of the word "that," which can serve as either a determiner (DET) or complementizer (THAT), until some further informat ion is available. Consider the sentences

That problem i~ important:

That problems are difficult to ~olve i~ important .

Instead of assigning a preterminal to "that," we leave open the possibility of assigning either DET or THAT until the first reduc­ tion that involves the word. In the first case, this reduction will be by the rule NP --+ DET NOM, thus forcing, once and for all , the assignment of DET as preterminal. In the second case, the DET NOM analysis is disallowed on the basis of number agreement , so that the first applicable reduction is the COMP S reduction to ·s, forcing the assignment of THAT as preterminal.

or course, the question arises as to what state the par­ ser goes into after shifting the lexical item "that." The answer is quite straightforward, though its interpretation vi~ a vi~ the determinism hypothesis is subtle. The simple answer is that the parser enters into a state corresponding to the union of the stat es entered upon shifting a DET and upon shifting a THAT respectively, in much the same way as the deterministic simula­ tion of a nondeterministic finite automaton enters a "union" state when faced with a nondeterministic choice. Are we then merely simulating a nondeterministic machine here! The answer is equivocal. Although the implementation acts as a simulator for a nondeterministic machine, the nondeterminism is a priori bounded, given a particular grammar and lexicon.3 Thus, the nondl'terminism could be traded in for a larger, albeit still finite, set of states, unlike the nondeterminism found in other pars­ ing algorithms. Anothl'r way of looking at the situation is to note that there is no observable property of the algorithm that would distinguish the operation of the parser from a determinis­ tic onl'. In some sense, there is no interesting difference between the limited nondeterminism of this parser, and Marcus's notion of strict determinism. In fact , the implementation of Marcus's parser also embodies a bounded nondeterminism in much the same way this parser does.

The differentiating property between this parser and that of Marcus is a slightly different one, namely, the property of quasi-real-time operation. 4 By quasi-real-time operation, Marcus means that there exists a maximum interval of parser operation for which no output can be generated. If the parser operates for longer than this, it must generate some output. For instance, the parser might be guaranteed to produce output (i.e., struc­ ture) at least every three words. However, because preterminal assignment can be delayed indefinitely in pathological grammars, there may exist sentences in such grammars for which arbitrary numbers of words need to be read before output can be produced. It is not clear whether this is a real disadvantage or not, and, if so, whether there are simple adjustments to the algorithm that would result in quasi-real-time behavior. In fact, it is a property of bot tom-up parsing in general that quasi-real-time behavior is not. guaranteed. Our parser has a less restrictive but similar property, fairneu, that is, our parser generates output linear in the input, though there is no constant over which out­ put. is guaranteed. For a fuller discussion of these properties, see Pereira and Shieber [forthcoming] .

To summarize, preterminal delaying, as an intrinsic part of the algori thm, does not actually change the basic properties of the algori thm in any observable way. Note, however, that preterminal assignments, like reductions, are irrevocable once they are made (as a byproduct of the determinism of the algo­ rithm). Such decisions can therefore lead to garden paths, as they do for the sentences presented in Section 3.6.

We now discuss the central feature of the algorithm, namely, the resolution of shift-reduce conflicts.

3.3 The Disambiguation Rules

Conflicts arise in two ways: ~hift- reduce conflicts, in which the parser has t.he option of either shifting a word onto the stack or reducing a set of elements on the stack to a new element; reduce-reduce conflicts, in which reductions by several grammar rules are possible. The parser uses two rules to resolve these conflicts: 5

3 The boundedness comes about because only a finite amount or inform:.­ tion is kept per state (an integer) and the nondeterminism stops at the preterminal level, so that the splitting or states does not propagate.

4 1 am indebted to Mitch Marcus for this observation and the previous comparison wi th his parser.

• (I) Resolve shift-reduce conflicts by shifting.
• Resolve reduce-reduce conflicts by performing the longer reduction.

These two rules suffice to engender the appropriate be­ havior in the parser for cases of right association and minimal attachment. Though we demonstrate our system primarily with PP-attachment examples, we claim that the rules are generally valid for the phenomena being modeled (Pereira and Shieber, forthcoming].

3.4 Some Examples

Some examples demonstrate these principles. Consider the sentence

Joe took the book that I bought for Suun.

After a certain amount of parsing has been completed deter­ ministically, the parser will be in the following configuration:

NP v NP that NP v II for su~an

with a shift-reduce conflict, since the V can be reduced to a VP / NP 6 or the P can be shifted. The principles presented would solve the conflict in favor of the shift, thereby leading to the following derivation:

which yields the structure:

[s Joe[vptook[NP[Npthe book][5 that I bought for Susan]]]]

The sentence Joe bought the book for Su6an.

5The original notion or using a shift-reduce parser and general scheduling principles to handle right association and minimal attachment , together with the following two rules, are due to Fernando Pereira (Pereira, 1982( . The formalization of preterminal delaying and the extensions to the lexical­ preference cases and garden-path behavior are due to the author .

6 The "slash-category" analysis or long-distance dependencies used here is loosely based on the work or Gazdar (1981] . The Appendix I grammar does not incorporate the full range or slashed rules, however, but merely a representative selection for illustrative purposes .

demonstrates resolution of a reduce-reduce conflict. At some point in the parse, the parser is in the following configuration:

with a reduce-reduce conflict. Either a more complex NP or a VP can be built. The conflict is resolved in favor of the longer reduction, i.e., the VP reduction. The derivation continues:

ending in an accepting state with the following generated struc­ ture:

[sJoe(vpbought(Npthe book](ppfor Susan]]]

3.5 Lexi cal Preference

To handle the lexical-preference examples, we extend the second rule slightly. Preterminal-word pairs can he stipulated as either weak or ~trong. The second rule becomes

1. Resolve reduce-reduce conflicts by performing the longest reduction with the ~tronge~t leftmo6t 6lack element.1

Therefore, if it is assumed that the lexicon encodes the information that the triadic form of "want" (V2 in the sample grammar) and the dyadic form of "position" (V1) are both weak, we can sec the operation of the shift-reduce parser on the "dress on that rack" sentences of Section 2. Both sentences are similar in form and will thus have a similar configuration when the reduce-reduce conflict arises. For example, the first sentence will be in the following configuration:

In this case, the longer reduction would require assignment of the preterminal category V2 to "want," which is the weak form; thus, the shorter reduction will be preferred, leading to the derivation:

and the underlying structure:

[sthe woman(vpwanted[NP[Npthe dress](ppon that rack]]]]

7Note that strength takes precedence over length .

In the case in which the verb is "positioned," however, the longer reduction does not yield the weak form of the verb; it will there­ fore be invoked, resulting in the structure:

[sthe woman[yppositioned[Npthe dress][ppon that rack]]]

3.6 Garden-Path Sentences

As a side effect of these conflict resolution rules, certain sentences in the language of the grammar will receive no parse by the parsing system just discussed. These sentences are ap­ parently the ones classified as "garden-path" sentences, a class that humans also have great difficulty parsing. Marcus's conjec­ ture that such difficulty stems from a hard failure of the normal sentence-processing mechanism is directly modeled by the pars­ ing system presented here.

For instance, the sentence

The horae raced pad the barn fell.

exhibits a reduce-reduce conflict before the last word. If the participial form of "raced" is weak, the finite verb form will be chosen; consequently, "raced past the barn" will be reduced to a VP rather than a participial phrase. The parser will fail shortly, since the correct choice of reduction was not made.

Similarly, the sentence

That ualy, deep-aea fiah ahould be underwater ia impor­ tant.

will fail, though grammatical. Before the word "should" is shifted, a reduce-reduce conflict arises in forming an NP from either "That scaly, deep-sea fish" or "scaly, deep-sea fish." The longer (incorrect) reduction will be performed and the parser will fail.

Other examples, e.g., "the boy got fat melted," or "the prime number few" would be handled similarly by the parser, though the sample grammar of Appendix I does not parse them [Pereira and Shieber, forthcoming].

4. Conclusion

To be useful, natural-language systems must model the behavior, if not the method, of the native speaker. We have demonstrated that a parser using simple general rules for disam­ biguating sentences can yield appropriate behavior for a large class of performance phenomena-right association, minimal at­ tachment , lexical preference, and garden-path sentences-and that, morever, it can do so deterministically without generating all the parses and choosing among them. The parsing system has been implemented and has confirmed the feasibility of our approach to the modeling of these phenomena.