If a context-free language enjoys the local parsability property then, no matter how the source string is segmented, each segment can be parsed in- dependently, and an efficient parallel parsing algorithm becomes possible. The new class of locally chain-parsable languages (LCPL), included in deterministic context-free languages, is here defined by means of the chain-driven automa- ton and characterized by decidable properties of grammar derivations. Such au- tomaton decides to reduce or not a factor in a way purely driven by the terminal characters, thus extending the well-known concept of Input-Driven (ID) (visibly) pushdown machines. LCPL extend and improve the practically relevant operator- precedence languages (Floyd), which are known to strictly include the ID lan- guages, and for which a parallel-parser generator exists. Consistently with the classical results for ID, chain-compatible LCPL are closed under reversal and Boolean operations, and language inclusion is decidable.
Locally chain-parsable languages / S. Crespi Reghizzi, V. Lonati, D. Mandrioli, M. Pradella (LECTURE NOTES IN COMPUTER SCIENCE). - In: Mathematical Foundations of Computer Science 2015 / [a cura di] G.F. Italiano, G. Pighizzini, D.T. Sannella. - [s.l] : Springer, 2015. - ISBN 978-3-662-48056-4. - pp. 154-166 (( Intervento presentato al 40. convegno MFCS tenutosi a Milano nel 2015 [10.1007/978-3-662-48057-1_12].
Locally chain-parsable languages
V. LonatiSecondo
;
2015
Abstract
If a context-free language enjoys the local parsability property then, no matter how the source string is segmented, each segment can be parsed in- dependently, and an efficient parallel parsing algorithm becomes possible. The new class of locally chain-parsable languages (LCPL), included in deterministic context-free languages, is here defined by means of the chain-driven automa- ton and characterized by decidable properties of grammar derivations. Such au- tomaton decides to reduce or not a factor in a way purely driven by the terminal characters, thus extending the well-known concept of Input-Driven (ID) (visibly) pushdown machines. LCPL extend and improve the practically relevant operator- precedence languages (Floyd), which are known to strictly include the ID lan- guages, and for which a parallel-parser generator exists. Consistently with the classical results for ID, chain-compatible LCPL are closed under reversal and Boolean operations, and language inclusion is decidable.File | Dimensione | Formato | |
---|---|---|---|
chp%3A10.1007%2F978-3-662-48057-1_12.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
234.37 kB
Formato
Adobe PDF
|
234.37 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.