Path economization in exhaustive left-to-right syntactic analysis
Abstract
In exhaustive left-to-right syntactic analysis using the predictive approach, each path of syntactic connection which originates at the beginning of a sentence must be followed until it is clear whether or not it will lead to the production of a well-formed analysis. The original scheme of following each path until it terminates either in an analysis or in a grammatical inconsistency has been considerably improved through the. incorporation of two path-testing techniques. Using the first technique, the program abandons a path as unproductive whenever a situation is detected where the prediction pool contains more predictions of a given type than can possibly be fulfilled by the remaining words in the sentence. Employment of the second technique, which is based on periodic comparison of the current prediction pool with pools formed on earlier productive paths, eliminates repeated analysis of identical right-hand segments which belong to distinct paths. Taken together, the two path-testing procedures frequently enable the program to terminate the processing of a path well before its end has been reached. For most sentences, this means a considerable reduction in the total path length traversed, accompanied by a corresponding increase in the speed of analysis. Comparison of runs performed using both versions of the program indicates that employment of the new techniques reduces the average running time per sentence to less than one-fifth of its former value.- Anthology ID:
- 1963.earlymt-1.29
- Volume:
- Proceedings of the Annual meeting of the Association for Machine Translation and Computational Linguistics
- Month:
- 25-26 August
- Year:
- 1963
- Address:
- Denver, Colorado
- Venue:
- EarlyMT
- SIG:
- Publisher:
- Note:
- Pages:
- Language:
- URL:
- https://aclanthology.org/1963.earlymt-1.29
- DOI:
- Cite (ACL):
- Warren J. Plath. 1963. Path economization in exhaustive left-to-right syntactic analysis. In Proceedings of the Annual meeting of the Association for Machine Translation and Computational Linguistics, Denver, Colorado.
- Cite (Informal):
- Path economization in exhaustive left-to-right syntactic analysis (Plath, EarlyMT 1963)