Breadth-depth grammars  extend the context-free ones by allowing breadth-first derivations. Breadth-depth languages include the context-free ones and are recognized by monostatic (one-state) automata having a double-ended queue (dequeue) as their memory. Examples of breadth-depth grammars for compilation and scheduling problems are included to argue for their applicability. We define deterministic monostatic dequeue automata and investigate their languages. Main results are their incomparability with context-free deterministic languages and linear-time recognizability. We introduce the LL(1) grammars, as an extension of the classical top-down deterministically parsable context-free grammars, and we present a recursive descent parsing algorithm using a FIFO queue. Work supported by ESPRIT Basic Research Actions ASMICS and by Ministero dell'Università e della Ricerca Scientifica e Tecnologica MURST 60%.
File in questo prodotto:
Non ci sono file associati a questo prodotto.