Meta(ID:3933/met003)Syntax-directed compilerVal Schorre Syntax-directed compiler Used Chomskian grammars to lay out the basic syntax. Related languages
References: The META SYSTEMS (Schorre, [Schor 64], Schneider and Johnson [Seh 64]) The META systems are the product of the Los Angeles SIGPLAN working group on syntax-directed compilers. Although the original work was diversified, the current systems are generally based on a model known as META-II, developed by Sehorre [Schor 64]. Within this model the parsing and translation processes for a language are all stated in a set of BNF-like rules. These rules become reeursive recognizers with embedded code generators when implemented. The rules do not allow left reeursion, using instead the prefix iteration operator $. Terminal symbols are quoted; system symbols are preceded by "."; and all unmarked symbols are user's nonterminals. Parentheses are used to group alternates within right parts. The following rules are used in translating Boolean expressions: 1. UNION = INTER ('OR' .OUT('BT' *1) UNION .LABEL *I].EMPTY) ; 2. INTER = BPRIMARY ('AND' .OUT('BF' *1) INTER .LABEL "1 I .EMPTY) ; 3. BPRIMARY = .ID .OUT('LD' *) I '('UNION')'; The last rule defines a procedure for recognizing a Boolean primary in an algebraic language. The word BPRIMAR Y followed by "=" defines the name of the rule, while the right part of the rule is both an algorithm for testing an input stream for the occurrence of a union and a code generator in ease an identifier (.ID) is found. The above rules contain examples of the three basic entities used in most META compilers. The mention of the name of another rule, in this ease UNION, causes a reeursive call on that recognizer to be invoked. The occurrence of a literal string "(" states that the input stream is to be tested for a left duces a line of text, where "*" always refers to the last item recognized by the primitive nonterminal .ID. The first mention of a *1 within a rule (as in Rule 1 above) causes both the generation of a label and the output of that label. Subsequent references within the same rule output the same label. That is, when a rule is entered new labels may be generated. These labels exist only while the rule is active. If a call is made to another rule, the labels are pushed onto a stack. Upon return from the called rule, the previous labels are restored. The action .LABEL *1 indicates that the label corresponding to *1 is to be written out..EMPTY is a primitive nonterminal which has no effect on the input but is always satisfied or true. For the input stream "(A OR B) AND (C OR D)" the following code would be produced where LD, BT, BF are mnemonics for Load, Branch True, and Branch False respectively. LD A BT L1 LD B L1 BF L2 LD C BT L3 LD D L3 L2 The usefulness of META-II was severely limited by the lack of facilities for backup or for reordering the output. There have been several attempts to extend the META techniques to a complete TWS. META-3 [Schor 64] was an attempt to extend the basic META-II concept so that ALGOI, 60 could be compiled for a 7090. It added some ability for semantic tests and register manipulation, but the additions never proved adequate. META-5 has been used in a number of format conversion and source-tosource language translations, but has not been used for compilers. The most recent development is TREE META, a multipass system using complex processing of intermediate syntax trees. The slowness and inefficiency of META compilers is recognized by their authors, but the ease of implementation, the boot-strapping capabilities, and the large class of languages they can handle are used to justify the work that has gone into their development. Abstract: A critical review of recent efforts to automate the writing of translators of programming languages is presented. The formal study of syntax and its application to translator writing are discussed in Section II. Various approaches to automating the postsyntactic (semantic) aspects of translator writing are discussed in Section III, and several related topics in Section IV. in [ACM] CACM 11(02) (February 1968) view details in Computers & Automation 21(6B), 30 Aug 1972 view details The exact number of all the programming languages still in use, and those which are no longer used, is unknown. Zemanek calls the abundance of programming languages and their many dialects a "language Babel". When a new programming language is developed, only its name is known at first and it takes a while before publications about it appear. For some languages, the only relevant literature stays inside the individual companies; some are reported on in papers and magazines; and only a few, such as ALGOL, BASIC, COBOL, FORTRAN, and PL/1, become known to a wider public through various text- and handbooks. The situation surrounding the application of these languages in many computer centers is a similar one. There are differing opinions on the concept "programming languages". What is called a programming language by some may be termed a program, a processor, or a generator by others. Since there are no sharp borderlines in the field of programming languages, works were considered here which deal with machine languages, assemblers, autocoders, syntax and compilers, processors and generators, as well as with general higher programming languages. The bibliography contains some 2,700 titles of books, magazines and essays for around 300 programming languages. However, as shown by the "Overview of Existing Programming Languages", there are more than 300 such languages. The "Overview" lists a total of 676 programming languages, but this is certainly incomplete. One author ' has already announced the "next 700 programming languages"; it is to be hoped the many users may be spared such a great variety for reasons of compatibility. The graphic representations (illustrations 1 & 2) show the development and proportion of the most widely-used programming languages, as measured by the number of publications listed here and by the number of computer manufacturers and software firms who have implemented the language in question. The illustrations show FORTRAN to be in the lead at the present time. PL/1 is advancing rapidly, although PL/1 compilers are not yet seen very often outside of IBM. Some experts believe PL/1 will replace even the widely-used languages such as FORTRAN, COBOL, and ALGOL.4) If this does occur, it will surely take some time - as shown by the chronological diagram (illustration 2) . It would be desirable from the user's point of view to reduce this language confusion down to the most advantageous languages. Those languages still maintained should incorporate the special facets and advantages of the otherwise superfluous languages. Obviously such demands are not in the interests of computer production firms, especially when one considers that a FORTRAN program can be executed on nearly all third-generation computers. The titles in this bibliography are organized alphabetically according to programming language, and within a language chronologically and again alphabetically within a given year. Preceding the first programming language in the alphabet, literature is listed on several languages, as are general papers on programming languages and on the theory of formal languages (AAA). As far as possible, the most of titles are based on autopsy. However, the bibliographical description of sone titles will not satisfy bibliography-documentation demands, since they are based on inaccurate information in various sources. Translation titles whose original titles could not be found through bibliographical research were not included. ' In view of the fact that nany libraries do not have the quoted papers, all magazine essays should have been listed with the volume, the year, issue number and the complete number of pages (e.g. pp. 721-783), so that interlibrary loans could take place with fast reader service. Unfortunately, these data were not always found. It is hoped that this bibliography will help the electronic data processing expert, and those who wish to select the appropriate programming language from the many available, to find a way through the language Babel. We wish to offer special thanks to Mr. Klaus G. Saur and the staff of Verlag Dokumentation for their publishing work. Graz / Austria, May, 1973 in Computers & Automation 21(6B), 30 Aug 1972 view details |