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

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%.
Foundamentals of Computation Theory 1991 - n. 529
3540544585
INF; formal languages; queue grammars; queue automata; breadth-depth grammars; parsing; LL(1) analysis
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11311/569751
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact