A Global Parser for Context-Free Phrase Structure Grammars An algorithm for analyzing any context-free phrase structure grammar and for generating a program which can then parse any sentence in the language (or indicate that the given sentence is invalid) is described. The parser is of the "top-to-bottom" type and is recursive . A number of heuristic procedures whose purpose is to shorten the basic algorithm by quickly ascertaining that certain substrings of the input sentence cannot correspond to the target nonterminal symbols are included. Both the generating algorithm and the parser have been implemented in RCA SNOBOL and have been tested successfully on a number of artificial grammars and on a subset of ALGOL. A number of the routines for extracting data about a grammar, such as minimum lengths of N-derivable strings and possible prefixes, are given and may be of interest apart from their application in this particular context. CACM April, 1968 Unger, S. H. parser, syntax-directed compiler, context-free grammars, syntactic analysis, translators 3.42 4.12 5.24 CA680402 JB February 23, 1978 11:27 AM 1350 4 1768 1399 4 1768 1496 4 1768 1659 4 1768 1665 4 1768 1683 4 1768 1768 4 1768 1768 4 1768 1768 4 1768 1781 4 1768 1787 4 1768 1787 4 1768 1824 4 1768 1825 4 1768 1836 4 1768 1861 4 1768 1945 4 1768 1945 4 1768 2015 4 1768 2061 4 1768 2110 4 1768 2110 4 1768 2127 4 1768 2187 4 1768 2317 4 1768 2545 4 1768 2698 4 1768 2733 4 1768 3094 4 1768 1141 5 1768 1265 5 1768 1768 5 1768 1768 5 1768 1768 5 1768 1781 5 1768