Syntax-directed compression of program files

Parsing can be applied to compress source programs. A suitably encoded parse tree, together with the symbol table, constitutes a very compact representation of the program. The paper reports a Prolog implementation of the method, including automatic, syntax-directed, encoder and decoder generators. The test results show compression gains of 50–60 per cent.     

An application for plagiarized source code detection based on a parse tree kernel

Program plagiarism detection is a task of detecting plagiarized code pairs among a set of source codes. In this paper, we propose a code plagiarism detection system that uses a parse tree kernel. Our parse tree kernel calculates a similarity value between two source codes in terms of their parse tree similarity. Since parse trees contain the essential syntactic structure of source codes, the system effectively handles structural information. The contributions of this paper are two-fold. First, we propose a parse tree kernel that is optimized for program source code. The evaluation shows that our system based on this kernel outperforms well-known baseline systems. Second, we collected a large number of real-world Java source codes from a university programming class. This test set was manually analyzed and tagged by two independent human annotators to mark plagiarized codes. It can be used to evaluate the performance of various detection systems in real-world environments. The experiments with the test set show that the performance of our plagiarism detection system reaches to 93% level of human annotators.     

Abstract Implementation of Algebraic Specifications in a Temporal Logic Language

A formal technique for incorporating two specification paradigms is presented,in which an algebraic specification is implemented by a set of abstract procedures specified in pre and post-condition style.The link between the two level specifications is provided via a translation from terms of algebraic specifications into temporal logic formulae representing abstract programs.In terms of translation,a criterion for an abstract implementation satisfying its specification is given,which allows one to check the consistency between the two levels of specifications.The abstract implementations can be refined into executable code by refining each abstract procedure in it.It is proved that the satisfication relation between a specification and its implementations is preserved by such refinement steps.     

Automated analysis of the SCR-style requirements specifications

The SCR(Software Cost Reduction)requirements method is an effective method for specifying software system requirements.This paper presents a formal model analyzing SCR-style requirements.The analysis model mainly applies state translation rules,semantic computing rules and attributes to define formal semantics of a tabular notation in the SCR requirements method,and may be used to analyze requirements specifications to be specified by the SCR requirements method.Using a simple example,this paper introduces how to analyze consistency and completeness of requirements specifications.     

一种用于反编译代码与源代码的比较算法

现有反编译器产生的代码与对应的源代码之间存在差异,找到并理解差异有助于改进并完善反编译器的设计。该文给出一种适用于C语言反编译代码与源代码的比较算法。该算法以语法树匹配方法为基础,定义新的C语言中间代码表示形式并对表达式进行动态匹配,提高了语法树匹配的准确性。实验结果表明,该算法能有效计算出反编译代码与源代码之间的多数差异。     

Register allocation in a pattern matching code generator

Register allocation in a pattern-matching code generator is discussed, and a strategy for the allocation of registers is presented. The strategy is suitable for code generators that perform no data-flow analysis, but do perform common subexpression analysis. An implementation of the strategy has produced high quality code.     

CCNeter : C程序代码Petri网自动建模工具

CCNeter是实现扩展的Petri网——CNet自动可视化建模的工具,对程序语句从数据、操作和控制3个方面进行描述,刻画了程序代码中数据、操作以及控制之间的关系。它通过解析C工程中文件、函数模块、变量之间的依赖关系,自动形成程序的CNet规范,并根据CNet规范自动进行图形绘制和布局。CCNeter是实现程序静态分析自动化的重要前提。     

语法和语义结合的代码补全方法

在软件工程领域,代码补全是集成开发环境（integrated development environment,IDE）中最有用的技术之一,提高了软件开发效率,成为了加速现代软件开发的重要技术.通过代码补全技术进行类名、方法名、关键字等预测,在一定程度上提高了代码规范,降低了编程人员的工作强度.近年来,人工智能技术的发展促进了代码补全技术的发展.总体来说,智能代码补全技术利用源代码训练深度学习网络,从语料库学习代码特征,根据待补全位置的上下文代码特征进行推荐和预测.现有的代码特征表征方式大多基于程序语法,没有反映出程序的语义信息.同时,目前使用到的网络结构在面对长代码序列时,解决长距离依赖问题的能力依旧不足.因此,提出了基于程序控制依赖关系和语法信息结合共同表征代码的方法,并将代码补全问题作为一个基于时间卷积网络（time convolution network,TCN）的抽象语法树（abstract grammar tree,AST）节点预测问题,使得网络模型可以更好地学习程序的语法和语义信息,并且可以捕获更长范围的依赖关系.实验结果表明,该方法比现有方法的准确率提高了约2.8%.     

Platform‐independent code conversion within the C++ locale framework

This paper describes some of the author's experiences from a C++ implementation of a concordance program for texts in Old West Norse (also known as Old Icelandic) and Runic Swedish. Since the input to the program used a character repertoire that no standard one‐byte character encoding covers, it was natural to use Unicode to represent data both inside the program and in external files. Inside the program, each character was represented with C++ ‘wide characters’; the input and output was represented in UTF‐8. The author constructed C++ code conversion facets that convert data between those two representations during file I/O. This enabled him to successfully compile, and run, the concordance program on both Linux (Fedora Core 3 with gcc 3.4.2) and Windows XP (using Visual C++ .NET 2003). The only necessary change to the source when changing platform was isolated to the lines selecting which code conversion facet to use—all other pieces of code remained unchanged. In particular, the author could still use the standard C++ locale framework for collation and code conversion, in spite of the fact that the library‐provided code conversion facets had been replaced. Copyright © 2006 John Wiley & Sons, Ltd.     

Compiler Hacking for Source Code Analysis

Many activities related to software quality assessment and improvement, such as empirical model construction, data flow analysis, testing or reengineering, rely on static source code analysis as the first and fundamental step for gathering the necessary input information. In the past, two different strategies have been adopted to develop tool suites. There are tools encompassing or implementing the source parse step, where the parser is internal to the toolkit, and is developed and maintained with it. A different approach builds tools on the top of external already-available components such as compilers that output the program abstract syntax tree, or that make it available via an API.This paper discusses techniques, issues and challenges linked to compiler patching or wrapping for analysis purposes. In particular, different approaches for accessing the compiler parsing information are compared, and the techniques used to decouple the parsing front end from the analysis modules are discussed.Moreover, the paper presents an approach and a tool, XOgastan, developed exploiting the gcc/g++ ability to save a representation of the intermediate abstract syntax tree. XOgastan translates the gcc/g++ dumped abstract syntax tree format into a Graph eXchange Language representation, which makes it possible to take advantage of currently available XML tools for any subsequent analysis step. The tool is illustrated and its design discussed, showing its architecture and the main implementation choices made.     

Using abstraction and model checking to detect safety violations inrequirements specifications

Exposing inconsistencies can uncover many defects in software specifications. One approach to exposing inconsistencies analyzes two redundant specifications, one operational and the other property-based, and reports discrepancies. This paper describes a “practical” formal method, based on this approach and the SCR (software cost reduction) tabular notation, that can expose inconsistencies in software requirements specifications. Because users of the method do not need advanced mathematical training or theorem-proving skills, most software developers should be able to apply the method without extraordinary effort. This paper also describes an application of the method which exposed a safety violation in the contractor-produced software requirements specification of a sizable, safety-critical control system. Because the enormous state space of specifications of practical software usually renders direct analysis impractical, a common approach is to apply abstraction to the specification. To reduce the state space of the control system specification, two “pushbutton” abstraction methods were applied, one which automatically removes irrelevant variables and a second which replaces the large, possibly infinite, type sets of certain variables with smaller type sets. Analyzing the reduced specification with the model checker Spin uncovered a possible safety violation. Simulation demonstrated that the safety violation was not spurious but an actual defect in the original specification     

Formal requirements modelling with executable use cases and coloured Petri nets

This paper presents executable use cases (EUCs), which constitute a model-based approach to requirements engineering. EUCs may be used as a supplement to model-driven development (MDD) and can describe and link user-level requirements and more technical software specifications. In MDD, user-level requirements are not always explicitly described, since usually it is sufficient that one provides a specification, or platform-independent model, of the software that is to be developed. Therefore, a combination of EUCs and MDD may have potential to cover the path from user-level requirements via specifications to implementations of computer-based systems.     

Specifications: Formal and informal—a case study

Formal specifications (algebraic) are given for an informally specified small subsystem of the Change Management Automatic Build System. A comparison of the two specifications shows that although informal specifications are easier to read, the formal specifications are clearer, specify operation domains precisely, define the interaction between the operations, show the incompleteness of the informal specifications and are devoid of implementation details. The formal specifications pointed to the need of a function not in the subsystem whose inclusion would improve the system design. This inclusion is now being considered. However, the use of algebraic specifications requires practice and experience. Although the formal specification of large systems is somewhat impractical at the moment, experience in using formal specifications can lead to better informal specifications.     

A specification-based approach to concurrency analysis

The behavior of a concurrent program often depends on the arbitrary interleaving of computations performed by asynchronous processes. The resulting non-determinism can lead to such phenomena as deadlock and starvation, making program development extremely difficult, and consequently making the development of tools for formal analysis highly desirable.A specification-based approach to concurrency analysis is a particularly promising way of addressing some of the difficulties inherent in concurrent program development. According to this approach, a programmer first writes a specification describing the interprocess communication behavior of a concurrent program. A set of formal analysis techniques are then applied in an effort to determine whether the specification can be fully satisfied. If the analysis is successful, target code is generated automatically that conforms to the specification.This approach has a variety of benefits. While such properties as safety and liveness are rather difficult to discern in actual code, they are actually easy to include as part of a specification. Moreover, state spaces induced by specifications tend to be smaller and more manageable than state spaces of actual code, and this leads to more effective analysis techniques. Finally, the generation of interprocess communication code from formal specifications is accomplished in a relatively straightforward manner.Research partially supported by NSF grant CCR-9109231.     

一种基于树结构的数据报表发布体系及实现

文中给出了一种基于树结构的数据报表发布机制，使得数据报表既是数据的消费者，又是数据的产生者，将报表本身看作一个关系模型，作为树结构上的一个节点，可以由其它节点经过关系运算复合而成，也可以通过继承机制生成新的节点，介绍了节点的生成、解析及数据查询操作的递归算法，最后给出了一种整个系统的实现构架。     

Saving reuse from the noose: reuse of analogous specifications through human involvement in reuse process

Analogy is proposed as an alternative paradigm for the reuse of specifications during requirements analysis. First, critical determinants of analogies between software engineering problems are discussed in relation to a specification retrieval mechanism. Second, the process of specification reuse is examined. Specification reuse by analogy is knowledge-intensive, hence an important role is proposed for the analyst during specification reuse: analyst involvement would appear necessary to categorize a new problem, select between candidate reusable specifications, and customize the selected specification to the new domain. Finally, a specification reuse tool is proposed that recognises the collaborative nature of reuse by analogy. This tool assists and advises the analyst during reuse founded on cognitive models of analyst behaviour during analogous reasoning and reuse. The prototype version of this intelligent reuse advisor (Ira) is outlined.     

Object‐oriented processing of Java source code

Code transformation and analysis tools provide support for software engineering tasks such as style checking, testing, calculating software metrics as well as reverse‐ and re‐engineering. In this paper we describe the architecture and the applications of JTransform, a general Java source code processing and transformation framework. It consists of a Java parser generating a configurable parse tree and various visitors (transformers, tree evaluators) which produce different kinds of outputs. While our framework is written in Java, the paper further opens an opportunity for a new generation of XML‐based source code tools. Copyright © 2004 John Wiley & Sons, Ltd.