A Syntax-Analysis Procedure for Unambiguous Context-Free Grammars

Abstract

A syntax-analysis Mgorithm is presented for a language generated by an unambiguous context-free grammar in a number of elementary operations proportional to n = log n, where n is the length of a given string, using a random access memory. The amount of memory required for the algorithm is proportional to n 2 log n. The proposed algorithm is a modified version of Cocke's algorithm and utilizes a eertair, property of unambiguous normal grammars.