A Breadth-First Parsing Model
Proceedings of the Eighth International Joint Conference on Artificial Intelligence. Natural Language. Pages 696-697.
© 1983 International Joint Conferences on Artificial Intelligence
Abstract
Recent attempts at modeling humans' abilitiesat processing natural language have centered around depth first parsing algorithms, and control strategies for making the best choices for disambiguation and attachment. This paper proposes a breadth-first algor ithrn as a model. The algorithm avoids sane of the carrnon pitfalls of depth-first approaches regarding ambiguity, and by using more pre-canputed information about the grammar, avoids sane of the usual proolans of parallel parsing algorithms as well.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1. Parsing Models
In the study of canputational rnodels of human language processing, cognitive scientists sean to have given little attention to all-paths p:1rsers, focusing instead on depth-first algorithms. This restriction is imposed so that the models will be consistent with the fact that people do not generally perceive ambiguities. In addition, it is an attempt to stay in line with the hypothesis that people p:1rse sentences in linear tirre. The idea is that the fewer alternatives considered, the faster the p:1rse tirre should be. The fastest way, of course, would be a depth first parse which made the right choice at every step of the way, hence the interest in deterministic parsers. The attempt to find principles which would guide ·a parser correctly through a depth-first search, led (Kinball, 1973) to fonrulate the principles of Right Association and Closure. (Frazier and Fodor, 1978) propose their avn principles: Minimal Attachment and Local Association. In addition (Church, 1980) proposes the A-over-A Early Closure Principle, and (Ford, Bresnan, and Kaplan, 1981) propose the principles of Lexical Preference am Final Argurrents. All of these principles try to account for heM a top-down depth-first parser could get the preferred readings of sentences. Havever, the point I would like to make here is that for each choice point in an ambiguous example, there is a secorx'l alternative which the parser needs to be able to get at least sane of the tirre. As (Crain am Steedman, 1981) point out, the fact that people generally only perceive one reading of a sentence is perfectly consistent
A BREADI'H-FIRSI' PARSIN3 M)DEL
John Bear
Linguistics Research Center University of Texas Austin, Texas 78712 U.S.A.
with a parsing model which finds all the possible syntactic ramifications fran looking at a word, does sane contextual filtering to decide which alternative(s) to keep, and then looks at a new word and rep:!ats. Given this, it is not dJvious that the breadth-first approach is inferior.
2. A Breadth First Parser
Since (Earley's, 1970) and (Pratt's, 1975) demonstrations of hav a parser can work both bott~up, and top-down, there have been several proposals for hav this information might be used to good effect in a psychological model. (Chester, 1980) proposes a depth-first left-corner parser which uses top-davn information. (Martin, Church, and Patil, 1981) propose an all p:1ths parser very similar to the one presented here. Both of the parsers just mentioned fit roughly into the framework presented in (Kay, 1980), which allavs for intelligent left-corner parsers which can be botton-up or top-down, or anything in between. The basic idea behind these P.=~rsers is that they always have access to two 'kinds of information: what categories may cane next (top down), and what word actually is next (bottom-up). The modification suggested here is the incorporation of two lod<-ahead buffers, and the abolishment of all inactive edges.
2.1. Reachability
We start with a discussion of what (Pratt, 1975) calls "precedence", and (Kay 1980) calls "reachability". A category A is reachable fran a category R iff there is a derivation tree of R which has A on its left branch. In addition, a lat.~ of a rule [X --> Y1 Y 2 ··· Ynl is the first element on the right side Of the arrow, Y1· In the example below,. A, B, and C are all reachable fran R.
1.

2.2. Basic Algorithm
Tre p;~rser uses a chart as in (Kay, 1980J · The junctures between the words are called vertices and are labelled with numbers.
The parser stores information on the vertices in the form of edges. Trese edges represent partially completed constituents. In Kay's tenus, they would be "active". Each edge contains a category, a completion, and a start vertex. The category tells what the constituent will build up to when the rest of the daughters have been found. The completion, to use a term from (Winograd, 1983), indicates which of the daughters still need to be fouro. The start vertex shows the left errl of the partial constituent. For instance consider the example below.
2.

Given . that "ducks" can build to an NP, and that there is a rule [S --> NP VPJ in the grammar, the example shows that an edge may be stored at V1 going back to VO, and representing an S missing a VP.
Tre algorithm uses three main functions, Parse, Extend-Edges, and Ne"~r"Constit. The function Parse looks at the words in the input string one word at a time, considering all the ramifications fran one word before going on to the next. It keeps track of where it is with the Current Vertex, the vertex ill11!ediately to the right of the newest word looked at. The Previous Vertex is the vertex ill11!ediately before it. For each word, Parse calls Ne"~r"Constit.
Informally, for words and for each new constituent built, the procedure Ne"~r"Constit does three things. 1) It builds edges which are incomplete but which have just found their first daughter. 2) It tries to add the new-constituent as a daughter to other incomplete constituents to its left via the function Exterrl-Edges. Arrl 3) for unit productions which can build up the constituent, the procedure New-Ccnstit calls itself recursively.
The function Extend-Edges combines an incomplete constituent with a completed constituent to its right. If the result is a completed constituent, it calls New-Ccnstit. If the new constituent still lacks one or more daughters, a new edge is created arrl stored at the vertex just beyond the word the parser has most recently scanned. An edge is always stored at the vertex representing its right end. At the time it is stored this is always the Current Vertex. Newly completed constituents always end at that Vertex too.
wren a new constituent is built that sp;~ns the whole string, it is put into a list of interpretations, not on the chart. Only incomplete constituents are stored on the chart.
2.3. Top-down Filtering
To incorporate top-down information, the vertices also need to keep track 6f which symbols could come next, based on the edges stored at a given vertex, and the precomputed information about reachabil ity. Given a constituent going from Vi to V ·, and a list of edges stored at V ·, we can restdct the construction of constituenEs and edges even further. Now an edge is only proposed for a rule, if the root of the rule is reachable fran a category which is first on the completion of one of the edges at Vi. Similarly, a constituent starting at Vi is only built by some unit production if the root of the rule is reachable fran a category which is first on the completion of one of the edges at Vi.

At least same of the time, [men] can build to an NP. However in the example in (3), a constituent starting fran Vl may only be built if it will build to an N, or to something which is reachable fran N. Since an NP is presllllaoly not reachable from N, the NP [men] does not get built.
So far, the procedure outlined fits within the schenata that (Kay, 1980) describes. The next modification goes a little further. In addition to the machinery already described, two one-word look-ahead buffers are added. Now the word to the right of the Current Vertex is in the ~'1-buffer (Word-buffer). The other buffer, the M-buffer (Meaning-buffer) is initially empty for each word, and is a receptacle for information about a word's syntactic category or categories.
Now before the parser decides that it can build a new edge or extend an old one, it checks the completion against the word in the w-buffer. If the word is not reachable from what would be the first element of the new completion, the edge does not get constructed. If the word in the buffer is syntactically ~iguous, i.e. has more than one possible syntactic category, then the category which allows the edge to be constructed is saved in the M-buff er. So by the time the p3.rser is ready to advance, it has already narrowed down the lexical ambiguity somewhat. If there is still more than one possible category for the word by the time the parser gets to it, the new word in the look-ahead buffer could conceivably filter out all the edges which would be proposed for one or more of the urrlesi rable readings. If such is not the case, then the p;~rser must resort to same sort of contextual filtering as alluded to above.
The fact that the tarser is breadth-first allows the parser to dispense with inactive edges. This turns out to have an interesting effect. Although the parser may build constituents that it cannot use in the final tarse tree, it does not keep than around. For instance in the sentence, "Bill likes the wanan who jogs," the tarser will build up the VP !likes the wananl and then ccrnbine it with [Bill] to form a sentence. If there are no rules in the grammar of the form, IX--> S Yl, though, nothing more happens to the S. It simply never gets saved.
3. Conclusion
The fact that regular languages may be tarsed in linear time is due to the fact that for every nondeterministic finite state machine, there is an equivalent deterministic one. Or put in terms of grammars, for every regular language there is an unambiguous linear grammar that generates it. The problem with natural language, though, is that it has ambiguities. One may point out the need, in any mcxlel, to resort to contextual information to choose between different alternatives when ambiguity is encountered. To do this however, requires that the different choices exist in the model, i.e., in terms of finite state machines it requires that the states of the machine have not been expaooed to get rid of the noooeterminism. In terms of grammars again, even though there exists a linear grammar for any regular language, it is certainly not true that all grammars of regular languages are linear. Hence, the claim that natural language is regular cannot really be said to account for the fact that people seem to be able to parse natural languages in linear time. One needs to make the stronger claim that linear grammars can adequatly describe natural language. This precludes the existence of any ambiguity at all, and seems to be excessive considering the facts.
As an alternative to the deterministic parsers that have been proposed, we have suggested a breadth-first tarser for context-free languages. It only pursues alternatives which are consistent with information about what has cane before, and with what the next word is. If the grammar taken as a whole specifies that there is only one alternative at sane point, even though locally there might be more than one, then the tarser only pursues that one alternative. If there is global ambiguity, the tarser allows for it. To account for the observation that ambiguity is usually not perceived, the tarser only needs to have access to the same · sort of contextual information that depth-first tarsers need.
4. REFERENCES
- Ill Kimball, John (1973} Seven Principles of Sur face Structure Parsing in Natural Language. Cognition, Vol 2, pp. 15-47.
- 121 Frazier, Lyn and Janet Fodor (1979} The Sau sage ~lachine: A New '1\vo-Stage Parsing Model. Cognition 6, pp.291-325.
- 131 Church, Kenneth (1980} On Memory Limitations in Natural Language Processing. MIT Laboratory for Canp.Iter science: Cambndge, ~s.
- 141 Ford, Marilyn, Joan Bresnan, and Rooald Kaplan (1981} A Canpetence-Based Theory of Syntactic Closure. Paper presented at the Symposium on Modelling Human Parsing Strategies. Center for Cognitive Science, University of Texas, Austin.
- 151 Crain, Steven and Mark Steedman (1981} The Use of Context by the Psychological Parser. Paper presented at the Symposium on Mooel ling Human Parsing Strategies. Center for Cognitive Science, University of Texas, Austin.
- Earley, Jay (1970} An Efficient Context-Free Parsing Algorithn. C<lllllunications of the ACM, Vol 13, No 2.
- 171 Pratt, Vaughn (1975} Lingol-A progress report. IJCAI 4.
- Chester, Daniel (1900} A Parsing Algorithm that Extends Phrases. American Journal of Corrr putational Linguistics, Vol 6, No 2.
- 191 Nartin, W.A., Church, K., and Ranesh Patil (1981} Preliminary Analysis of a Breadth-First Parsing Algorithm: Theoretical arrl Experiin7n tal Results. Paper presented at the Symposwm on Modelling Human Parsing Strategies. Center for Cognitive Science, University of Texas, Austin.
- [101 Kay, Martin (1900} Algorithm Schemata and Data Structures in Syntactic Processing. To appear in The Proceedings of the Nobel ~ sium on Text Processing, Gothenburg, Sweden.
- 1111 Winograd, Terry (1983} Language as a ccx;mi tive Process, Vol 1. Addison-wesley: Readwg, Mass.
@inproceedings{ijcai1983p168,
title = {A Breadth-First Parsing Model},
author = {Bear, John},
booktitle = {Proceedings of the Eighth International Joint Conference on
Artificial Intelligence, {IJCAI-83}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Alan Bundy},
pages = {696--697},
year = {1983},
note = {Natural Language},
url = {https://ijcai.org/proceedings/1983/168},
}
TY - CPAPER TI - A Breadth-First Parsing Model AU - Bear, John T2 - Proceedings of the Eighth International Joint Conference on Artificial Intelligence, IJCAI-83 PB - International Joint Conferences on Artificial Intelligence PY - 1983 SP - 696 EP - 697 UR - https://ijcai.org/proceedings/1983/168 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: