Abstract Despite the parsing power of LR/LALR algorithms, e.g. YACC, programmers often choose to write recursive‐descent parsers by hand to obtain increased flexibility, better error handling, and ease of debugging. We introduce ANTLR, a public‐domain parser generator that combines the flexibility of hand‐coded parsing with the convenience of a parser generator, which is a component of PCCTS. ANTLR has many features that make it easier to use than other language tools. Most important, ANTLR provides predicates which let the programmer systematically direct the parse via arbitrary expressions using semantic and syntactic context; in practice, the use of predicates eliminates the need to hand‐tweak the ANTLR output, even for difficult parsing problems. ANTLR also integrates the description of lexical and syntactic analysis, accepts LL(k) grammars for k > 1 with extended BNF notation, and can automatically generate abstract syntax trees. ANTLR is widely used, with over 1000 registered industrial and academic users in 37 countries. It has been ported to many popular systems such as the PC, Macintosh, and a variety of UNIX platforms; a commercial C++ front‐end has been developed as a result of one of our industrial collaborations.

To evaluate the performance of a memory system, computer architects must determine the miss rate m of a cache C when running program P. Typically, the measured miss rate depends on the specific address mapping M of P set arbitrarily by the compiler and linker. The author removes the effect of the address-mapping on the miss rate by analyzing a symbolic trace T of basic blocks. By assuming each basic block has an equal probability of ending up anywhere in the address map, he determines the expected miss rate averaged over all possible address mappings. The resulting gap model gives the expected miss rate for instruction caches of varying cache size, line size, and set associativity. The model is simple but robust, and turns out to be the familiar LRU stack model with a statistical viewpoint. The model allows a trace of arbitrary length to he compactly summarized in a few thousand bytes of information. It also predicts how an intervening trace, such as an operating system call or a task switch, will affect the miss rate. Comparisons to measured miss rates from SPEC 92 instruction traces show that the model typically has relative differences of less than 20% for a variety of cache parameters.>

Linking is traditionally a batch process that resolves cross-references between object modules and run-time libraries to produce a stand-alone executable image. Because most program changes only involve a small part of the program, we have implemented an incremental linker, named Inclink, that processes only the changed modules. Inclink generates a new executable in time proportional to the size of change; in contrast, a batch linker generates an executable in time proporitonal to the size of the program. To minimize updates to the executable, Inclink allocates extra space for every module. By allocating 24 percent more space in the executable for overflows, Inclink can update a module in place over 97 percent of the time. Measurements show that Inclink is more than an order of magnitude faster than the UNIX [2] batch linker and that 88 percent of all links will take less than 2 s of CPU time on a MicroVAX-2, independent of program size.

Efficient data layout is an important aspect of the compilation process. A model for the creation of perfect memory maps for large-scale parallel machines capable of user-controlled partitionable single-instruction-multiple data/single-program-multiple data (SIMD/SPMD) operation is developed. The term perfect implies that no memory fragmentation occurs and ensures that the memory map size is kept to a minimum. A major constraint on solving this problem is based on the single program nature of both the SIMD and SPMD modes of parallelism. It is assumed that all processors within the same submachine used identical addresses to access corresponding data items in each of their local memories. Necessary and sufficient conditions are derived for being able to create perfect memory maps, and results are applied to several partitionable interconnection networks.>

To profile the changes made to programs during development and maintenance, the authors have instrumented the 'make' utility that is used to compile and link programs. With minor modifications, they have used 'make' to find out how much time programmers spend waiting for compiling and linking, how many modules are compiled each time a program is linked, and the change in size of the compiled modules. Measurements show that most programs are relinked after only one or two modules are recompiled, and that over 90% of all recompilations yield object code that is less than 100 bytes larger in size. The authors are using these results to guide the design of an incremental programming environment, particularly with respect to an incremental linker.>