path: root/miniany/doc/en.wikibooks.org_wiki_Compiler_Construction_Introduction.txt

   #[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&section=1
   9. https://en.wikibooks.org/w/index.php?title=Compiler_Construction/Introduction&action=edit&section=1
  10. https://en.wikipedia.org/wiki/Bootstrapping_(compilers)
  11. https://en.wikibooks.org/w/index.php?title=Compiler_Construction/Introduction&veaction=edit&section=2
  12. https://en.wikibooks.org/w/index.php?title=Compiler_Construction/Introduction&action=edit&section=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&section=3
  15. https://en.wikibooks.org/w/index.php?title=Compiler_Construction/Introduction&action=edit&section=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