Syntax-checking and parsing of context-free languages by pushdown-store automata
Victor B. Schneider · 1967
By way of two heuristic examples, this paper demonstrates an algorithm that constructs computer-realizable machines for syntax checking and parsing of computer programs constructed from context-free grammars. The algorithm followed constructs a pushdown-store, one-way automaton that corresponds to the context-free version of the grammar being considered. This automaton has the property of accepting a string of symbols on its input tape if and only if that string belongs to the language of its grammar. In addition, it signals the source of error in an unacceptable string on its input tape as a result of the correspondence between states of the automaton and rules of the grammar.