diff options
Diffstat (limited to 'miniany/doc/en.wikibooks.org_wiki_Compiler_Construction_Introduction.txt')
| -rw-r--r-- | miniany/doc/en.wikibooks.org_wiki_Compiler_Construction_Introduction.txt | 382 |
1 files changed, 382 insertions, 0 deletions
diff --git a/miniany/doc/en.wikibooks.org_wiki_Compiler_Construction_Introduction.txt b/miniany/doc/en.wikibooks.org_wiki_Compiler_Construction_Introduction.txt new file mode 100644 index 0000000..195b011 --- /dev/null +++ b/miniany/doc/en.wikibooks.org_wiki_Compiler_Construction_Introduction.txt @@ -0,0 +1,382 @@ + #[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 |