Search

On-line algorithm is an emerging area of research since last five decades with immense theoretical and practical significance. Here the sequence of inputs is received and processed by the algorithm one by one in order. At any instant of time, the algorithm has the knowledge of past and present inputs without knowledge of future inputs. Competitive analysis is a standard performance measure for on-line algorithms in which the performance of an on-line algorithm is compared with that of an optimum offline algorithm. List update problem is a well studied research problem in the area of on-line algorithms, which finds applications in data-compression, dictionary maintenance, collision resolution in hash table, symbol table organization in compiler and computing convex hull in computational geometry. From the literature it is known that Move To Front(MTF) is the best performing deterministic list update algorithm using singly linked list in all practical applications. In this paper, we study and analyse the performance of a deterministic on-line list update algorithm known as Move To Middle(MTM) using doubly linked list. We make a first attempt to find the competitive ratio of MTM algorithm, which was only experimentally studied in the literature. In our study by considering doubly linked list as the data structure and a new variant of standard full cost model, we obtain new competitive analysis result and prove that MTM is 2-competitive. From our competitive analysis result, we show that MTM outperforms MTF.

We describe an integrated solution to symbol, heap and logic engine memory management in a context where exchanges of arbitrary Prolog terms occur between multiple dynamically created engines, implemented in a new Java-based experimental Prolog system. As our symbols represent not just Prolog atoms, but also handles to Java objects (including arbitrary size integers and decimals), everything is centered around a symbol garbage collection algorithm ensuring that external objects are shared and exchanged between logic engines efficiently. Taking advantage of a tag-on-data heap representation of Prolog terms, our algorithm performs in-place updates of live symbol references directly on heap cells. With appropriate fine tuning of collection policies our algorithm provides an integrated memory management solution for Prolog systems, with amortized cost dominated by normally occurring heap garbage collection costs.

In order to adapt different languages and platforms, the paper discusses how to process and validate IDL symbol table and intermediate code by XML API. It puts emphasis on IDL API extension towards DOM API based on the idea of combining XML with IDL compilers. At last, the IDL compiler designing framework based on XML API is given, in which compiler front end can be managed and validated by some XML techniques and tools, IDL API can be validated on the basis of test, so IDL intermediate code is provided with maintainability, portability and generation. IDL compiler can be developed and extended by XML-based API, which realizes versatility and portability of modern compiler.

Compilers, during compilation, analyze the application being compiled and build up extensive knowledge about the program. This knowledge is essential for the compiler to produce correct object code. Though some part of this knowledge is retained in the generated object files as symbol table information to be used by the linker and/or debugger, most of it is discarded after the compilation is done. In this paper, we introduce the TRICK framework, which is an attempt to retain and reuse this internal information generated by the compiler as part of its program analysis, in building new tools or enhancing existing tools as well for reuse by the compiler for continuous program optimization. We present examples of how development and maintenance of various program analysis tools can be simplified by using the TRICK framework describing tools developed by our group as well as how TRICK framework can be employed in continuous program optimization by the compiler. TRICK framework can be part of both static and dynamic compilation system, though our current usage model is in the context of a static compilation system

Each symbol in a source program has a series of attributes that govern the operations performed on it. In this paper, we explore object-oriented techniques for representing the attributes of symbols and translating the operations performed on them. This approach is shown superior in memory and run-time speed to the procedural style traditionally used for writing compilers. We demonstrate object-oriented symbol management in a compiler for an arithmetic subset of C. We have used C++ --- a single-dispatching language --- to implement the same, but we emphasize the need for multiple dispatching to develop programs in a heavily-object-oriented style.

The language VTRT has been implemented in Borland Pascal as a protected-mode MS DOS interpreter. The integrated development environment program includes a special-purpose text editor and a debugger, which allows stepwise tracing of the program at the source code level and the pseudocode level, executes the program up to an interrupt point, and ensures full control over all interpreter components (symbol table, stack, heap).

rdp is a parser generator which accepts Iterator Backus Naur Form productions decorated with attributes and ANSI-C actions and produces recursive descent parsers. It has special support for the generation of tree-based intermediate forms, built-in symbol table handling for the implementation of context-sensitive components of the language syntax and a support library that includes a generalised graph handling module that can output graphs in a form suitable for use with well known visualisation tools.

An efficient LFG parser implementation of Indian languages in general and Bangla in particular has been discussed. It has been shown that the classical technique of nonconfigurational syntactic encoding principles lead to too many disjunctive constraints to be satisfied by the parser. Noting that most of the disjunctions do not exist if an a priori knowledge of the verb is available, a "delayed" syntactic encoding formalism has been proposed. The points of syntactic encoding of noun phrases have been treated a "forward references" that are to be temporarily maintained in a "symbol table" for later precipitation. The proposed solution has two parts. The first part deals with identification of forward reference points, which is done by introducing a new metavariable and augmenting the scope of the Locate operator. The second part deals with precipitation of forward references through special schemata called m-structure schemata projected by the verb. An extension of the solution to one type of Bangla complex sentences has also been proposed (in the Appendix). Implementation notes based on object-oriented programming principles have been provided.

The programming tradeoffs between structure-oriented and clause-oriented operations on data structures in Prolog are limited in current implementations because the assertion of clauses that include uninstantiated variables destroys any binding between these variables and those with which they are unified in the execution of the program. Built-in predicates for Prolog that allow one to assert predicate variables pointers, which are constants, rather than uninstantiated variables, are presented. The author shows: the possible performance benefits of clause-oriented implementations of data structures over equivalent structure-oriented versions, the logical implications of the proposed built-in predicates, and their practical significance by integrating them in C-Prolog and evaluating the two different implementations of the symbol table dictionary in D.H.D. Warren's pseudo-Pascal compiler example. >

The META/REDUCE translator writing system operates in a LISP environment closely interfaced with both LISP and REDUCE syntax. The language supports: BNF like syntax, recursive descent parsing schemes, lexical primitives, symbol table primitives, and automatic syntax error message generation. A complete simple arithmetic expression evaluator provides an introduction to the capabilities of the system. The body of the work describes the control constructs and primitives of the system. The paper is completed with the description of a working interpreter for a subset of a contemporary programming language. It is assumed that the reader has some familiarity with LISP 1.5 and REDUCE.

The Universal Compiling System (UCS) is a unified compiling system for a set of languages and architectures. The integrated implementation discipline of UCS results in reduced development and maintenance costs and increased reliability and efficiency. The key to the UCS design is the strict separation of the source language dependent processes from the architecture dependent processes. This is made possible through the use of an intermediate text and dictionary (symbol table) which is both language independent and architecture independent.

A technique using minimal perfect hash functions to generate small fast table driven frontends is described. A parser for the PASCAL language generated by this method is then presented.In this paper a technique for creating small fast table driven compiler frontends is described. To demonstate the practicality of this method, we give the code and tables for a demonstration parser for the PASCAL language.Our technique is based on minimal perfect hash functions, MPHF. A MPHF is a bijection from a set of N objects to the first N consecutive non-negative integers. We use the technique for generating MPHFs described by the author in [2] to generate three different hash tables: the parser table, the lexical table and the reserved word table. In [2] the author described an algorithm called the mincycle algorithm whose input is W: a set of N objects, R1 and R2: two positive integers, and hO:W->I, hi:W->O., R1-1 and h2:W->R1., R-1: three pseudo-random functions. Here I is the set of integers and R=R1+R2. The mincycle algorithm looks for and can be expected to find a function g:0., R-1->I such that h(w) = (h0(w) + g(h1(w)) + g(h2(w))) mod N is a MPHF.We will not give the details of the mincycle algorithm as they are described in detail elsewhere [2]. We merely note that if we can guarantee that w ε W, w' e W, h1(w)=hl(w') and h2(w)=h2(w') implies that w=w' then h0 serves no useful purpose and may be omitted.The parser is created directly from syntax diagrams which are slightly modified from those given by Jensen and Wirth [1]. From these syntax diagrams we have created an augmented transition network (ATN) [3]. The only actions we use are push and pop for a syntax stack containing states of the ATN and install, lookup, newscope and oldscope which manipulate a rudimentary symbol table. We use information from the symbol table only at states from which more than one valid transition is possible on seeing an identifier. Thus, checking for valid semantics is extremly rudimentary, but more complete semantic checking could be added to the existing syntactic framework.The parser code is given in figure 1. The output of lex is syntactic tokens. Statement 1: is a MPHF. If we do not find the state-token pair in the transition table (transtab) we use the default table (deftab) to find the next state and a (possibly null) action. The transition table (Table 1) gives each valid non-default state-token pair of the ATN along with its position in the transition table and its associated next state and action.The state table (Table 2) gives for each state its value in the state indirect table (stindtab) and its associated default next state and action. The token table (Table 3) gives for each token its value in the token indirect table (tokindtab). The parser contains 126 states, 53 tokens and 196 valid non-default state-token pairs.The lexical analyzer was created in a manner similar to the parser. The reserved word table was created using the algorithm given in [2]. Unlike Jensen and Wirth [1] we consider read, readln, write and writeln to be reserved words. For reasons of space only the parser is shown here.Although PASCAL is small as programming languages go, because of the ease with which the method described above created a PASCAL frontend, the author strongly suspects that this method is applicable to larger languages such as ADA.

This paper discusses the efficient implementation of Ada's visibility requirements. A scope stack and an unstructured name space are used to facilitate separate compilation and ensure that each Ada declaration takes a constant unit of time. Visibility issues affect practically every aspect of semantic analysis in Ada: declarations, statements, expressions, and separate compilation. The design of the symbol table package is, thus, a critical one. In this paper, I discuss the design goals of the symbol table for the Ada Integrated Environment (AIE) bootstrap compiler front end, and how they were influenced by the Ada language. Since the compiler is being heavily used by the AIE project, we have ample data with which to measure symbol table performance.

PEPL (Psychology Experiment Programming Language) is a real-time, on-line experimental control system designed for a 4K PDP-8 computer with minimal additional hardware. The system, consisting of the PEPL language, a symbol table for standard DEC assemblers, and an operating system, is capable of asynchronous, timed control of multiple subjects or experiments. The language offers the user high-level instructions for execution control, computation, timing, and I/O control.

Pi is a debugger written in C + +. This paper explains how object-oriented programming in C + + has influenced Pi's evolution. The motivation for object-oriented programming was to experiment with a browser-like graphical user interface. The first unforeseen benefit was in the symbol table: lazy construction of an abstract syntax-based tree gave a clean interface to the remainder of Pi, with an efficient and robust implementation. Next, though not in the original design, Pi was easily modified to control multiple processes simultaneously. Finally, Pi was extended to control processes executing across multiple heterogeneous target processors.

Forth is a unique threaded language ideally suited for microcomputers. Programs are incredibly compact; e.g. in 5K to 6K bytes you can get the interactive Forth compiler, running stand-alone as its own operating system including I/O drivers and other run-time routines, plus an assembler written in Forth (in case you want to optimize time-critical programs), virtual memory software, and a text editor. Not only does all this fit into 5K to 6K bytes (of which 4K are written in Forth), but it runs in the same space (plus 1K buffer), with no additional symbol table area, overlays, swapping, or use of any other software.And while Forth gives all the convenience of interactive interpreters, it is very fast. For most applications, the run-time overhead is 20 to 30% for minis and 70 to 100% for micros (compared to 1000% or more which is common for interpreters). Number-crunching applications may take longer. And when Forth isn't fast enough, the system's own assembler can be used to re-code inner loops.But the best news of all is that software development times are cut by half or more over assembly programming. The programming is entirely structured (there is no GOTO), and the resulting code is re-entrant and can be designed for PROM.Forth has been implemented on many microcomputers. A recommended configuration is 16K bytes and a terminal; a floppy is a good idea for storing source programs (and virtual memory for programs and data is supported). Forth works well with a CRT, so hard copy is less necessary.Forth has existed for several years, and is used commercially in a number of installations, but until recently it has been priced far out of reach of hobbyists, and even most computer experts have never heard of it. However, the language is in the public domain, and today low-cost versions are just becoming available. Also there is a new Forth Interest Group (787 Old County Rd, San Carlos, CA 94070), dedicated to letting the serious hobbyist and the professional know about Forth and how they can get it.

In programming practice it is often necessary to subsume records of different types under one common type such as an array, a file or a linked list. One has only to think of differently formatted records in a personnel file or of entries in a compiler's symbol table. Ever since PASCAL, records with variants constitute the most suitable language constructs available for this purpose.The problem of accessing record components within variants has not been satisfactorily solved by today's languages in two respects. In the first place uniqueness is demanded for the component names across all record variants, and this leads to an unnatural denotation in many cases. Secondly, there is no guarantee at compile time that access to a record variant will not result in a runtime error.In the present paper, ways of avoiding these problems are proposed.

The implementation in Algol 68R of a cross assembler for the PDP11 minicomputer to run on the ICL1900 is described. The assembler duplicates the features of the PAL11 assembler. RRE's Syntax Improving Device was used for a two pass assembly system. The cross assembler uses a tree structured symbol table, a lexical analyser to read in basic assembler items and code generation routines that use Algol 68 modes and operators to map the 8 bit bytes and 16 bit words of the mini onto the ICL1900 words. The cross assembler reproduces the error diagnostics of PAL11 with more detailed diagnostics available if required by the user. The assembler outputs binary program on paper tape for loading directly onto the mini.

Statistical data is presented on the distribution of FORTRAN identifiers as a function of length and initial character. The performance of two hash coding algorithms is tested with random probing on a pool of actual FORTRAN identifiers. A significant gain in performance is observed relative to the theoretical case of random keys, which reinforces the case for hash coding for symbol table construction in FORTRAN compilers.

An interpretive hybrid programming language, HYBRID, has been developed by The Foxboro Company, for use in a small hybrid computer system. The TELETYPE* oriented language comprises a command structure resembling FOCAL and offers hybrid instructions similar to HOI. It provides features seldom found in software for small (mini) computers with limited core, such as computed (variable) part and step numbers in go-to instructions, foreground- background operational modes, monitor functions, and a full assortment of hybrid and interrupt handling capabilities. The HYBRID program occupies approximately 4K of core in a PDP-7t 18-bit computer and includes routines for drum (disc) and paper tape input- output of source and data files. It permits the use of assembly (machine) language routines to be called by source program commands. The variable list (Symbol Table) is referenced in a binary search mode, which results in fast execution speed as well as efficient running of the source program. The language contains a number of error-checking and source-program protection provisions to make it as user-friendly and fault-tolerant as possible .

The format of a dictionary (symbol table) adequate for a PL/I compiler is presented. The dictionary contains two types of entries: name and attribute. Methods of storing name entries are discussed. Emphasis is placed on the contents and structure of the attribute entries necessary to handle structures in a block environment. Extensions of the method that allow one-pass compilation are discussed. The relevance of the dictionary structure to other higher-level language compilers is explained.

The general advantages of using large computers to assemble code for laboratory minicomputers are discussed. A PDP-8 assembler implemented under IBM OS/360 is presented, and its use is described.