Speculative data-parallel algorithms for language recognition have been widely experimented for various types of finitestate automata (FA), deterministic (DFA) and nondeterministic (NFA), often derived fromregular expressions (RE). Such an algorithm cuts the input string into chunks, independently recognizes each chunk in parallel by means of identical FAs, and at last joins the chunk results and checks the overall consistency. In chunk recognition, it is necessary to speculatively start the FAs in any state, thus causing an overhead that reduces the speedup over a serial algorithm. The existing data-parallel DFA-based recognizers suffer from an excessive number of starting states, and the NFA-based ones suffer from the number of nondeterministic transitions.

Abstract We extend the notion of the Dyck language from words to two-dimensional arrays of symbols, i.e., pictures, using the row-column combination (also known as the crossword) of two Dyck languages over the same alphabet. In a Dyck crossword picture, each column and each row must be a word from the respective Dyck language. The pairing of open and closed parentheses in a Dyck word can be represented by edges connecting corresponding cells in the same row or column. This defines a matching graph, which serves as the two-dimensional analogue of the syntactic tree of a Dyck word. A matching graph is partitioned into simple circuits of unbounded length (always a multiple of four), whose labels form a regular language. These circuits exhibit a wide variety of forms and labelings, which we illustrate and partially classify. With a two-letter alphabet, a Dyck crossword is necessarily empty. The minimal non-trivial case, requiring an alphabet of size four, already generates all possible forms of matching graphs and is the primary focus of our study. We prove that the only picture with a single matching circuit (i.e., a Hamiltonian cycle) has size 2 by 2. Two key properties of Dyck words–cancellation and well-nesting–can be generalized to two dimensions, leading to two alternative definitions of 2D Dyck languages: neutralizable and well-nested. These languages are special cases of Dyck crossword pictures called quaternate, where all circuits have length 4 (i.e., are rectangles). This results in a strict language inclusion hierarchy: well-nested $$\subset $$ ⊂ neutralizable $$\subset $$ ⊂ quaternate $$\subset $$ ⊂ Dyck crosswords. When the alphabet size exceeds four, not all combinations of row and column Dyck languages yield non-empty crosswords. To identify productive combinations, we introduce an alphabetic graph, where nodes represent alphabet symbols and edges represent their couplings. A matching circuit corresponds to the unrolling of an alphabetic graph circuit. Finally, we prove that Dyck crosswords are not tiling-recognizable, as expected for a definition extending Dyck word languages to pictures.

The row-column combination RCC maps two (word) languages over the same alphabet onto the set of rectangular arrays, i.e., pictures, such that each row/column is a word of the first/second language. The resulting array is thus a crossword of the component words. Depending on the family of the components, different picture (2D) language families are obtained: e.g., the well-known tiling-system recognizable languages are the alphabetic projection of the crossword of local (regular) languages. We investigate the effect of the RCC operation especially when the components are context-free, also with application of an alphabetic projection. The resulting 2D families are compared with others defined in the past. The classical characterization of context-free languages, known as Chomsky-Schützenberger theorem, is extended to the crosswords in this way: the projection of a context-free crossword is equivalent to the projection of the intersection of a 2D Dyck language and the crossword of strictly locally testable language. The definition of 2D Dyck language relies on a new more flexible so-called Cartesian RCC operation on Dyck languages. The proof involves the version of the Chomsky-Schützenberger theorem that is non-erasing and uses a grammar-independent alphabet.

A classic result in formal language theory is the equivalence among non-counting, or aperiodic, regular languages, and languages defined through star-free regular expressions, or first-order logic. Past attempts to extend this result beyond the realm of regular languages have met with difficulties: for instance it is known that star-free tree languages may violate the non-counting property and there are aperiodic tree languages that cannot be defined through first-order logic. We extend such classic equivalence results to a significant family of deterministic context-free languages, the operator-precedence languages (OPL), which strictly includes the widely investigated visibly pushdown, alias input-driven, family and other structured context-free languages. The OP model originated in the '60s for defining programming languages and is still used by high performance compilers; its rich algebraic properties have been investigated initially in connection with grammar learning and recently completed with further closure properties and with monadic second order logic definition. We introduce an extension of regular expressions, the OP-expressions (OPE) which define the OPLs and, under the star-free hypothesis, define first-order definable and non-counting OPLs. Then, we prove, through a fairly articulated grammar transformation, that aperiodic OPLs are first-order definable. Thus, the classic equivalence of star-freeness, aperiodicity, and first-order definability is established for the large and powerful class of OPLs. We argue that the same approach can be exploited to obtain analogous results for visibly pushdown languages too.

Optimizing programs to exploit the underlying hardware architecture is an important task. Much research has been done on enabling compilers to find the best set of code optimizations that can build the fastest and less resource-hungry executable for a given program. A common approach is iterative compilation, sometimes enriched by machine learning techniques. This provides good results, but requires extremely long compilation times and an initial training phase lasting even for days or weeks. We present long-term learning, a new algorithm that allows the compiler user to improve the performance of compiled programs with reduced compilation times with respect to iterative compilation, and without an initial training phase. Our algorithm does not just build good programs: it acquires knowledge every time a program is compiled and it uses such knowledge to learn compiler heuristics, without the need for an expert to manually define them. The heuristics are evolved during every compilation, by evaluating their effect on the generated programs. We present implementations of long-term learning on top of two different compilers, and experimental data gathered on multiple hardware configurations showing its effectiveness.

Getting insight into different aspects of source code artifacts is increasingly important – yet there is little empirical research using large bodies of source code, and subsequently there are not much statistically significant evidence of common patterns and facts of how programmers write source code. We pose 32 research questions, explain rationale behind them, and obtain facts from 2,080 randomly chosen Java applications from Sourceforge. Among these facts we find that most methods have one or zero arguments or they do not return any values, few methods are overridden, most inheritance hierarchies have the depth of one, close to 50 % of classes are not explicitly inherited from any classes, and the number of methods is strongly correlated with the number of fields in a class. Categories and Subject Descriptors

Abstract ILDJIT, a new‐generation dynamic compiler and virtual machine designed to support parallel compilation, is introduced here. Our dynamic compiler targets the increasingly popular ECMA‐335 specification. The goal of this project is twofold: on one hand, it aims at exploiting the parallelism exposed by multi‐core architectures to hide the dynamic compilation latencies by pipelining compilation and execution tasks; on the other hand, it provides a flexible, modular and adaptive framework for dynamic code optimization. The ILDJIT organization and the compiler design choices are presented and discussed highlighting how adaptability and extensibility can be achieved. Thanks to the compilation latency masking effect of the pipeline organization, our dynamic compiler is able to mask most of the compilation delay, when the underlying hardware exposes sufficient parallelism. Even when running on a single core, the ILDJIT adaptive optimization framework manages to speedup the computation with respect to other open‐source implementations of ECMA‐335. Copyright © 2010 John Wiley & Sons, Ltd.

Embedded media applications have to satisfy real-time, low power consumption and silicon area constraints. These applications spend most of the execution time in the iteration of a few kernels; such kernels are typically made of independent operations, which can be executed in parallel. Clustered architectures are a solution designed to exploit the high instruction level parallelism (ILP) of the media kernels, to keep a good level of scalability and to match the strict constraints of the embedded domains. Within this category, architectures with reconfigurable connections between clusters are of particular interest. The enhanced flexibility allows them to handle several different data-paths effectively, hence multiple applications; this is a key economic factor in the semiconductor world, in which the cost of the masks significantly increases at every technological advance. This papers describes hierarchical cluster assignment (HCA), a compilation technique that deals with the problem of mapping the computation of multimedia kernels onto the clusters of the target machine. HCA exploits the hierarchical structure of the clusters of the target architectures; it works by decomposing the problem of cluster assignment into a sequence of simpler sub-problems, each of them involving a subset of the kernel instructions and a subset of the machine clusters. A prototype of this methodology has been implemented in a flexible framework and tested on machine models based on the DSPfabric architecture.

The article addresses the formal specification, design and implementation of the behavioral component of graphical user interfaces. The complex sequences of visual events and actions that constitute dialogs are specified by means of modular, communicating grammars called VEG (Visual Event Grammars), which extend traditional BNF grammars to make them more convenient to model dialogs.A VEG specification is independent of the actual layout of the GUI, but it can easily be integrated with various layout design toolkits. Moreover, a VEG specification may be verified with the model checker SPIN, in order to test consistency and correctness, to detect deadlocks and unreachable states, and also to generate test cases for validation purposes.Efficient code is automatically generated by the VEG toolkit, based on compiler technology. Realistic applications have been specified, verified and implemented, like a Notepad-style editor, a graph construction library and a large real application to medical software. It is also argued that VEG can be used to specify and test voice interfaces and multimodal dialogs. The major contribution of our work is blending together a set of features coming from GUI design, compilers, software engineering and formal verification. Even though we do not claim novelty in each of the techniques adopted for VEG, they have been united into a toolkit supporting all GUI design phases, that is, specification, design, verification and validation, linking to applications and coding.

The research described concerns the partitioning of large control applications for a multi-computer system in order to meet plant localization requirements and to exploit parallelism. The considered applications have hierarchical structure and are composed by a network of automata. Our application domain is the automation of power stations and electricity distribution. Because of strong EM noise in such environments, the software architecture is organized to be tolerant to transient faults, which could affect the stability of the control system. The hierarchical structure provides a decompositional approach to the design of complex applications. The context for this work is the ASFA platform, originally designed by the Italian board of electricity. The main result is a new partitioning algorithm for hierarchical automata networks, that splits the application into sub-networks which are deadlock-free, compliant with localization constraints, and as parallelizable as possible. The algorithm is also able to satisfy mutual exclusion constraints and to take into account computation/communication weights to achieve balancing of partitions.

The paper addresses the formal specification, design and implementation of the behavioral component of graphical user interfaces. Dialogs are specified by means of modular, communicating grammars called VEG (Visual Event Grammars), which extend traditional BNF grammars to make the modeling of dialogs more convenient. A VEG specification is independent of the actual layout of the GUI, but it can be easily integrated with various layout design toolkits. The specification may be verified with the model checker Spin, in order to test consistency and correctness, to detect deadlocks and unreachable states, and also to generate test cases for validation purposes. Efficient code is automatically generated by the VEG toolkit, based on compiler technology. Realistic applications have been specified, verified and implemented, like a Notepad-style editor, a graph construction library and a large real application to medical software. The complete VEG toolkit is going to be available soon as free software.

Logres is a new-generation database system integrating\nfeatures from deductive and object-oriented\ndatabases [1, 2, 3, 4, 5]. The data model of Logres supports\nstructural and semantic complexity through a rich\ncollection of concepts from object-oriented models. The\nrule language allows for the manipulation of complex objects,\nthe generation of new objects, and the definition of\npassive and active constraints. The application of set of\nrules to database states is controlled by means of qualifiers,\nwhich dictate the side effects of rules; qualifiers\nare the unique procedural feature of Logres, otherwise\na fully declarative language.

The authors present an environment and a methodology for the design and rapid prototyping of data-intensive software applications, i.e., applications which perform substantial retrieval and update activity on persistent data. In the approach, the application is formally specified using Logres, a database language which combines object-oriented data modeling and rule-based programming. These specifications are translated into Algres, an extended relational algebra, thus yielding a rapid executable prototype. Algres programs embedded into a conventional programming language interface may be converted to conventional programs operating on a commercial relational system. This methodology helps automate the conversion from declarative requirements to imperative code, performing several tasks fully automatically and reducing the probability of human errors, while integrity constraints and application specifications are expressed in a declarative language, at a very high level of abstraction.>

LOGRES is a new project for the development of extended database systems which is based on the integration of the object-oriented data modelling paradigm and of the rule-based approach for the specification of queries and updates.

A method for designing and prototyping program construction systems using relational databases is presented. Relations are the only data structures used inside the systems and for interfaces; programs extensively use relational languages, in particular relational algebra. Two large projects are described. The Ada Relational Translator (ART) is an experimental compiler-interpreter for Ada in which all subsystems, including the parser, semantic analyzer, interpreter, kernel, and debugger, use relations as their only data structure; the relational approach has been pushed to the utmost to achieve fast prototyping in a student environment. Multi-Micro Line (MML) is a tool set for constructing programs for multimicroprocessors' targets, in which relations are used for allocation and configuration control. Both experiences validate the approach for managing teamwork in evolving projects, identify areas where this approach is appropriate, and raise critical issues.>

Chains (or cascade composition) of push-down transducers are introduced as a model of multi-pass compilers. We focus on deterministic chains, since nondeterministic transducer chains of length two define the recursively enumerable sets. Deterministic chains recognize in linear time a superset of context-free deterministic languages. This family is $\mathcal{CH}$ closed under Boolean operations, disjoint shuffle,and reverse deterministic pushdown translation, but not under homomorphism. Equivalent definitions of the family in terms of composition of syntax-directed translation schemes and control languages are considered. The family is a strict hierarchy ordered by the length of the chain. The complexity of $\mathcal{CH}$ is obviously linear, but not all linear-time parsable languages are in $\mathcal{CH}$. On the other hand it strictly includes the Boolean closure of deterministic languages. Finally $\mathcal{CH}$ is not comparable with another classical Boolean algebra of formal languages, namely real-time languages.

The notion of noncounting language, initially introduced for regular languages recognized by counter-free finite machines, and recently extended to parenthesized context-free languages, is here further studied for general (i.e., nonparenthesized) context-free languages. While weakly equivalent context-free grammars do not, in general, fall in the same class with respect to the noncounting property, it is shown by a complex proof that weakly equivalent operator precedence grammars are all counting or all noncounting (a property which distinguishes the operator precedence languages from classical deterministically parsable families).

Abstract A system for assisting in the testing phase of compilers is described. The definition of the language to be compiled drives an automatic sentence generator. The language is described by an extended BNF grammar which can be augmented by actions to ensure contextual congruence, e.g. between definition and use of identifiers. For deep control of the structure of the produced sample the grammar can be described by step‐wise refinements: the generator is iteratively applied to each level of refinement, producing at last compilable, complete programs. The implementation is described and some experimental results are reported concerning PLZ, MINIPL and some other languages.

The class of noncountlng (aperiodic) context-free parenthesis languages is introduced here and is found to extend the classical theory of noncountmg regular languages It Is proved that it is possible to decide whether or not a context-free parenthesis grammar Is noncountmg The class of k-distract-homogeneous grammars (previously introduced in connection with studies on grammatical mference or language acqmsitmn) is rigorously defined and proved to be noncountlng It as argued that the noncountmg model fits the syntactic aspects of natural or araficial languages more closely than the context-free model