Consiglio Nazionale delle Ricerche

Tipo di prodottoArticolo in rivista
TitoloToward a theory of input-driven locally parsable languages
Anno di pubblicazione2017
FormatoCartaceo
Autore/iStefano Crespi-Reghizzi and Violetta Lonati and Dino Mandrioli and Matteo Pradella
Affiliazioni autoriDEIB, Politecnico di Milano, DI, Università degli Studi di Milano, IEIIT, CNR
Autori CNR e affiliazioni
  • STEFANO CRESPI REGHIZZI
  • MATTEO PRADELLA
Lingua/e
  • inglese
AbstractIf a context-free language enjoys the local parsability property then, no matter how the source string is segmented, each segment can be parsed independently, and an efficient parallel parsing algorithm becomes possible. The new class of locally chain parsable languages (LCPLs), included in the deterministic context-free language family, is here defined by means of the chain-driven automaton and characterized by decidable properties of grammar derivations. Such automaton decides whether to reduce or not a substring in a way purely driven by the terminal characters, thus extending the wellknown concept of input-driven (ID) alias visibly pushdown machines. The LCPL family extends and improves the practically relevant Floyd's operator-precedence (OP) languages which are known to strictly include the ID languages, and for which a parallel parser generator exists.
Lingua abstractinglese
Altro abstract-
Lingua altro abstract-
Pagine da105
Pagine a121
Pagine totali-
RivistaTheoretical computer science
Attiva dal 1975
Editore: Elsevier - Lausanne ;
Paese di pubblicazione: Paesi Bassi
Lingua: inglese
ISSN: 0304-3975
Titolo chiave: Theoretical computer science
Titolo abbreviato: Theor. comp. sci.
Numero volume della rivista658
Fascicolo della rivista-
DOI10.1016/j.tcs.2016.05.003
Verificato da refereeSì: Internazionale
Stato della pubblicazionePreprint
Indicizzazione (in banche dati controllate)
  • Scopus (Codice:2-s2.0-84966714079)
Parole chiaveOperator Precedence languages, Input-driven languages, Visibly Pushdown languages, Parallel Parsing
Link (URL, URI)https://doi.org/10.1016/j.tcs.2016.05.003
Titolo parallelo-
Data di accettazione-
Note/Altre informazioni-
Strutture CNR
  • IEIIT — Istituto di elettronica e di ingegneria dell'informazione e delle telecomunicazioni
Moduli CNR-
Progetti Europei-
Allegati
  • Toward a theory of input-driven locally parsable languages
    Descrizione: preprint dell'articolo