The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
This paper describes a tool for the transformation of attributed trees using pattern matching. The trees to be processed are defined by a formalism based on contextfree grammars. Operations for trees such as composition and decomposition are provided. The approach can be characterized as an amalgamation of trees or terms including pattern matching, with recursion, attribute grammars, and imperative...
Classic LR(1) parsing methods have the problem of producing too large parsing tables for programming language grammars. An alternative is to build an automaton that combines the lookahead symbol with reading the parsing stack from its top, to determine the next parsing action. The building procedure for such a parser and its use for parsing are presented through an example grammar. Results from an...
A simple extension of the usual LR parser construction is made in order to build a translator. The LR parsing algorithm is extended by a facility to do output operations within the action shift and reduce. A class of translation grammars, called R-translation grammars, is introduced as an extension of the class of postfix translation grammars. Transformations called shaking-down and postponing of...
This paper deals with a method how an effective attribute-directed top-down parser and attribute evaluator can be constructed from a conditional L-attributed grammar (CLAG). The method is based on exploitation of an attribute stack in attribute evaluation and on definition of a translation scheme for CLAG.
The decomposition of attribute grammars into modules is investigated. In our approach the alternative rules of a nonterminal may be separated into different modules. The aim of our concept is the generation of special grammars in respect to the design decisions of a compiler writer. Therefore, a module represents a concrete syntactic or semantic design decision. The import- and export-interface of...
This paper presents an overview of an integrated graphic environment called P-GEN(1) to develop applications based on attribute grammars. The system has a modular structure to enable integration of different modules for all phases of the processing of an attribute grammar specification. This environment contains routines for transforming attribute grammar specifications written in different formalisms...
Identification is the task of finding the relation between used identifier occurrences and the declared entities of a program. The paper presents the techniques needed for the implementation of high-level identification specifications based on visibility rules. The underlying specification method is related to descriptions in language reports defining the identification in terms of validity and hiding...
The central task of symbol table administration is identification of all identifiers used in the source program under consideration of visibility rules varying between the different programming languages. Usually this problem is handled by a hash search of the identifier and an additional decision about the visibility of this identifier in the current program region (“scoping problem”). The most used...
There are many possible implementations of some very useful programming abstractions (sets, lists, and maps, to name a few), and selecting from among them is currently one of the early tasks in the design of a software system. While programming discipline and/or language features may allow the user to change implementations of an abstraction relatively easily, there remains the inherent problem of...
LDL is a system supporting the design of procedural programming languages and generating interpreters for prototyping purposes. Moreover, test sets for testing interpreters/compilers of the developed language can be generated. LDL is based on GSFs — a kind of attribute grammars — and uses the denotational approach for semantics definition. For the prototype interpreter its correctness can be proved.
We report progress on the development of Actress, a compiler generator based on action semantics. It consists of a number of modules, written in SML, that can be composed to construct either an action notation compiler or a simple compiler generator. We also outline current and future developments that will improve the quality of the generated compilers.
When confronted with the requirement to supply language processors for a wide range of languages, hardware architectures, and operating systems, the conventional approach to software reuse — decoupling language specific front ends from hardware specific code generators by some common intermediate representation — proves to be insufficient. A larger set of decoupling interfaces can be defined such...
We present an interprocedural generalization of the well-known (intraprocedural) Coincidence Theorem of Kam and Ullman, which provides a sufficient condition for the equivalence of the meet over all paths (MOP) solution and the maximal fixed point (MFP) solution to a data flow analysis problem. This generalization covers arbitrary imperative programs with recursive procedures, global and local variables,...
This paper reports on provably correct compiler implementation in the ESPRIT basic research action 3104 ProCoS (Provably Correct Systems). A sharp distinction is drawn between correctness of the specification of a compiler and correctness of the actual implementation. The first covers semantical correctness of the code to be generated, whereas the second concerns correctness of the compiler program...
As object oriented languages ease software construction significantly, these languages are very promising candidates for parallelizing compilers. To combine the advantages of object oriented programming with the power of parallel processing two major problems have to be solved: the virtual function and the class scope problem. We present solutions to these problems and exemplify them by extending a fast interprocedural data flow analysis algorithm...
The tree pattern matching approach for code selection has proven very successful. This paper presents an algorithm to test the completeness of a code selector specification. A specification is said to be complete, if it can produce code for every possible intermediate code tree produced by the front end. To enable a code generator generator to test the completeness property current code selector...
In this paper, we present a new register allocation framework based on hierarchical cyclic interval graphs. We motivate our approach by demonstrating that cyclic interval graphs provide a feasible and effective representation to characterize sequences of live ranges of variables in successive iterations of a loop. Based on this representation we provide a new heuristic algorithm for minimum register...
Conventional compilers typically ignore the potential benefits of keeping array elements in registers for reuse, due in part to the fact that standard data flow analysis techniques used in register allocation are not expressive enough to distinguish among individual array elements. This paper introduces the concept of register pipelining as an integrated approach to register allocation for both scalar...
We designed heuristics for applying the list scheduling algorithm to processors with complex pipelines. On these processors the pipeline can stall due to resource contention (structural hazards) in addition to the usual data hazards. Conventional heuristics consider only data hazards. Our heuristics reduce structural hazards, too. Code with much instruction-level parallelism is optimized to avoid...
This paper reports the results of a comparison between a new class of architectures, called transport-triggered architectures, and traditional architectures, called operation-triggered architectures. It does this comparison by means of the MOVE-i860, which is a transport-triggered approximation of the i860. Several benchmarks are scheduled for the MOVE-i860 by a software pipelining scheduler. By scheduling...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.