LIDO(ID:1492/lid003)Input language for the attribute evaluator generator LIGA (a successor of GAG and a subsystem of the Eli compiler-compiler). LIDO is derived from GAG's input language ALADIN. Related languages
References: This paper is an application of the "literate programming" paradigm to language definition. It was generated by Eli from a specification. A complete "lint" processor for the language it defines was also generated by Eli from that specification. The generated processor detects and reports invalid tokens, syntax errors, undefined and multiply-defined identifiers, and type errors. In other words, it verifies that a program conforms to the syntax and complete static semantics of the language. When you read this paper, you are reading a complete, formal definition of a language. Nothing is left out, and nothing is left to your imagination. The formalisms used in this definition are context-free grammars, attribute grammars in the style of LIDO, and a notation for describing operator overloading. Formal definitions of various aspects of the language appear as macros embedded in the natural-language description. These embedded macros are numbered sequentially, and the numbers are used to cross-reference macro definitions and uses. Eli's library has been used to advantage in several places. For example, macros 2, 5 and 6 use "canned descriptions" to avoid the need for repeating well-known regular expressions for C basic symbols, and macro 9 invokes library routines for name analysis [7]. Error reports like the one in macro 10 are output by a library module. The definition has been tested by generating the processor and processing a suite of programs, some of which conform to the language definition and others of which deviate from it. Admittedly, the language being defined is a simple one. Its translation provides a project for an undergraduate compiler construction course in which no tools are used [11]. It illustrates an appropriate set of compilation problems without introducing uninteresting complications. How does the approach represented by this paper scale up? I can't answer that question precisely, because this paper is our first attempt at formalizing an existing natural-language definition. We do have other language definitions, but they consist solely of the formal specifications without the descriptive text. For example, a specification for Icon from which Eli generates a processor that verifies Icon programs and translates them into the standard interpretive representation consists of just over 3400 lines of text. (The translator generated from the Icon specification runs only about 15% slower than the hand-coded translator distributed by the Icon group.) Eli is a joint project of the Universities of Colorado and Paderborn. It consists of a collection of off-the-shelf tools managed by an expert system. The form of specification illustrated by this paper was made possible by our recent integration of FunnelWeb. Extract: The C-- Language The C-- Language C-- is a scaled-down version of C. The features selected illustrate basic problems for compiler designers: scanning, parsing, name analysis, overload resolution, static storage allocation and code generation. Features that merely increase the implementation effort without illustrating such techniques were excluded. This chapter defines the structure and meaning of a C-- program. It has five sections, each dealing with one aspect of the language: basic symbols and comments, program structure, declarations, expressions and statements. Basic symbols are the indivisible atoms of the language, and their meanings are defined by relating them to our shared experience with programming languages. All other constructs are composite; each is formed by combining parts. Their meanings can thus be defined in terms of the meanings of their components and fundamental concepts such as "sequence of execution". in [ACM SIGPLAN] SIGPLAN Notices 28(02) February 1993 view details |