Operator precedence and the visibly pushdown property

详细信息    查看全文

• 作者：Stefano Crespi Reghizzi ; Dino M ; rioli
• 关键词：Pushdown automata ; Closure under language operations ; Operator precedence grammars ; Parenthesis languages ; XML languages ; Balanced languages ; Height deterministic languages
• 刊名：Journal of Computer and System Sciences
• 出版年：2012
• 出版时间：November, 2012
• 年：2012
• 卷：78
• 期：6
• 页码：1837-1867
• 全文大小：827 K

文摘

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.