Generating a recognizer for a BNF grammar

This paper describes an algorithm which takes the BNF definition of the grammar of a language and constructs a set of productions for recognizing sentences of the language. These productions, as introduced by Floyd [ 4] and modified by Evans [ 3] , constitute a language in which may be written a one-pass, one-push-down-8tack recognizer, which involves no closed subroutines. Thus it goes directly from the basic definition of the grammar of a programming language to an efficient parser for the language which could easily be incorporated into a compiler. Production Language*. The production language consists of a set of produc-tions of the form LO a b c I- * G I *G1 Let us assume we are parsing a sentence by productions. Each time we scan a character, it is placed at the top of a push down stack known as the syntax stack. Then we sequence through the productions, comparing the top few characters in the syntax stack to each production. The first bar in the production represents th