کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
429603 687607 2012 31 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Operator precedence and the visibly pushdown property
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Operator precedence and the visibly pushdown property
چکیده انگلیسی

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.


► Operator precedence languages (OPL) dominate visibly pushdown languages (VPL).
► VPL are OPL characterized by restricted precedence relations.
► OPL closed under boolean operations concatenation star and other operations.
► No larger deterministic language family is known with such properties.
► OPL enable model checking and foster parallel and incremental parsing.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 78, Issue 6, November 2012, Pages 1837–1867
نویسندگان
, ,