1,720,992 research outputs found
Classical and Incremental Attribute Evaluation by Means of Recursive Procedures
No full textAbstractThe class of absolutely noncircular (ANC) attribute grammars (AGs) has been heavily studied, mainly because simple and recursive evaluators can be automatically produced for such grammars. We give a characterization of ANC AGs that includes as special cases most of the already existing definitions of this class. Our goal is that of clarifying the relationships among these definitions and also among the evaluators corresponding to them.We show also that for a more restricted class of AGs (the doubly noncircular AGs) recursive incremental evaluators can be constructed in a way very similar to that used for the ANC AGs
Interpretation and Reduction of Attribute Grammars
Full text linkAn attribute grammar (AG) is in reduced form if in all its derivation trees every attribute contributes to the translation. We prove that, eventhough AG are generally not in reduced form, they can be reduced, i.e., put into reduced form, without modifying their translations. This is shown first for noncircular AG and then for arbitrary AG. In both cases the reduction consists of easy (almost syntactic) transformations which do not change the semantic domain of the AG. These easy transformations are formalized by introducing the notion of AG interpretation as an extension to AG of the concept of context-free grammar form. Finally we prove that any general algorithm for reducing even the simple class of L-AG needs exponential time (in the size of the input AG) infinitely often
Machines for Attribute Grammars
No full textTwo automata models are introduced that play, with respect to attribute grammars and attribute-evaluation for them, the same role as pushdown automata have with respect to context-free grammars and their parsing. It is shown, in fact, that these automata define the same class of string-to-value translations as attribute grammars. Their class of tree-to-value translations seems instead to be larger than that of attribute grammars and the difference is overcome by means of (a special type of) context-free grammar interpretations. An extended model of attribute grammar is presented that is as powerful as the automata with respect to tree-to-value translations
Complementation of abstract domains made easy
No full textIn standard abstract interpretation theory, the inverse of the reduced product of abstract domains was recently defined and called complementation. Given two domains C and D such that D abstracts C , the complement C ∼ D is the most abstract domain whose reduced product with D gives C back. We show that, when C is a continuous complete lattice, there is a particularly simple method for computing C ∼ D . Since most domains for abstract interpretation are (complete and) continuous, this method is widely applicable. In order to demonstrate its relevance, we apply this result and some of its consequences to Cousot and Cousot’s domain for integer interval analysis of imperative programs, and to several well- known domains for the static analysis of logic languages, viz., Pos, Def and Sharing. In particular, we decompose Sharing in three more abstract domains whose reduced product gives back Sharing, and such that each component corresponds to one of the three properties that coexist in the elements of Sharing: ground-dependency, pair-sharing (or equivalently variable independence) and set-sharing. Using our theory, we minimize each component of this decomposition obtaining in some case domains that are surprisingly simpler than the corresponding original components
Expressive Power of Definite Clauses for Verifying Authenticity
No full textThanks to the work of Bruno Blanchet definite clauses are
an established technique for verifying security properties
of communication protocols. We investigate the expressive
power of this approach with respect to verifying authenticity.
A translation from protocols into definite clauses is given,
and direct proofs for correctness and completeness of the
authenticity verification based on these clauses are shown.
These proofs are new, and in particular the completeness
result is surprising. These results, beside their intrinsic
value, shed light on some interesting issues about existing
proposals for exploiting definite clauses in protocols verification
- …
