The concept of incremental parsing is briefly introduced. An algorithm which augments an LR parser with the capability of reanalyzing a limited part of a modified program is illustrated. The algorithm operates on a sequence of configurations representing the parse of the old input and finds the smallest part of the sequence which must be recomputed to obtain the parse of the new input. The implementation is discussed: a suitable data structure and a version of the algorithm which operates upon it are introduced; finally the problem of realizing efficient incremental parsers is faced, showing a modification to the basic algorithm which enable the reanalysis to be performed in linear time.

Incremental LR Parsers

CELENTANO, Augusto
1978-01-01

Abstract

The concept of incremental parsing is briefly introduced. An algorithm which augments an LR parser with the capability of reanalyzing a limited part of a modified program is illustrated. The algorithm operates on a sequence of configurations representing the parse of the old input and finds the smallest part of the sequence which must be recomputed to obtain the parse of the new input. The implementation is discussed: a suitable data structure and a version of the algorithm which operates upon it are introduced; finally the problem of realizing efficient incremental parsers is faced, showing a modification to the basic algorithm which enable the reanalysis to be performed in linear time.
1978
10
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in ARCA 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: https://hdl.handle.net/10278/35385
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact