If 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 well-known 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.
Toward a theory of input-driven locally parsable languages
CRESPI REGHIZZI, STEFANO;MANDRIOLI, DINO;PRADELLA, MATTEO
2017-01-01
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 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 well-known 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.File | Dimensione | Formato | |
---|---|---|---|
accauno-journal.pdf
accesso aperto
:
Pre-Print (o Pre-Refereeing)
Dimensione
245.16 kB
Formato
Adobe PDF
|
245.16 kB | Adobe PDF | Visualizza/Apri |
1-s2.0-S0304397516301165-main-published.pdf
Accesso riservato
:
Publisher’s version
Dimensione
554.02 kB
Formato
Adobe PDF
|
554.02 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.