Summary In this paper, we describe our experience in grammar engineering to construct multiple parsers and front ends for the Python language. We present a metrics‐based study of the evolution of the Python grammars through the multiple versions of the language in an effort to distinguish and measure grammar evolution and to provide a basis of comparison with related research in grammar engineering. To conduct this research, we have built a toolkit, pygrat, which builds on tools developed in other research. We use pygrat to build a system that automates much of the process needed to translate the Python grammars from EBNF to a formalism acceptable to the bison parser generator. We exploit the suite of Python test cases, used by the Python developers, to validate our parser generation. Finally, we describe our use of the menhir parser generator to facilitate the parser and front‐end construction, eliminating some of the transformations and providing practical support for grammar modularisation.

Background: Python is one of the most popular modern programming languages. In 2008 its authors introduced a new version of the language, Python 3.0, that was not backward compatible with Python 2, initiating a transitional phase for Python software developers. Aims: The study described in this paper investigates the degree to which Python software developers are making the transition from Python 2 to Python 3. Method: We have developed a Python compliance analyser, PyComply, and have assembled a large corpus of Python applications. We use PyComply to measure and quantify the degree to which Python 3 features are being used, as well as the rate and context of their adoption. Results: In fact, Python software developers are not exploiting the new features and advantages of Python 3, but rather are choosing to retain backward compatibility with Python 2. Conclusions: Python developers are confining themselves to a language subset, governed by the diminishing intersection of Python 2, which is not under development, and Python 3, which is under development with new features being introduced as the language continues to evolve.

Developing and maintaining reliable object-oriented software requires a precise understanding of how individual classes must be used. Unfortunately, for many systems, especially those that are large, the available documentation is inadequate. Developers are left with incomplete information concerning the allowable set of call sequences that each class can accommodate. Techniques for reverse engineering this information and presenting it to developers in an intellectually scalable manner are critical. In this paper, we present four contributions to address this challenge. First, we describe a runtime trace collection system for large C++ applications. Second, we present a methodology for reverse engineering interface protocols from collected trace data. Third, we present a scalable, tunable algorithm for generating compact specifications of these protocols. Finally, we present a detailed case study involving the Mozilla Necko library. We consider popular applications in common use constructed using this library. The results are promising both in terms of the performance of the approach and the utility of the identified protocols.

In this paper, we address the problem of localizing faults by analyzing execution traces of successful and unsuccessful invocations of the application when run against a suite of tests. We present a new algorithm, based on a linear programming model, which is designed to be particularly effective for the case where multiple faults are present in the application under investigation. Through an extensive empirical study, we show that in the case of both single and multiple faults, our approach outperforms a host of prominent fault localization methods from the literature.

Many software development tools that assist with tasks such as testing and maintenance are specific to a particular development language and require a parser for that language. Because a grammar is required to develop a parser, construction of these software development tools is dependent upon the availability of a grammar for the development language. However, a grammar is not always available for a language and, in these cases, acquiring a grammar is the most difficult, costly, and time-consuming phase of tool construction. In this paper, we describe a methodology for grammar recovery from a hard-coded parser. Our methodology is comprised of manual instrumentation of the parser, a technique for automatic grammar recovery from parse trees, and a semi-automatic metrics-guided approach to refactoring an iterative grammar to obtain a recursive grammar. We present the results of a case study in which we recover and refactor a grammar from version 4.0.0 of the GNU C++ parser and then refactor the recovered grammar using our metrics-guided approach. Additionally, we present an evaluation of the recovered and refactored grammar by comparing it to the ISO C++98 grammar.

The object-oriented (OO) paradigm provides several benefits during analysis and design of large-scale software systems, but scores lower in terms of testability. The low testability score for OO software is due mainly to the composition of OO systems exhibiting the characteristics of abstraction, encapsulation, genericity, inheritance, polymorphism, concurrency and exception handling. To address the difficulty of testing the features of a class, a plethora of implementation-based testing techniques (IBTTs) have been developed. However, no one IBTT has emerged as the preferred technique to test the implementation of a class. In this paper we present a technique that automatically identify those IBTTs that are most suitable for testing a class based on the characteristics of that class. Our approach uses a taxonomy of OO classes that is used to succinctly abstract the characteristics of a class under test (CUT). We have implemented a tool that automates the process of mapping IBTTs to a class. In addition to identifying the IBTTs that would be best suited for testing a class, our tool provides feedback to the tester facilitating the identification of the characteristics of the class that are not suitably tested by any of the IBTTs in the list. We provide results of a study supporting the notion that using more than on IBTT during testing improves test coverage of a CUT.

Abstract In this paper, techniques are presented that exploit two design patterns, the Visitor pattern and the Decorator pattern, to validate invariants about the data attributes in a C++ class automatically. To investigate the pragmatics involved in using the two patterns, a study of an existing, well‐tested application, keystone, a parser and front‐end for the C++ language, is presented. Results from the study indicate that these two patterns provide flexibility in terms of the frequency and level of granularity of validation of the class invariants, which are expressed in the Object Constraint Language (OCL). The quantitative results measure the impact of these approaches and the additional faults uncovered through validation of the case study. Copyright © 2005 John Wiley & Sons, Ltd.

We present an approach for reverse engineering a program to capture design and implementation artifacts such as metrics and UML class or sequence diagrams. We also describe an implementation of our approach, libthorin. However, unlike previous reverse engineering tools, libthorin can be applied to a variety of programming languages including C, C++, Java, Fortran 90 and C#. Moreover, libthorin can provide both coarse-grained and fine-grained information about the program under development to enable re-engineering of information and high-level diagrams such as metrics and class diagrams, or low-level diagrams such as sequence diagrams, control flow graphs and other program representations and analysis tools for testing, debugging and profiling an application under development.

This paper presents a strategy for the visualization of dynamic object relationships in Java programs. The metaphor of a chemical molecule is used to aid comprehension, and to help in reducing the size of the object graph. Our strategy has been implemented by dynamically instrumenting Java bytecode to collect trace data, which is then analyzed and visualized in 3D using VRML. Quantitative and graphical results are presented, based on an analysis of programs in the SPEC JVM98 and JOlden benchmark suites.

Abstract One approach to measuring and managing the complexity of software, as it evolves over time, is to exploit software metrics. Metrics have been used to estimate the complexity of the maintenance effort, to facilitate change impact analysis, and as an indicator for automatic detection of a transformation that can improve the quality of a system. However, there has been little effort directed at applying software metrics to the maintenance of grammar‐based software applications, such as compilers, editors, program comprehension tools and embedded systems. In this paper, we adapt the software metrics that are commonly used to measure program complexity and apply them to the measurement of the complexity of grammar‐based software applications. Since the behaviour of a grammar‐based application is typically choreographed by the grammar rules, the measure of complexity that our metrics provide can guide maintainers in locating problematic areas in grammar‐based applications. Copyright © 2004 John Wiley & Sons, Ltd.

In this paper we present the design and implementation of a class ordering system that is driven by a parameterized cost model. The parameters to the model assign weights to the edge types that describe the relationships between the classes in the graphical representation of the program. The nodes in the graph are classes and the edges express relationships between the classes. Previous research has included three or four edge types in the graph. However, to accommodate the full complement of C++ language constructs, which include template classes and functions and nested classes, we extend the graph to include six edge types. The parameters to the cost model can be tuned to remove certain types of edges in an attempt to reduce the cost of the testing effort or to reduce the cost of breaking cycles in the graph. Our case study indicates that inclusion of inheritance edges in cycle breaking considerations may reduce the number of edge removals by a factor of two or more.

Abstract Software tools are fundamental to the comprehension, analysis, testing and debugging of application systems. A necessary first step in the development of many tools is the construction of a parser front‐end that can recognize the implementation language of the system under development. In this paper, we describe our use of token decoration to facilitate recognition of ambiguous language constructs. We apply our approach to the C++ language since its grammar is replete with ambiguous derivations such as the declaration/expression and template‐declaration/expression ambiguity. We describe our implementation of a parser front‐end for C++, keystone, and we describe our results in decorating tokens for our test suite including the examples from Clause Three of the C++ standard. We are currently exploiting the keystone front‐end to develop a taxonomy for implementation‐based class testing and to reverse‐engineer Unified Modeling Language (UML) class diagrams. Copyright © 2002 John Wiley & Sons, Ltd.

In this paper, we describe a non-invasive approach for validation of class invariants in C++ applications. Our approach is fully automated so that the user need only supply the class invariants for each class hierarchy to be checked and our validator constructs an InvariantVisitor, a variation of the Visitor Pattern, and an InvariantFacilitator. Instantiations of the InvariantVisitor and InvariantFacilitator classes encapsulate the invariants in C++ statements and facilitate the validation of the invariants. We describe both our approach and our results of validating invariants in keystone, a well tested parser front-end for C++.

The size and complexity of hardware and software systems continues to grow, making the introduction of subtle errors a more likely possibility. A major goal of software engineering is to enable developers to construct systems that operate reliably despite increased size and complexity. One approach to achieving this goal is through formal methods: mathematically based languages, techniques and tools for specifying and verifying complex software systems. The authors apply a theoretical tool (that is supported by many formal methods), the correctness preserving transformation (CPT), to a real software engineering problem: the need for optimization during the maintenance of code. We present four program transformations and a model that forms a framework for proof of correctness. We prove the transformations correct and then apply them to a cryptography application implemented in C++. Our experience shows that CPTs can facilitate generation of more efficient code while guaranteeing the preservation of original behavior.

A new approach is given for scheduling a sequential instruction stream for execution "in parallel" on asynchronous multiprocessors. The key idea in our approach is to exploit the fine grained parallelism present in the instruction stream. In this context, schedules are constructed by a careful balancing of execution and communication costs at the level of individual instructions, and their data dependencies. Three methods are used to evaluate our approach. First, several existing methods are extended to the fine grained situation. Our approach is then compared to these methods using both static schedule length analyses, and simulated executions of the scheduled code. In each instance, our method is found to provide significantly shorter schedules. Second, by varying parameters such as the speed of the instruction set, and the speed/parallelism in the interconnection structure, simulation techniques are used to examine the effects of various architectural considerations on the executions of the schedules. These results show that our approach provides significant speedups in a wide-range of situations. Third, schedules produced by our approach are executed on a two-processor Data General shared memory multiprocessor system. These experiments show that there is a strong correlation between our simulation results, and these actual executions, and thereby serve to validate the simulation studies. Together, our results establish that fine grained parallelism can be exploited in a substantial manner when scheduling a sequential instruction stream for execution "in parallel" on asynchronous multiprocessors.>

We present a new technique for constructing a program dependence graph that contains a program's control flow, along with the usual control and data dependence information. Our algorithm constructs a program dependence graph while the program is being parsed. For programs containing only structured transfers of control, our algorithm does not require information provided by the control flow graph or post dominator tree and therefore obviates the construction of these auxiliary graphs. For programs containing explicit transfers of control, our algorithm adjusts the partial control dependence subgraph, constructed during the parse, to incorporate exact control dependence information. There are several advantages to our approach. For many programs, our algorithm may result in substantial savings in time and memory since our construction of the program dependence graph does not require the auxiliary graph. Furthermore, since we incorporate control and data flow as well as exact control dependence information into the program dependence graph, our graph has a wide range of applicability. We have implemented our algorithm by incorporating it into the Free Software Foundation's GNU C compiler; currently we are performing experiments that compare our technique with the traditional approach.

Static instruction scheduling is an important optimization to exploit instruction level parallelism. If the scheduler has to consider resource constraints to prevent structural hazards, usually the processor timing is simulated by overlaying binary matrices representing the resource usage of instructions. This technique is rather time consuming. It is shown that the timing can be simulated by a deterministic finite automaton and the matrix operations for a simulation step are replaced by two table lookups. A prototype implementation shows that about an eighteenfold speedup of the simulation can be expected. This performance gain can be used either to speed up existing scheduling algorithms or to use more complex algorithms to improve scheduling results.>

Unified interprocedural graph (UIG) that extracts the important features of existing program representations and adds new information to provide an integrated representation for maintenance tasks is presented. Algorithms that were developed for previous representations are adapted to use the UIG by identifying the subset of nodes and edges in the UIG required for that computation. Newly developed algorithms can use the UIG since it contains data flow, control flow, data dependence, and control dependence information. The main benefits of this approach are the reduction in storage space since individual representations are not kept, the savings in maintenance time of a single representation over the individual representations, and the convenience of accessing a single program representation without increase in access time. A single program representation also assists in program understanding since relationships among program elements are incorporated into one graph.>

The authors present a novel system for re-engineering and retesting programs for execution in a shared memory multiprocessor environment. The system consists of two main components: a compiler that reengineers a sequential program for execution on shared memory multiprocessors, and a data-flow tester for the parallelized code. Several important enhancements to an existing parallelizing compiler have been made, including an efficient intermediate program representation on which data-flow analysis is performed. The compiler also inserts probes in a parallelized program to make it testable in its new environment. By inserting the probes in appropriate places, a compact execution trace is produced. The data-flow tester uses a new dynamic data-flow analysis algorithm to determine the test case coverage.>

A unified interprocedural program representation, the unified interprocedural graph (UIG) is presented; it combines the features of existing program representations to permit access to information for modifying, understanding, analyzing, testing and debugging. The algorithms developed for each of these independent graphs are adapted to use this unified representation by identifying the subset of nodes and edges required for that computation. The UIG can be incorporated into a maintenance environment and the associated algorithms used to build program maintenance tools. The authors present a brief overview of the graph representations on which the UIG is based and illustrate them with an example. The algorithms that use these graphs to gather the interprocedural information are described.>

Abstract Although the expressive power of retentive control is widely accepted, languages possessing such control forms are not always available. In this paper, we present an implementation technique to extend a recursive language to one containing simulation processes. In particular, we report on the design of a preprocessor that translates SimCal, a language that combines Pascal and the process abstraction of Simula, into Pascal. The translation is done automatically by the preprocessor without additional information from the user. The preprocessor has been implemented for a microcomputer using Turbo Pascal, which is also used as the target language. SimCal has been found to be useful for teaching simulation and for programming simulation applications.