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