Operator precedence and the visibly pushdown property |
| |
Authors: | Stefano Crespi Reghizzi Dino Mandrioli |
| |
Affiliation: | DEI – Politecnico di Milano, Piazza Leonardo da Vinci, 32, I-20133 Milano, Italy;Waseda University;Nanjing University of Posts and Telecommunications |
| |
Abstract: | Floyd?s operator precedence grammars and languages (FG, FL) are a classical subclass of deterministic context-free (DCF) grammars and languages. We prove that several recently introduced language families motivated by the needs of model checking and of specifying XML-like languages are proper subsets of FL. The main cases considered include visibly pushdown languages (VPL) and balanced languages (BALAN), which are characterized by restricted precedence relations. FL have all the closure properties available for regular languages and generally viewed as necessary for application to model checking: reversal, prefixing and suffixing, concatenation, Kleene star, and boolean operations. All but the last results are new, and some require complex proofs, due to the necessary changes of syntax structure. Thus FL are the largest known subfamily of DCF having the same closure properties as VPL. FG, unlike VPL grammars, which are intended for abstract syntax modelling, are structurally adequate to specify real programming languages. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|