Breadth-depth grammars [3] 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%.
Deterministic dequeue automata abd LL(1) parsing of breadth-depth grammars
BREVEGLIERI, LUCA ODDONE;CITRINI, CLAUDIO;CRESPI REGHIZZI, STEFANO
1991-01-01
Abstract
Breadth-depth grammars [3] 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%.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
