In contrast to the usual depth-first derivations of context-free (CF) grammars, breadth-first derivations (also in combination with depth-first ones) yield a class of augmented context-free grammars (ACF) (also termed multi-breadth-depth grammars) endowed with greater generative capacity, yet manageable. The inadequacy of CF grammars to treat distant dependencies is overcome by the new model. ACF grammars can be classified with respect to their disposition, a concept related to the data structure needed to parse their strings. For such augmented CF grammars we consider the LL(k) condition, that ensures top-down deterministic parsing. We restate the condition as an adjacency problem and we prove that it is decidable for any disposition. The deterministic linear-time parser differs from a recursive descent parser by using instead of a LIFO stack a more general data structure, involving FIFO queues and LIFO stacks in accordance with the disposition. ACF grammars can be also viewed as a formalized version of ATN (Augmented Transition Networks).

Deterministic parsing for augmented context-free grammars

BREVEGLIERI, LUCA ODDONE;CHERUBINI, ALESSANDRA;CRESPI REGHIZZI, STEFANO
1995

Abstract

In contrast to the usual depth-first derivations of context-free (CF) grammars, breadth-first derivations (also in combination with depth-first ones) yield a class of augmented context-free grammars (ACF) (also termed multi-breadth-depth grammars) endowed with greater generative capacity, yet manageable. The inadequacy of CF grammars to treat distant dependencies is overcome by the new model. ACF grammars can be classified with respect to their disposition, a concept related to the data structure needed to parse their strings. For such augmented CF grammars we consider the LL(k) condition, that ensures top-down deterministic parsing. We restate the condition as an adjacency problem and we prove that it is decidable for any disposition. The deterministic linear-time parser differs from a recursive descent parser by using instead of a LIFO stack a more general data structure, involving FIFO queues and LIFO stacks in accordance with the disposition. ACF grammars can be also viewed as a formalized version of ATN (Augmented Transition Networks).
Lecture Notes in Computer Science: Mathematical Foundations of Computer Science Conference 1995 - n. 969
INF; formal languages; augmented context-free grammars; queue grammars; deterministic parsing; LL parsing
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/569777
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact