AN EARLIER VERSION OF THIS PAPER WAS PRESENTED AT THE 1965 CONTE...

3506. An earlier version of this paper was presented at the 1965

context-sensitivity in a grammar but one should talk of

International Conference on Computational Linguistics, New York,

degrees of context-sensitivity. In order, therefore, to

May 19-21.

2

tions are pertinent in the case of a grammar having

parse natural-language data adequately, the parsing

sufficient context-sensitivity to serve the needs of syn-

system has to have not merely some fixed capability of

tactic recognition adequate for the machine translation

being sensitive to a certain range of contexts but a

of natural languages.

capacity to increase its context-sensitivity.

a) Since the table will tend to be increasingly com-

This means that the most significant alterations in

grammar rules from the standpoint of natural-language

plex because of the requirement of high context-sensi-

tivity, a dictionary-type binary lookup may no longer

parsing will not be those that affect the formation of

particular rules within the same format. Rather, those

be sufficient. Rather, it may become necessary to de-

vise an algorithm for searching the table in such a

alternatives that will really make a difference in the

way that the graduation of contextual conditions is

adequacy of the parsings of natural-language sentences

taken into account properly.

will be alterations of the format itself in terms of in-

b) Revisions of the rules in such a complex table

creasing the degree of context-sensitivity. This in effect

will not be as simple a matter as it seems, because it

means that the simplicity claimed for a separate table

of rules with a constant algorithm turns out to be il-

will no longer be obvious which of the rules is to be

modified in a given case, nor will it be obvious where

lusory, since the proponents of this concept of simplic-

in the table this rule can be found. Likewise, it will

ity admit that it applies only when the rules are held to

the same format.

not be obvious what contextual conditions will have to