#[1]alternate [2]Edit [3]Wikibooks (en) [4]Wikibooks Atom feed Compiler Construction/Introduction From Wikibooks, open books for an open world < [5]Compiler Construction [6]Jump to navigation [7]Jump to search Introducing Compilers and Interpreters[[8]edit | [9]edit source] A compiler is a computer program that implements a programming language specification to "translate" programs, usually as a set of files which constitute the source code written in source language, into their equivalent machine readable instructions (the target language, often having a binary form known as object code). This translation process is called compilation. We compile the source program to create the compiled program. The compiled program can then be run (or executed) to do what was specified in the original source program. The source language is always a higher-level language in comparison to machine code, written using some mixture of English words and mathematical notation, assembly language being the lowest compilable language (an assembler being a special case of a compiler that translates assembly language into machine code). Higher-level languages are the most complex to support in a compiler/interpreter, not only because they increase the level of abstraction between the source code and the resulting machine code, but because increased complexity is required to formalize those abstract structures. The target language is normally a low-level language such as assembly, written with somewhat cryptic abbreviations for machine instructions, in these cases it will also run an assembler to generate the final machine code. But some compilers can directly generate machine code for some actual or virtual computer e.g. byte-code for the Java Virtual Machine. Another common approach to the resulting compilation effort is to target a virtual machine. That will do just-in-time compilation and byte-code interpretation and blur the traditional categorizations of compilers and interpreters. For example, C and C++ will generally be compiled for a target `architecture'. The draw-back is that because there are many types of processor there will need to be as many distinct compilations. In contrast Java will target a Java Virtual Machine, which is an independent layer above the 'architecture'. The difference is that the generated byte-code, not true machine code, brings the possibility of portability, but will need a Java Virtual Machine (the byte-code interpreter) for each platform. The extra overhead of this byte-code interpreter means slower execution speed. An interpreter is a computer program which executes the translation of the source program at run-time. It will not generate independent executable programs nor object libraries ready to be included in other programs. A program which does a lot of calculation or internal data manipulation will generally run faster in compiled form than when interpreted. But a program which does a lot of input/output and very little calculation or data manipulation may well run at about the same speed in either case. Being themselves computer programs, both compilers and interpreters must be written in some implementation language. Up until the early 1970's, most compilers were written in assembly language for some particular type of computer. The advent of C and Pascal compilers, each written in their own source language, led to the more general use of high-level languages for writing compilers. Today, operating systems will provide at least a free C compiler to the user and some will even include it as part of the OS distribution. Compiler construction is normally considered as an advanced rather than a novice programming task, mainly due to the quantity of code needed (and the difficulties of grokking this amount of code) rather than the difficulty of any particular coding constructs. To this most books about compilers have some blame. The large gap between production compilers and educational exercises promotes this defeatist view. For the first version of a compiler written in its own source language you have a [10]bootstrapping problem. Once you get a simple version working, you can then use it to improve itself. Note: A compiler is a non-trivial computer program; when written completely by hand a non-optimizing compiler for a simple source language is likely to be upwards of 3000 lines long. Some compiler-writing tools are available which can reduce this size, but will add the corresponding dependencies. The compilation process At the highest level, compilation is broken into a number of parts: 1. Lexical analysis (tokenizing) 2. Syntax analysis (parsing) 3. Type checking 4. Code generation Note: You should read most of this chapter, since the rest of the book will assume it as background information. Requirements[[11]edit | [12]edit source] Any compiler has some essential requirements, which are perhaps more stringent than for most programs: * Any valid program must be translated correctly, i.e. no incorrect translation is allowed. * Any invalid program must be rejected and not translated. There will inevitably be some valid programs which can't be translated due to their size or complexity in relation to the hardware available, for example problems due to memory size. The compiler may also have some fixed-size tables which place limits on what can be compiled (some language definitions place explicit lower bounds on the sizes of certain tables, to ensure that programs of reasonable size/complexity can be compiled). There are also some desirable requirements, some of which may be mutually exclusive: * Errors should be reported in terms of the source language or program. * The position at which an error was detected should be indicated; if the actual error probably occurred somewhat earlier then some indication of possible cause(s) should also be provided. * Compilation should be fast. * The translated program should be fast. * The translated program should be small. * If the source language has some national or international standard: + Ideally the entire standard should be implemented. + Any restrictions or limits should be well and clearly documented. + If extensions to the standard have been implemented: o These extensions should be documented as such. o There should be some way of turning these extensions off. There are also some possibly controversial requirements to consider (see chapter on [13]dealing with errors): * Errors detected when the translated program is running should still be reported in relation to the original source program e.g. line number. * Errors detected when the translated program is running should include division by 0, running out of memory, use of an array subscript/index which is too big or too small, attempted use of an undefined variable, incorrect use of pointers, etc. Overall Structure[[14]edit | [15]edit source] For ease of exposition we will divide the compiler into a front end and a back end. These need not even be written in the same implementation language, providing they can communicate effectively via some intermediate representation. The following list itemizes the tasks carried out by the front end and the back end. Note that the tasks are not carried out in any particular order, as outlined below, and discussed in more detail in subsequent chapters. * Front end + lexical analysis - convert characters to tokens + syntax analysis - check for valid sequence of tokens + semantic analysis - check for meaning + some global/high-level optimization * Back end + some local optimization + register allocation + peep-hole optimization + code generation + instruction scheduling Almost all the source-language aspects are handled by the front end. It is possible to have different front ends for different high-level languages, and a common back end which does most of the optimization. Almost all the machine-dependent aspects are handled by the back end. It is possible to have different back ends for different computers so that the compiler can produce code for different computers. The front end is normally controlled by the syntax analysis processing. As necessary, the syntax analysis code will call a routine which performs some lexical analysis and returns the next token. At selected points during syntax analysis, appropriate semantic routines are called which perform any relevant semantic checks and/or add information to the internal representation. [16]Next - Describing a Programming Language Retrieved from "[17]https://en.wikibooks.org/w/index.php?title=Compiler_Construction/I ntroduction&oldid=3357979" [18]Category: * [19]Book:Compiler Construction Navigation menu Personal tools * Not logged in * [20]Discussion for this IP address * [21]Contributions * [22]Create account * [23]Log in Namespaces * [24]Book * [25]Discussion [ ] English Views * [26]Read * [27]Edit * [28]Edit source * [29]View history [ ] More Search ____________________ Search Go Navigation * [30]Main Page * [31]Help * [32]Browse * [33]Cookbook * [34]Wikijunior * [35]Featured books * [36]Recent changes * [37]Donations * [38]Random book * [39]Using Wikibooks Community * [40]Reading room forum * [41]Community portal * [42]Bulletin Board * [43]Help out! * [44]Policies and guidelines * [45]Contact us Tools * [46]What links here * [47]Related changes * [48]Upload file * [49]Special pages * [50]Permanent link * [51]Page information * [52]Cite this page * [53]Get shortened URL Sister projects * [54]Wikipedia * [55]Wikiversity * [56]Wiktionary * [57]Wikiquote * [58]Wikisource * [59]Wikinews * [60]Wikivoyage * [61]Commons * [62]Wikidata * [63]MediaWiki * [64]Meta-Wiki Print/export * [65]Create a collection * [66]Download as PDF * [67]Printable version In other languages [68]Add links * This page was last edited on 5 January 2018, at 20:05. * Text is available under the [69]Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the [70]Terms of Use and [71]Privacy Policy. * [72]Privacy policy * [73]About Wikibooks * [74]Disclaimers * [75]Code of Conduct * [76]Developers * [77]Statistics * [78]Cookie statement * [79]Mobile view * [80]Wikimedia Foundation * [81]Powered by MediaWiki References Visible links: 1. https://en.m.wikibooks.org/wiki/Compiler_Construction/Introduction 2. https://en.wikibooks.org/w/index.php?title=Compiler_Construction/Introduction&action=edit 3. https://en.wikibooks.org/w/opensearch_desc.php 4. https://en.wikibooks.org/w/index.php?title=Special:RecentChanges&feed=atom 5. https://en.wikibooks.org/wiki/Compiler_Construction 6. https://en.wikibooks.org/wiki/Compiler_Construction/Introduction#mw-head 7. https://en.wikibooks.org/wiki/Compiler_Construction/Introduction#searchInput 8. https://en.wikibooks.org/w/index.php?title=Compiler_Construction/Introduction&veaction=edit§ion=1 9. https://en.wikibooks.org/w/index.php?title=Compiler_Construction/Introduction&action=edit§ion=1 10. https://en.wikipedia.org/wiki/Bootstrapping_(compilers) 11. https://en.wikibooks.org/w/index.php?title=Compiler_Construction/Introduction&veaction=edit§ion=2 12. https://en.wikibooks.org/w/index.php?title=Compiler_Construction/Introduction&action=edit§ion=2 13. https://en.wikibooks.org/wiki/Compiler_Construction/Dealing_with_errors 14. https://en.wikibooks.org/w/index.php?title=Compiler_Construction/Introduction&veaction=edit§ion=3 15. https://en.wikibooks.org/w/index.php?title=Compiler_Construction/Introduction&action=edit§ion=3 16. https://en.wikibooks.org/wiki/Compiler_Construction/Describing_a_Programming_Language 17. https://en.wikibooks.org/w/index.php?title=Compiler_Construction/Introduction&oldid=3357979 18. https://en.wikibooks.org/wiki/Special:Categories 19. https://en.wikibooks.org/wiki/Category:Book:Compiler_Construction 20. https://en.wikibooks.org/wiki/Special:MyTalk 21. https://en.wikibooks.org/wiki/Special:MyContributions 22. https://en.wikibooks.org/w/index.php?title=Special:CreateAccount&returnto=Compiler+Construction%2FIntroduction 23. https://en.wikibooks.org/w/index.php?title=Special:UserLogin&returnto=Compiler+Construction%2FIntroduction 24. https://en.wikibooks.org/wiki/Compiler_Construction/Introduction 25. https://en.wikibooks.org/wiki/Talk:Compiler_Construction/Introduction 26. https://en.wikibooks.org/wiki/Compiler_Construction/Introduction 27. https://en.wikibooks.org/w/index.php?title=Compiler_Construction/Introduction&veaction=edit 28. https://en.wikibooks.org/w/index.php?title=Compiler_Construction/Introduction&action=edit 29. https://en.wikibooks.org/w/index.php?title=Compiler_Construction/Introduction&action=history 30. https://en.wikibooks.org/wiki/Main_Page 31. https://en.wikibooks.org/wiki/Help:Contents 32. https://en.wikibooks.org/wiki/Wikibooks:Card_Catalog_Office 33. https://en.wikibooks.org/wiki/Cookbook:Table_of_Contents 34. https://en.wikibooks.org/wiki/Wikijunior 35. https://en.wikibooks.org/wiki/Wikibooks:Featured_books 36. https://en.wikibooks.org/wiki/Special:RecentChanges 37. https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikibooks.org&uselang=en 38. https://en.wikibooks.org/wiki/Special:RandomInCategory/Book:Wikibooks_Stacks/Books 39. https://en.wikibooks.org/wiki/Using_Wikibooks 40. https://en.wikibooks.org/wiki/Wikibooks:Reading_room 41. https://en.wikibooks.org/wiki/Wikibooks:Community_Portal 42. https://en.wikibooks.org/wiki/Wikibooks:Reading_room/Bulletin_Board 43. https://en.wikibooks.org/wiki/Wikibooks:Maintenance 44. https://en.wikibooks.org/wiki/Wikibooks:Policies_and_guidelines 45. https://en.wikibooks.org/wiki/Wikibooks:Contact_us 46. https://en.wikibooks.org/wiki/Special:WhatLinksHere/Compiler_Construction/Introduction 47. https://en.wikibooks.org/wiki/Special:RecentChangesLinked/Compiler_Construction/Introduction 48. https://commons.wikimedia.org/wiki/Special:UploadWizard?uselang=en 49. https://en.wikibooks.org/wiki/Special:SpecialPages 50. https://en.wikibooks.org/w/index.php?title=Compiler_Construction/Introduction&oldid=3357979 51. https://en.wikibooks.org/w/index.php?title=Compiler_Construction/Introduction&action=info 52. https://en.wikibooks.org/w/index.php?title=Special:CiteThisPage&page=Compiler_Construction%2FIntroduction&id=3357979&wpFormIdentifier=titleform 53. https://en.wikibooks.org/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikibooks.org%2Fwiki%2FCompiler_Construction%2FIntroduction 54. https://en.wikipedia.org/wiki/Main_Page 55. https://en.wikiversity.org/wiki/Wikiversity:Main_Page 56. https://en.wiktionary.org/wiki/Wiktionary:Main_Page 57. https://en.wikiquote.org/wiki/Main_Page 58. https://en.wikisource.org/wiki/Main_Page 59. https://en.wikinews.org/wiki/Main_Page 60. https://en.wikivoyage.org/wiki/Main_Page 61. https://commons.wikimedia.org/wiki/Main_Page 62. https://www.wikidata.org/wiki/Wikidata:Main_Page 63. https://www.mediawiki.org/wiki/Main_Page 64. https://meta.wikimedia.org/wiki/Main_Page 65. https://en.wikibooks.org/w/index.php?title=Special:Book&bookcmd=book_creator&referer=Compiler+Construction%2FIntroduction 66. https://en.wikibooks.org/w/index.php?title=Special:DownloadAsPdf&page=Compiler_Construction%2FIntroduction&action=show-download-screen 67. https://en.wikibooks.org/w/index.php?title=Compiler_Construction/Introduction&printable=yes 68. https://www.wikidata.org/wiki/Special:NewItem?site=enwikibooks&page=Compiler+Construction%2FIntroduction 69. https://creativecommons.org/licenses/by-sa/4.0/ 70. https://foundation.wikimedia.org/wiki/Terms_of_Use 71. https://foundation.wikimedia.org/wiki/Privacy_policy 72. https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy 73. https://en.wikibooks.org/wiki/Wikibooks:Welcome 74. https://en.wikibooks.org/wiki/Wikibooks:General_disclaimer 75. https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct 76. https://developer.wikimedia.org/ 77. https://stats.wikimedia.org/#/en.wikibooks.org 78. https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement 79. https://en.m.wikibooks.org/w/index.php?title=Compiler_Construction/Introduction&mobileaction=toggle_view_mobile 80. https://wikimediafoundation.org/ 81. https://www.mediawiki.org/ Hidden links: 83. https://en.wikibooks.org/wiki/Main_Page