Recent literature extended the analysis of ω-languages from the regular ones to various classes of languages with “visible syntax structure”, such as visibly pushdown languages (VPLs). Operator precedence languages (OPLs), instead, were originally defined to support deterministic parsing and exhibit interesting relations with these classes of languages: OPLs strictly include VPLs, enjoy all relevant closure properties and have been characterized by a suitable automata family and a logic notation. We introduce here operator precedence ω-languages (ωOPLs), investigating various acceptance criteria and their closure properties. Whereas some properties are natural extensions of those holding for regular languages, others require novel investigation techniques. Application-oriented examples show the gain in expressiveness and verifiability offered by ωOPLs w.r.t. smaller classes.
Operator precedence omega-languages / F. Panella, M. Pradella, V. Lonati, D. Mandrioli - In: Developments in language theory : 17th international conference, DLT 2013, Marne-la-Vallée, France, june 18-21, 2013 : proceedings / [a cura di] M.-P. Béal, O. Carton. - Berlin : Springer, 2013. - ISBN 9783642387708. - pp. 396-408 (( Intervento presentato al 17. convegno International Conference on Developments in Language Theory tenutosi a Marne-la-Vallée, France nel 2013 [10.1007/978-3-642-38771-5_35].
Operator precedence omega-languages
V. Lonati;
2013
Abstract
Recent literature extended the analysis of ω-languages from the regular ones to various classes of languages with “visible syntax structure”, such as visibly pushdown languages (VPLs). Operator precedence languages (OPLs), instead, were originally defined to support deterministic parsing and exhibit interesting relations with these classes of languages: OPLs strictly include VPLs, enjoy all relevant closure properties and have been characterized by a suitable automata family and a logic notation. We introduce here operator precedence ω-languages (ωOPLs), investigating various acceptance criteria and their closure properties. Whereas some properties are natural extensions of those holding for regular languages, others require novel investigation techniques. Application-oriented examples show the gain in expressiveness and verifiability offered by ωOPLs w.r.t. smaller classes.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
