The synthesis of finite state syntax directed top-down and bottom-up transducers

The notion of context-free LR[K) and LL(K) grammars and of the related bottom-up and top-down syntax-directed parsings are well known [1,2,3]. In this report we present a number of synthesis algorithms which take a non-self-embedding, sequential, context-free grammar and produce the finite state transducer which either top-down or bottom-up parses sentences in the language induced by the grammar iff this grammar is finite state LL[K) respectively LR(K). This later property is decidable.