Syntax-directed correction of syntax errors

The systematic approach to compilation represented by syntax-directed compilers makes possible a similarly systematic approach to the automatic correction of syntax errors. This paper describes the syntax-directed syntax error correction system EXPL. Techniques for pinpointing the locations of syntax errors, generating sets of possible corrections and for choosing the best correction from such a set are presented. A particularly promising approach involves the use of semantic information to assist in the elimination of inappropriate syntactic corrections.     

语法制导翻译在汇编程序自动构造中的应用

提出了语法制导翻译用于自动构造汇编程序的方法。该方法简洁实用,自动化程度高,可用于计算机系统汇编程序的自动构造。     

Tailored compression of Java class files

Java class files can be transmitted more efficiently over a network if they are compressed. After an examination of the class file structure and obtaining statistics from a large collection of class files, we propose a compression scheme that is tailored to class files. Our scheme achieves significantly better compression than commonly used methods such as ZIP. © 1998 John Wiley & Sons, Ltd.     

Sre—a syntax recognizing editor

This paper presents a syntax-directed editor dubbed SRE, for syntax recognizing editor. Unlike other syntax-directed editors, SRE enables the user to edit programs with nearly the same natural and unrestrictive ease as a conventional text editor. In addition, it helps identify syntax errors and many typing errors before leaving the editor and attempting to compile a program. Programs are also formatted during entry, thereby providing immediate visual feedback of the recognized structure. The editor replaces the scanner/parser pass of a conventional compiler and thus reduces compilation time substantially.     

Automatic synthesis of compression techniques for heterogeneous files

We present a compression technique for heterogeneous files, those files which contain multiple types of data such as text, images, binary, audio, or animation. The system uses statistical methods to determine the best algorithm to use in compressing each block of data in a file (possibly a different algorithm for each block). The file is then compressed by applying the appropriate algorithm to each block. We obtain better savings than possible by using a single algorithm for compressing the file. The implementation of a working version of this heterogeneous compressor is described, along with examples of its value toward improving compression both in theoretical and applied contexts. We compare our results with those obtained using four commercially available compression programs, PKZIP, Unix compress, Stufflt, and Compact Pro, and show that our system provides better space savings.     

An experiment in parallel program design

This paper describes the development of a program to solve the Henderson and Snowdon ‘Telegrams Problem’, the program being expressed as a set of communicating sequential processes (Hoare⁷).     

基于多实体的矢量数据压缩改进算法

矢量数据压缩在地形环境仿真、制图综合、GIS等研究中具有重要作用,对增加移动设备的存储能力和提高矢量数据的网络传输效率来说是一项很重要的工作。根据动态规划算法理论、Douglas-Peucker算法和矢量数据的特点,提出了基于动态规划算法的矢量数据压缩的模型和改进方法,通过一条参考路径构造一条带形成最小误差搜索范围,同时条带宽度可自适应调整。并将单一实体的优化压缩算法扩展为基于多实体的压缩算法,解决了图层压缩的全局优化问题。实验结果表明,该方法具有较高的效率,能够得到较小的压缩误差。     

A simpler analysis of Burrows–Wheeler-based compression

In this paper, we present a new technique for worst-case analysis of compression algorithms which are based on the Burrows–Wheeler Transform. We mainly deal with the algorithm proposed by Burrows and Wheeler in their first paper on the subject [M. Burrows, D.J. Wheeler, A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation, Palo Alto, California, 1994], called bw0. This algorithm consists of the following three essential steps: (1) Obtain the Burrows–Wheeler Transform of the text, (2) Convert the transform into a sequence of integers using the move-to-front algorithm, (3) Encode the integers using Arithmetic code or any order-0 encoding (possibly with run-length encoding).     

A program structuring preprocessor for a macro assembly language

This paper deals with design considerations and implementation of a program structuring preprocessor for a macro assembly language. The macro assembly language is used for writing the code generation pass of a compiler. Macro instructions become lengthy, tedious and cumbersome when they incorporate some mild code improvement. This is chiefly because the macro assembly language lacks an adequate program structuring facility. Program structuring is a great help in improving ease of programming and the under-standability of the expansion control statements of a macro instruction in such a kind of programming. Considerations on the design of the source language and the outline of implementation are described. The design objective is ease of implementation and ease of use, and is fairly well satisfied by the language.     

Improving App Inventor usability via conversion between blocks and text

We have developed TAIL, a textual programming language isomorphic to the blocks language of MIT App Inventor (AI), and have extended AI with code blocks, a novel mechanism that enables bidirectional conversions between blocks and text fragments. TAIL improves AI׳s usability by facilitating the reading, writing, and sharing of programs, and may also ease the transition from blocks to text programming.     

Tokenisation and compression of Java class files

Method calls in object oriented languages, such as Java, are bound at run-time, making the method binding technique very important for the performance of the language. Efficient implementations can rely on having additional memory and/or processing power available either to store lookup tables or to allow for the construction of caches or rewriting of instructions during runtime. These are luxuries not always available on mobile devices such as mobile phones, tablets, etc. In this paper we describe a novel way of tokenising and compressing method dispatch tables to provide an efficient dispatch process which could be implemented in hardware in only a few operations. We demonstrate this in the context of Java, also showing a significant reduction in size for the resulting class files.     

Using static suffix array in dynamic application: Case of text compression by longest first substitution

Over the last decade, enhanced suffix arrays (ESA) have replaced suffix trees in many applications. Algorithms based on ESAs require less space, while allowing the same time efficiency as those based on suffix trees. However, this is only true when a suffix structure is used as a static index. Suffix trees can be updated faster than suffix arrays, which is a clear advantage in applications that require dynamic indexing. We show that for some dynamic applications a suffix array and the derived LCP-interval tree can be used in such a way that the actual index updates are not necessary. We demonstrate this in the case of grammar text compression with longest first substitution and provide the source code. The proposed algorithm has O(N²)$O(N^2)$ worst case time complexity but runs in O(N)$O(N)$ time in practice.     

Word-based text compression

The development of efficient algorithms to support arithmetic coding has meant that powerful models of text can now be used for data compression. Here the implementation of models based on recognizing and recording words is considered. Move-to-the-front and several variable-order Markov models have been tested with a number of different data structures, and first the decisions that went into the implementations are discussed and then experimental results are given that show English text being represented in under 2-2 bits per character. Moreover the programs run at speeds comparable to other compression techniques, and are suited for practical use.     

S-semantics for logic programming: A retrospective look

The paper provides an overview of the s-semantic approach to the semantics of logic programs which had been developed about twenty years ago. The aim of such an approach was that of providing a suitable base for program analysis by means of a semantics which really captures the operational behavior of logic programs, and thus offers useful notions of observable program equivalences. The semantics is given in terms of extended interpretations, which are more expressive than Herbrand interpretations, extends the standard Herbrand semantics, and can be obtained as a result of both top-down and bottom-up constructions. The approach has been applied to several extensions of positive logic programs and used to develop semantic-based techniques for program analysis, verification and transformation.     

A new generic scheme for functional logic programming with constraints

In this paper we propose a new generic scheme CFLP풟, intended as a logical and semantic framework for lazy Constraint Functional Logic Programming over a parametrically given constraint domain 풟. As in the case of the well known CLP풟 scheme for Constraint Logic Programming, 풟 is assumed to provide domain specific data values and constraints. CFLP풟 programs are presented as sets of constrained rewrite rules that define the behavior of possibly higher order and/or non-deterministic lazy functions over 풟. As a main novelty w.r.t. previous related work, we present a Constraint Rewriting Logic CRWL풟 which provides a declarative semantics for CFLP풟 programs. This logic relies on a new formalization of constraint domains and program interpretations, which allows a flexible combination of domain specific data values and user defined data constructors, as well as a functional view of constraints. This research has been partially supported by the Spanish National Projects MELODIAS (TIC2002-01167), MERIT-FORMS (TIN2005-09207-C03-03) and PROMESAS-CAM (S-0505/TIC/0407).     

LZ trie and dictionary compression

An efficient algorithm for trie compression has already been described. Here we present its practical value and demonstrate its superiority in terms of space savings to other methods of lexicon compression. Apart from simple lexicons, a compressed trie can, with some additional processing, be used as a component in the compact representation of simple static databases. We present the potential of the algorithm in compressing natural language dictionaries. Copyright © 2005 John Wiley & Sons, Ltd.     

基于动态规划算法的矢量压缩方法研究与改进

将动态规划算法应用于矢量数据压缩是一种非常有效的优化压缩方法,可以得到压缩误差最小的压缩曲线,但是会导致局部失真明显。针对该缺点提出一种改进算法,通过在动态规划算法执行过程中设定阈值限制最大位移来防止局部失真,同时对A. KOLESNIKOV等提出的原动态规划算法公式的错误进行了纠正。实验表明,改进算法在保持原算法优势的同时,可以较好地解决压缩曲线局部失真问题。     

线性调频信号数字脉压滤波器优化设计

针对线性调频(LFM)信号的高脉压旁瓣问题,提出了一种基于二阶锥规化的数字脉压旁瓣抑制滤波器设计方法.该方法以期望的压缩脉冲波形主瓣为参考,对脉压旁瓣进行控制,将脉压滤波器的设计转化为二阶锥规化问题进行求解.与已有方法相比,所提方法可以兼顾峰值旁瓣、主瓣宽度、处理增益损失等指标,具有设计灵活的优点.仿真结果验证了该方法的有效性,与常用的频域加窗方法相比,该方法的旁瓣抑制效果得到了改善,在归一化多普勒频移为0.005时,脉压主副比仍在44 dB以上,并且脉压信号的相位与参考响应基本一致,较好地满足了现代雷达系统的要求.     

Rewriting executable files to measure program behavior

Inserting instrumentation code in a program is an effective technique for detecting, recording, and measuring many aspects of a program's performance. Instrumentation code can be added at any stage of the compilation process by specially-modified system tools such as a compiler or linker or by new tools from a measurement system. For several reasons, adding instrumentation code after the compilation process—by rewriting the executable file—presents fewer complications and leads to more complete measurements. This paper describes the difficulties in adding code to executable files that arose in developing the profiling and tracing tools qp and qpt. The techniques used by these tools to instrument programs on MIPS and SPARC processors are applicable in other instrumentation systems running on many processors and operating systems. In addition, many difficulties could have been avoided with minor changes to compilers and executable file formats. These changes would simplify this approach to measuring program performance and make it more generally useful.