42-442: The TREE-META (or Tree Meta , TREEMETA ) Translator Writing System is a compiler-compiler system for context-free languages originally developed in the 1960s. Parsing statements of the metalanguage resemble augmented Backus–Naur form with embedded tree-building directives. Unparsing rules include extensive tree-scanning and code-generation constructs. TREE-META was instrumental in the development of NLS (oN-Line System) and
84-451: A meta programming metalanguage program. Many advocates of the language Forth call the process of creating a new implementation of Forth a meta-compilation and that it constitutes a metacompiler. The Forth definition of metacompiler is: This Forth use of the term metacompiler is disputed in mainstream computer science. See Forth (programming language) and History of compiler construction . The actual Forth process of compiling itself
126-527: A syntax of a generated compiler's target programming language and actions that should be taken against its specific constructs. Source code for a parser of the programming language is returned as the parser generator's output. This source code can then be compiled into a parser, which may be either standalone or embedded. The compiled parser then accepts the source code of the target programming language as an input and performs an action or outputs an abstract syntax tree (AST). Parser generators do not handle
168-475: A compiler which could in turn, compile a subset of PL/I. This system had extensive statistic-gathering facilities and was used to study the characteristics of top-down analysis. SIMPLE is a specialized translator system designed to aid the writing of pre-processors for PL/I, SIMPLE, written in PL/I, is composed of three components: An executive, a syntax analyzer and a semantic constructor. The TREE-META compiler
210-480: A compiler-compiler called TMG (presented in 1965). TMG was used to create early compilers for programming languages like B , PL/I and ALTRAN . Together with metacompiler of Val Schorre, it was an early inspiration for the last chapter of Donald Knuth 's The Art of Computer Programming . The LOT system was developed during 1966 at Stanford Research Institute and was modeled very closely after Meta II. It had new special-purpose constructs allowing it to generate
252-555: A formal description of programming language semantics, typically using denotational semantics . This approach is often called 'semantics-based compiling', and was pioneered by Peter Mosses ' Semantic Implementation System (SIS) in 1978. However, both the generated compiler and the code it produced were inefficient in time and space. No production compilers are currently built in this way, but research continues. The Production Quality Compiler-Compiler ( PQCC ) project at Carnegie Mellon University does not formalize semantics, but does have
294-635: A general reference. The syntax and implementation technique of Schorre's system laid the foundation for most of the systems that followed. The system was implemented on a small 1401, and was used to implement a small ALGOL -like language. Many similar systems immediately followed. Roger Rutman of AC Delco developed and implemented LOGIK, a language for logical design simulation, on the IBM 7090 in January 1964. This compiler used an algorithm that produced efficient code for Boolean expressions. Another paper in
336-403: A higher level of abstraction . A metalanguage operates on a higher level of abstraction in order to describe properties of a language. Backus–Naur form (BNF) is a formal metalanguage originally used to define ALGOL 60 . BNF is a weak metalanguage , for it describes only the syntax and says nothing about the semantics or meaning. Metaprogramming is the writing of computer programs with
378-469: A metacompiler in March 1963 that utilized a CRT display on the time-sharing PDP-l. This compiler produced actual machine code rather than interpretive code and was partially bootstrapped from Meta I. Schorre bootstrapped Meta II from Meta I during the spring of 1963. The paper on the refined metacompiler system presented at the 1964 Philadelphia ACM conference is the first paper on a metacompiler available as
420-464: A metacompiler. Programming in Forth is adding new words to the language. Changing the language in this way is metaprogramming . Forth is a metacompiler, because Forth is a language specifically designed for metaprogramming. Programming in Forth is extending Forth adding words to the Forth vocabulary creates a new Forth dialect . Forth is a specialized metacompiler for Forth language dialects. Design of
462-412: A semi-formal framework for machine description. Compiler-compilers exist in many flavors, including bottom-up rewrite machine generators (see JBurg ) used to tile syntax trees according to a rewrite grammar for code generation, and attribute grammar parser generators (e.g. ANTLR can be used for simultaneous type checking, constant propagation, and more during the parsing stage). Metacompilers reduce
SECTION 10
#1732780975088504-791: A valuable tool for advanced software engineering projects. Other examples of parser generators in the yacc vein are ANTLR , Coco/R , CUP, GNU Bison , Eli, FSL, SableCC , SID (Syntax Improving Device), and JavaCC . While useful, pure parser generators only address the parsing part of the problem of building a compiler. Tools with broader scope, such as PQCC , Coco/R and DMS Software Reengineering Toolkit provide considerable support for more difficult post-parsing activities such as semantic analysis, code optimization and generation. The earliest Schorre metacompilers, META I and META II, were developed by D. Val Schorre at UCLA. Other Schorre based metacompilers followed. Each adding improvements to language analysis and/or code generation. In programming it
546-517: Is a combination of a Forth being a self-hosting extensible programming language and sometimes cross compilation , long established terminology in computer science. Metacompilers are a general compiler writing system. Besides the Forth metacompiler concept being indistinguishable from self-hosting and extensible language. The actual process acts at a lower level defining a minimum subset of forth words , that can be used to define additional forth words, A full Forth implementation can then be defined from
588-404: Is a compiled test function returning success or failure . <name> is the function name. <body> is a form of logical expression consisting of tests that may be grouped, have alternates, and output productions. A test is like a bool in other languages, success being true and failure being false . Defining a programming language analytically top down is natural. For example,
630-418: Is a powerful attribute allowing easier development of computer programming languages and other computer tools. Command line processors, text string transforming and analysis are easily coded using metaprogramming metalanguages of metacompilers. A full featured development package includes a linker and a run time support library . Usually, a machine-oriented system programming language , such as C or C++,
672-546: Is a powerful tool, of many metacompilers, allowing the easy extension of their own metaprogramming metalanguage. The feature that separates a metacompiler apart from other compiler compilers is that it takes as input a specialized metaprogramming language that describes all aspects of the compiler's operation. A metaprogram produced by a metacompiler is as complete a program as a program written in C++ , BASIC or any other general programming language . The metaprogramming metalanguage
714-418: Is a prime example of a domain-specific language, designed for the domain of compiler writing. A metacompiler is a metaprogram usually written in its own metalanguage or an existing computer programming language. The process of a metacompiler, written in its own metalanguage, compiling itself is equivalent to self-hosting compiler . Most common compilers written today are self-hosting compilers. Self-hosting
756-495: Is a programming tool that creates a parser , interpreter , or compiler from some form of formal description of a programming language and machine. The most common type of compiler-compiler is called a parser generator . It handles only syntactic analysis . A formal description of a language is usually a grammar used as an input to a parser generator. It often resembles Backus–Naur form (BNF), extended Backus–Naur form (EBNF), or has its own syntax. Grammar files describe
798-479: Is able to compile its own source code and other languages. Among the earliest programs of the original Unix versions being built at Bell Labs was the two-part lex and yacc system, which was normally used to output C programming language code, but had a flexible output system that could be used for everything from programming languages to text file conversion. Their modern GNU versions are flex and bison . Some experimental compiler-compilers take as input
840-563: Is common to use the programming language name to refer to both the compiler and the programming language, the context distinguishing the meaning. A C++ program is compiled using a C++ compiler. That also applies in the following. For example, META II is both the compiler and the language. The metalanguages in the Schorre line of metacompilers are functional programming languages that use top down grammar analyzing syntax equations having embedded output transformation constructs. A syntax equation:
882-415: Is needed to write the support library. A library consisting of support functions needed for the compiling process usually completes the full metacompiler package. In computer science, the prefix meta is commonly used to mean about (its own category) . For example, metadata are data that describe other data. A language that is used to describe other languages is a metalanguage . Meta may also mean on
SECTION 20
#1732780975088924-500: Is not just a recognizer, but also outputs the assembly language for the input. It demonstrates one of the key features of TREE-META, which is tree pattern matching. It is used on both the LHS (GET and VAL for example) and the RHS (ADD and SUB). % This is an ALGOL-style comment delimited by % Compiler-compiler In computer science , a compiler-compiler or compiler generator
966-486: The semantics of the AST, or the generation of machine code for the target machine. A metacompiler is a software development tool used mainly in the construction of compilers , translators , and interpreters for other programming languages. The input to a metacompiler is a computer program written in a specialized programming metalanguage designed mainly for the purpose of constructing compilers. The language of
1008-526: The 1964 ACM proceedings describes Meta III , developed by Schneider and Johnson at UCLA for the IBM 7090. Meta III represents an attempt to produce efficient machine code, for a large class of languages. Meta III was implemented completely in assembly language. Two compilers were written in Meta III, CODOL, a compiler-writing demonstration compiler, and PUREGOL, a dialect of ALGOL 60. (It was pure gall to call it ALGOL). Late in 1964, Lee Schmidt bootstrapped
1050-403: The ability to treat programs as their data. A metacompiler takes as input a metaprogram written in a specialized metalanguages (a higher level abstraction) specifically designed for the purpose of metaprogramming. The output is an executable object program. An analogy can be drawn: That as a C++ compiler takes as input a C++ programming language program, a meta compiler takes as input
1092-399: The base set. This sounds like a bootstrap process. The problem is that almost every general purpose language compiler also fits the Forth metacompiler description. Just replace X with any common language, C, C++, Pascal , COBOL , Fortran , Ada , Modula-2 , etc. And X would be a metacompiler according to the Forth usage of metacompiler. A metacompiler operates at an abstraction level above
1134-414: The compiler it compiles. It only operates at the same (self-hosting compiler) level when compiling itself. One has to see the problem with this definition of metacompiler. It can be applied to most any language. However, on examining the concept of programming in Forth, adding new words to the dictionary, extending the language in this way is metaprogramming. It is this metaprogramming in Forth that makes it
1176-463: The compiler produced is called the object language. The minimal input producing a compiler is a metaprogram specifying the object language grammar and semantic transformations into an object program . A typical parser generator associates executable code with each of the rules of the grammar that should be executed when these rules are applied by the parser. These pieces of code are sometimes referred to as semantic action routines since they define
1218-484: The input stream and enough other facilities to parse any context-sensitive language. This system was successfully released to a wide number of users and had many string-manipulation applications other than compiling. It has many elaborate push-down stacks, attribute setting and testing facilities, and output mechanisms. That Meta 5 successfully translates JOVIAL programs to PL/I programs demonstrates its power and flexibility. Robert McClure at Texas Instruments invented
1260-411: The input was then processed by a simple form of unparse rules. The unparse rules used node recognition and attribute testing that when matched resulted in the associated action being performed. In addition like tree element could also be tested in an unparse rule. Unparse rules were also a recursive language being able to call unparse rules passing elements of thee tree before the action of the unparse rule
1302-651: The metacompiler EQGEN, from the PDP-l to the Beckman 420. EQGEN was a logic equation generating language. In 1964, System Development Corporation began a major effort in the development of metacompilers. This effort includes powerful metacompilers, Bookl, and Book2 written in Lisp which have extensive tree-searching and backup ability. An outgrowth of one of the Q-32 systems at SDC is Meta 5. The Meta 5 system incorporates backup of
TREE-META - Misplaced Pages Continue
1344-459: The original compiler-compiler was started by Tony Brooker and Derrick Morris in 1959, with initial testing beginning in March 1962. The Brooker Morris Compiler Compiler (BMCC) was used to create compilers for the new Atlas computer at the University of Manchester , for several languages: Mercury Autocode , Extended Mercury Autocode, Atlas Autocode , ALGOL 60 and ASA Fortran . At roughly
1386-561: The same time, related work was being done by E. T. (Ned) Irons at Princeton, and Alick Glennie at the Atomic Weapons Research Establishment at Aldermaston whose "Syntax Machine" paper (declassified in 1977) inspired the META series of translator writing systems mentioned below. The early history of metacompilers is closely tied with the history of SIG/PLAN Working group 1 on Syntax Driven Compilers. The group
1428-440: The semantics of the syntactic structure that is analyzed by the parser. Depending upon the type of parser that should be generated, these routines may construct a parse tree (or abstract syntax tree ), or generate executable code directly. One of the earliest (1964), surprisingly powerful, versions of compiler-compilers is META II , which accepted an analytical grammar with output facilities that produce stack machine code, and
1470-403: The solution of a problem a domain-specific language design. As a metacompiler's metalanguage will usually be a powerful string and symbol processing language, they often have strong applications for general-purpose applications, including generating a wide range of other software engineering and analysis tools. Besides being useful for domain-specific language development, a metacompiler
1512-405: The task of writing compilers by automating the aspects that are the same regardless of the object language. This makes possible the design of domain-specific languages which are appropriate to the specification of a particular problem. A metacompiler reduces the cost of producing translators for such domain-specific object languages to a point where it becomes economically feasible to include in
1554-621: Was developed at Stanford Research Institute in Menlo Park, California. April 1968. The early metacompiler history is well documented in the TREE META manual. TREE META paralleled some of the SDC developments. Unlike earlier metacompilers it separated the semantics processing from the syntax processing. The syntax rules contained tree building operations that combined recognized language elements with tree nodes. The tree structure representation of
1596-541: Was developed at Systems Development Corporation by Erwin Book, Dewey Val Schorre and Steven J. Sherman With the full power of (lisp 2) a list processing language optimizing algorithms could operate on syntax generated lists and trees before code generation. CWIC also had a symbol table built into the language. With the resurgence of domain-specific languages and the need for parser generators which are easy to use, easy to understand, and easy to maintain, metacompilers are becoming
1638-436: Was implemented and produced random algebraic expressions. Meta I the first metacompiler was implemented by Schorre on an IBM 1401 at UCLA in January 1963. His original interpreters and metamachines were written directly in a pseudo-machine language. META II , however, was written in a higher-level metalanguage able to describe its own compilation into the pseudo-machine language. Lee Schmidt at Bolt, Beranek, and Newman wrote
1680-478: Was performed. The concept of the metamachine originally put forth by Glennie is so simple that three hardware versions have been designed and one actually implemented. The latter at Washington University in St. Louis. This machine was built from macro-modular components and has for instructions the codes described by Schorre. CWIC (Compiler for Writing and Implementing Compilers) is the last known Schorre metacompiler. It
1722-620: Was ported to many systems including the UNIVAC 1108 , GE 645 , SDS 940 , ICL 1906A , PERQ , and UCSD p-System . This is a complete example of a TREE-META program extracted (and untested) from the more complete (declarations, conditionals, and blocks) example in Appendix 6 of the ICL 1900 TREE-META manual. That document also has a definition of TREE-META in TREE-META in Appendix 3. This program
TREE-META - Misplaced Pages Continue
1764-572: Was started primarily through the effort of Howard Metcalfe in the Los Angeles area. In the fall of 1962, Howard Metcalfe designed two compiler-writing interpreters. One used a bottom-to-top analysis technique based on a method described by Ledley and Wilson. The other used a top-to-bottom approach based on work by Glennie to generate random English sentences from a context-free grammar. At the same time, Val Schorre described two "meta machines", one generative and one analytic. The generative machine
#87912