Memory requirements and local ambiguities of parsing strategies

We present a method for calculating lower bounds on the space required and local ambiguities entailed by parsing strategies. A fast, compact natural language parser must implement a strategy with low space requirements and few local ambiguities. It is also widely assumed in the psycholinguistics literature that extremely limited short-term space is available to the human parser, and that sentences containing center-embedded constructions are incomprehensible because processing them requires more space than is available. However, we show that the parsing strategies most psycholinguists assume require less space for processing center-embedded constructions than for processing other perfectly comprehensible constructions. We present alternative strategies for which center-embedded constructions do require more space than other constructions.     

Effects of tasks on BOLD signal responses to sentence contrasts: Review and commentary

Functional neuroimaging studies of syntactic processing have been interpreted as identifying the neural locations of parsing and interpretive operations. However, current behavioral studies of sentence processing indicate that many operations occur simultaneously with parsing and interpretation. In this review, we point to issues that arise in discriminating the effects of these concurrent processes from those of the parser/interpreter in neural measures and to approaches that may help resolve them.     

Use of verb information in syntactic parsing: evidence from eye movements and word-by-word self-paced reading

We investigated whether readers use verb information to aid in their initial parsing of temporarily ambiguous sentences. In the first experiment, subjects' eye movements were recorded. In the second and third experiments, subjects read sentences by using a noncumulative and cumulative word-by-word self-paced paradigm, respectively. The results of the first two experiments supported Frazier and Rayner's (1982) garden-path model of sentence comprehension: Verb information did not influence the initial operation of the parser. The third experiment indicated that the cumulative version of the self-paced paradigm is not appropriate for studying on-line parsing. We conclude that verb information is not used by the parser to modify its initial parsing strategies, although it may be used to guide subsequent reanalysis.     

A program for parsing mouse movements into component submovements

Most current movement control theories include the idea that movement toward a target can be broken into several submovements. The complexity of analyzing a movement into its constituent submovement structure and the additional complexity imposed by the problem of noise in the data and hand tremor seem to be daunting to researchers. This paper discusses a program that can ameliorate both of these problems and parse movements into their constituent submovements. It also contains a graphing feature that is useful as a visual tool for analyzing submovement structure. The programs are easily modifiable, so that researchers can specify their own parsing rules on the basis of different assumptions about movement control and use the parser for data from different experimental tasks.     

Syntactic analysis in sentence comprehension: Effects of dependency types and grammatical constraints

This paper presents three experiments on the parsing of Italian wh-questions that manipulate the wh-type (whovs. which-N)and the whextraction site (main clause, dependent clause with or without complementizer). The aim of these manipulations is to see whether the parser is sensitive to the type of dependencies being processed and whether the processing effects can be explained by a unique processing principle, the minimal chain principle (MCP; De Vincenzi, 1991). The results show that the parser, following the MCP, prefers structures with fewer and less complex chains. In particular: (1) There is a processing advantage for the wh-subject extractions, the structures with less complex chains; (2) there is a processing dissociation between the whoand which questions; (3) the parser respects the principle that governs the well-formedness of the empty categories (ECP).     

The sausage machine: A new two-stage parsing model

It is proposed that the human sentence parsing device assigns phrase structure to word strings in two steps. The first stage parser assigns lexical and phrasal nodes to substrings of roughly six words. The second stage parser then adds higher nodes to link these phrasal packages together into a complete phrase marker.This model of the parser is compared with ATN models, and with the two-stage models of Kimball (1973) and Fodor, Bever and Garrett (1974). Our assumption that the units which are shunted from the first stage to the second stage are defined by their length, rather than by their syntactic type, explains the effects of constituent length on perceptual complexity in center embedded sentences and in sentences of the kind that fall under Kimball's principle of Right Association. The particular division of labor between the two parsing units allows us to explain, without appeal to any ad hoc parsing strategies, why the parser makes certain ‘shortsighted’ errors even though, in general, it is able to make intelligent use of all the information that is available to it.     

Simple,applied text parsing

Text parsing for use in linguistic or artificial intelligence research can often be ill-suited for use in other lines of investigation in which simple, problem-specific parsing techniques may be used. This paper describes the development of a simple text parser for use in a specific research setting. The resulting parsing programs are compact enough for easy use on most available m inland microcomputers, while still providing adequate results for some applications such as chunking text into small units for later presentation.     

Competition and recency in a hybrid network model of syntactic disambiguation

The competitive attachment model of human parsing is a hybrid connectionist architecture consisting of a distributed feature passing method for establishing syntactic relations within the network, and a numeric competition mechanism for resolving ambiguities, which applies to all syntactic relations. Because the approach employs a uniform mechanism for establishing syntactic relations, and a single competition mechanism for disambiguation, the model can capture general behaviors of the human parser that hold across a range of syntactic constructions. In particular, attachment and binding relations are similarly processed and are therefore subject to the very same influences of disambuguation and processing over time. An important influence on the competitive disambiguation process is distance within the network. Decay of numeric activation, along with distributed feature passing through the network structure, has an unavoidable effect on the outcome of attachment and binding competitions. Inherent properties of the model thus lead to a principled explanation of recency effects in the human parsing of both attachment and filler/gap ambiguities.     

Disfluencies and human language comprehension

Spoken language contains disfluencies, which include editing terms such as uh and um as well as repeats and corrections. In less than ten years the question of how disfluencies are handled by the human sentence comprehension system has gone from virtually ignored to a topic of major interest in computational linguistics and psycholinguistics. We discuss relevant empirical findings and describe a computational model that captures how disfluencies influence parsing and comprehension. The research reviewed shows that the parser, which presumably evolved to handle conversations, deals with disfluencies in a way that is efficient and linguistically principled. The success of this research program reinforces the current trend in cognitive science to view cognitive mechanisms as adaptations to real-world constraints and challenges.     

Head position and parsing ambiguity

A strongly principle-based model of parsing seeks to employ principles of the competence grammar directly in language processing. Within grammatical theory, the Projection Principle holds that each level of syntactic representation is a uniform projection of the lexical properties of heads. With respect to parsing this suggests that a phrasal node cannot be projected until the occurrence of its head and thus constitutes a strong empirical hypothesis concerning the fundamental nature of human language processing. This paper contrasts some cross-linguistic predictions made by a specific Grammarderived parsing model against those of a well-known top-down model whose functional motivation is decidedly nonlinguistic. This latter Minimal Attachment model is found to predict significant difficulty with respect to the processing of languages such as Japanese, which display rather different surface properties than English. This problem is not encountered in a model which recognizes the crucial role of heads in licensing argument structure with respect to Processing as well as Grammar. Cross-linguistic parsing differences are attributed to the linear and structural positions of licensing heads which constitute the primary locus of the cross-linguistic variation which is therefore ultimately to be ascribed directly to the Projection Principle.     

Disfluencies, language comprehension, and Tree Adjoining Grammars

Disfluencies include editing terms such as uh and um as well as repeats and revisions. Little is known about how disfluencies are processed, and there has been next to no research focused on the way that disfluencies affect structure-building operations during comprehension. We review major findings from both computational linguistics and psycholinguistics, and then we summarize the results of our own work which centers on how the parser behaves when it encounters a disfluency. We describe some new research showing that information associated with misarticulated verbs lingers, and which adds to the large body of data on the critical influence of verb argument structures on sentence comprehension. The paper also presents a model of disfluency processing. The parser uses a Tree Adjoining Grammar to build phrase structure. In this approach, filled and unfilled pauses affect the timing of Substitution operations. Repairs and corrections are handled by a mechanism we term “Overlay,” which allows the parser to overwrite an undesired tree with the appropriate, correct tree. This model of disfluency processing highlights the need for the parser to sometimes coordinate the mechanisms that perform garden-path reanalysis with those that do disfluency repair. The research program as a whole demonstrates that it is possible to study disfluencies systematically and to learn how the parser handles filler material and mistakes. It also showcases the power of Tree Adjoining Grammars, a formalism developed by Aravind Joshi which has yielded results in many different areas of linguistics and cognitive science.     

Expectation-based syntactic comprehension

This paper investigates the role of resource allocation as a source of processing difficulty in human sentence comprehension. The paper proposes a simple information-theoretic characterization of processing difficulty as the work incurred by resource reallocation during parallel, incremental, probabilistic disambiguation in sentence comprehension, and demonstrates its equivalence to the theory of Hale [Hale, J. (2001). A probabilistic Earley parser as a psycholinguistic model. In Proceedings of NAACL (Vol. 2, pp. 159-166)], in which the difficulty of a word is proportional to its surprisal (its negative log-probability) in the context within which it appears. This proposal subsumes and clarifies findings that high-constraint contexts can facilitate lexical processing, and connects these findings to well-known models of parallel constraint-based comprehension. In addition, the theory leads to a number of specific predictions about the role of expectation in syntactic comprehension, including the reversal of locality-based difficulty patterns in syntactically constrained contexts, and conditions under which increased ambiguity facilitates processing. The paper examines a range of established results bearing on these predictions, and shows that they are largely consistent with the surprisal theory.     

Parsing to Learn

Learning a language by parameter setting is almost certainly less onerous than composing a grammar from scratch. But recent computational modeling of how parameters are set has shown that it is not at all the simple mechanical process sometimes imagined. Sentences must be parsed to discover the properties that select between parameter values. But the sentences that drive learning cannot be parsed with the learner's current grammar. And there is not much point in parsing them with just one new grammar. They must apparently be parsed with all possible grammars, in order to find out which one is most successful at licensing the language. The research task is to reconcile this with the fact that the human sentence parsing mechanism, even in adults, has only very limited parallel parsing capacity. I have proposed that all possible grammars can be folded into one, if parameter values are fragments of sentential tree structures that the parser can make use of where necessary to assign a structure to an input sentence. However, the problem of capacity limitations remains. The combined grammar will afford multiple analyses for some sentences, too many to be computed on-line. I propose that the parser computes only one analysis per sentence but can detect ambiguity, and that the learner makes use of unambiguous input only. This provides secure information but relatively little of it, particularly at early stages of learning where few grammars have been excluded and ambiguity is rife. I consider three solutions: improving the parser's ability to extract unambiguous information from partially ambiguous sentences, assuming default parameter values to temporarily eliminate ambiguity, reconfiguring the parameters so that some are subordinate to others and do not present themselves to the learner until the others have been set. A more radical alternative is to give up the quest for error-free learning and permit parameters to be set without regard for whether the parser may have overlooked an alternative analysis of the sentence. If it can be assumed that the human parser keeps a running tally of the parameter values it has accessed, then the learner would do nothing other than parse sentences for comprehension, as adults do. The most useful parameter values would become more and more easily accessed; the noncontributors would drop out of the running. There would be no learning mechanism at all, over and above the parser. But how accurate this system would be remains to be established.     

Learning To Parse?

A strong claim about human sentence comprehension is that the processing mechanism is fully innate and applies differently to different languages only to the extent that their grammars differ. If so, there is hope for an explanatory project which attributes all parsing strategies to fundamental design characteristics of the parsing device. However, the whole explanatory program is in peril because of the discovery (Cuetos & Mitchell, 1988) that Late Closure is not universal: Spanish, and also Dutch and other languages, favor Early Closure (high attachment) where English favors Late Closure flow attachment). I argue that the universal parser can weather this storm. Exceptions to Late Closure in Spanish and other languages are observed only in one construction (a relative clause attaching into a complex noun phrase [NP]), which is borderline in English too. For other constructions, low attachment is preferred in all languages tested. I propose that what differentiates the complex NP construction is the heaviness of the attachee compared to that of the host configuration. A relative clause is a heavy attachee, and the lower NP alone is small as a host; the relative is therefore better balanced if the whole complex NP is its host. A wide range of facts is accounted for by the principle that a constituent likes to have a sister of its own size. Light constituents will tend to attach low, and heavy ones to attach high, since larger constituents are dominated by higher nodes. A preference for balanced weight is familiar from work on prosodic phrasing. I suggest, therefore, that prosodic processing occurs in parallel with syntactic processing (even in reading) and influences structural ambiguity resolution. Height of attachment ambiguities are resolved by the prosodically motivated same-size-sister constraint. The exceptional behavior of English may be due to its prosodic packaging of a relative pronoun with the adjacent noun, overriding the balance tendency. If this explanation is correct, it is possible that all cross-language variations in parsing preferences are due to cross-language variations in the prosodic component of the competence grammar.     

A Probabilistic Model of Lexical and Syntactic Access and Disambiguation

The problems of access—retrieving linguistic structure from some mental grammar —and disambiguation—choosing among these structures to correctly parse ambiguous linguistic input—are fundamental to language understanding. The literature abounds with psychological results on lexical access, the access of idioms, syntactic rule access, parsing preferences, syntactic disambiguation, and the processing of garden-path sentences. Unfortunately, it has been difficult to combine models which account for these results to build a general, uniform model of access and disambiguation at the lexical, idiomatic, and syntactic levels. For example, psycholinguistic theories of lexical access and idiom access and parsing theories of syntactic rule access have almost no commonality in methodology or coverage of psycholinguistic data. This article presents a single probabilistic algorithm which models both the access and disambiguation of linguistic knowledge. The algorithm is based on a parallel parser which ranks constructions for access, and interpretations for disambiguation, by their conditional probability. Low-ranked constructions and interpretations are pruned through beam-search; this pruning accounts, among other things, for the garden-path effect. I show that this motivated probabilistic treatment accounts for a wide variety of psycholinguistic results, arguing for a more uniform representation of linguistic knowledge and for the use of probabilistically-enriched grammars and interpreters as models of human knowledge of and processing of language.     

Parsing as a Cue-Based Retrieval Model

This paper develops a novel psycholinguistic parser and tests it against experimental and corpus reading data. The parser builds on the recent research into memory structures, which argues that memory retrieval is content-addressable and cue-based. It is shown that the theory of cue-based memory systems can be combined with transition-based parsing to produce a parser that, when combined with the cognitive architecture ACT-R, can model reading and predict online behavioral measures (reading times and regressions). The parser's modeling capacities are tested against self-paced reading experimental data (Grodner & Gibson, 2005), eye-tracking experimental data (Staub, 2011), and a self-paced reading corpus (Futrell et al., 2018).     

A computational model of human parsing

This report describeslicensing-structure parsing (LS-parsing), a computational model of human parsing. LS-parsing corresponds to human parsing at three points: (1) the order in which the LS parser builds nodes is psychologically more accurate than the orders in which either LL or LR parsers build nodes, (2) the LS parser's preferences in resolving local ambiguities are preferable to Frazier's strategies on both empirical and theoretical grounds, and (3) the backtracking strategies the parser uses when it has made an error at an earlier choice point model the distinction betweenweak andstrong garden paths-strong garden paths being irrecoverable, weak garden paths causing psychological difficulty, but not preventing recovery of the correct structure.     

Against repair-based reanalysis in sentence comprehension

Structural reanalysis is generally assumed to be representation-preserving, whereby the initial analysis is manipulated or repaired to arrive at a new structure. This paper contends that the theoretical and empirical basis for such approaches is weak. A conceptually simpler alternative is that the processor reprocesses (some portion of) the input using just those structure-building operations available in first-pass parsing. This reprocessing is a necessary component of any realistic processing model. By contrast, the structural revisions required for second-pass repair are more powerful than warranted by the abilities of the first-pass parser. This paper also reviews experimental evidence for repair presented by Sturt, Pickering, and Crocker (1999). We demonstrate that the Sturt et al. findings are consistent with a reprocessing account and present a self-paced reading experiment intended to tease apart the repair and reprocessing accounts. The results support a reprocessing interpretation of Sturt et al.'s data, rendering a repair-based explanation superfluous.