#1
  1. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,648
    Rep Power
    4248

    How does an interpreter/compiler work?


    Everything you were afraid to ask about how a compiler/interpreter works.

    Let's start by discussing a very simple form of a compiler/interpreter:

    Source File ---> Scanner ---> Lexer ---> Parser ---> Interpreter/Code Generator

    So what do all the terms here mean. We'll work on that as we go:
    Source File: This is the program that is read by the compiler or interpreter. This is the text that needs to be compiled or interpreted.

    Scanner: This is the first module in a compiler or interpreter. Its job is to read the source file one character at a time. It can also keep track of which line number and character is currently being read. A typical scanner can be instructed to move backwards and forwards through the source file. Why do we need to move backwards? We will see why in just a little bit when we examine the lexer. For now, assume that each time the scanner is called, it returns the next character in the file.

    Lexer: This module serves to break up the source file into chunks (called tokens). It calls the scanner to get characters one at a time and organizes them into tokens and token types. For instance, if the source file read something like this:
    Code:
    cx = cy + 324;
    print "value of cx is ", cx;
    a lexer would perhaps break it like this:
    Code:
    cx  --> Identifier (variable)
    =  --> Symbol (assignment operator)
    cy  --> Identifier (variable)
    + --> Symbol (addition operator)
    324 --> Numeric constant (integer)
    ; --> Symbol (end of statement)
    print --> Identifier (keyword)
    "value of cx is " --> String constant
    , --> Symbol (string concatenation operator)
    cx --> Identifier (variable)
    ; --> Symbol (end of statement)
    Thus, the lexer calls the scanner to pass it one character at a time and groups them together and identifies them up as tokens for the language parser (which is the next stage). It also identifies the type of token (variable vs. keyword, assignment operator vs. addition operator vs. string concatenation operator etc.) Occasionally, the lexer has to tell the scanner to back up though. Consider a language that has operators that may be more than one character long (! vs. !=, < vs. <=, + vs. ++ etc.). Assume that the lexer has requested the scanner for a character and it has returned '<'. The lexer needs to determine whether the operator is a < or a <=. So it requests the scanner for another character. If the next character is a '=', it changes the token to '<=' and passes it to the parser. If not, it tells the scanner to back up one character and hold it in the buffer, while it passes the '<' to the parser.

    Parser: This is the part of the compiler that really understands the syntax of the language. It calls the lexer to get tokens and processes the tokens per the syntax of the language. For instance, taking the example from the lexer above, the hypothetical interaction between the lexer and parser could go like this:
    Code:
    Parser: Give me the next token
    Lexer: Next token is "cx" which is a variable.
    Parser: Ok, I have "cx" as a declared integer variable. Give me next token
    Lexer: Next token is "=", the assignment operator.
    Parser: Ok, the program wants me to assign something to "cx". Next token 
         Lexer: The next token is "cy" which is a variable.
         Parser: Ok, I know "cy" is an integer variable. Next token please
         Lexer: The next token is '+', which is an addition operator.
         Parser: Ok, so I need to add something to the value in "cy". Next token please.
             Lexer: The next token is "324", which is an integer.
             Parser: Ok, both "cy" and "324" are integers, so I can add them. Next token please:
             Lexer: The next token is ";" which is end of statement.
         Parser: Ok, I will evaluate "cy + 324" and get the answer
    Parser: I'll take the answer from "cy + 324" and assign it to "cx"
    In the above, the indenting shows a subprocess that the parser enters, to evaluate "cy + 324". This gives you a decent idea about how the parser operates. Also note that the parser is checking types and syntax rules (for instance, it checked whether cy and 324 were both integer types before adding them). If the parser gets a token that it was not expecting, it will stop processing and complain to the user about an error. The Scanner holds the current line number and character, so the Parser can inform the user approximately where the error occurred.

    Interpreter/Code Generator: This is the part that actually takes the action that is specified by a program statement. In some cases, this is actually part of the parser (especially for interpreters) and the parser interprets and takes action directly. In other cases, the parser converts the statements into byte-code (intermediate language). In case of a compiler, it then hands them to the Code Generator to convert into machine code instructions. If you want a compiler for a different CPU or architecture, all you have to do is put a new code generator unit to translate the byte code into machine code for the new CPU.

    This is about the simplest form for an interpreter or compiler. In the next few threads, we will look in some more detail at the interaction between the Parser and Code Generator.

    Feedback about this post will be greatly appreciated.

    Comments on this post

    • SimonGreenhill agrees : informative
    • medialint agrees
    • netytan agrees : Awesum Scorpi
    • jafet agrees : Good article
    • JhonnyO@gmail.c agrees
    • crownjewel82 agrees : My compiler construction professor would be proud.
    • LinuxPenguin agrees : Amazing
    • Brokenhope agrees : Thank you. I have always been curious how a compiler worked.
    Last edited by Scorpions4ever; December 16th, 2005 at 07:52 PM.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  2. #2
  3. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2008
    Posts
    2
    Rep Power
    0
    Thanks you!
    Have you source?

    Comments on this post

    • MrFujin disagrees : can you think? sorry, but answering a 3 years old post with a question that cant be answered is not that great (source in what!?)
    • FenderStrat agrees
  4. #3
  5. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,648
    Rep Power
    4248
    Actually I do have source code . People are using it as well.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  6. #4
  7. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,648
    Rep Power
    4248
    What do you need it for? Just curious?
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2008
    Posts
    2
    Rep Power
    0
    I learn compiler.I'm programming Scanner, but I have problem!
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2009
    Posts
    337
    Rep Power
    46
    Hey, I'm writing a small interpreter(inspired by High Order Calculator by Kernighan & Rob Pike) using yacc and hand-written lexical analyser. Currently I'm using function pointers as like in HOC.
    which would be better switch/function pointer ?
    Where should I store my function parameters? because for recursive call with formal parameters I need to restore parameters. What's the most efficient way?
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2010
    Posts
    1
    Rep Power
    0

    Target code generator


    Hi can someone help me with source code for a target code generator. Its for my assignment due friday
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    2
    Rep Power
    0

    continuaing threads?


    ...In the next few threads, we will look in some more detail at the interaction between the Parser and Code Generator.

    Feedback about this post will be greatly appreciated.
    This got linked on the Facebook.ILoveC++ group. I would love to see the rest of the threads. Could you post a link to the next one in a reply? Thanks.
  16. #9
  17. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,648
    Rep Power
    4248
    Thank you for reminding me about this. I did start writing some tutorial code in a variety of languages, to demonstrate that it is possible to write a little interpreter using the principles above. I was thinking of posting that code in a blog format. Actually, I already did write a couple of interpreters already, one of which may be familiar to old time readers of this forum .

    By the way, would you mind posting the URL to the facebook group please.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  18. #10
  19. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    2
    Rep Power
    0

    I Love C++ Facebook group URL


    Sorry, can't do URLs yet. But if you go to Facebook, you should be able to search for "I Love C++".

    There are more than a few "I Love (C, C#, C++,, Java, PHP, etc.)" groups now. It's nice to see.

    ERandall
  20. #11
  21. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,648
    Rep Power
    4248
    Tried searching for it, but I ended up with a bazillion different other groups that have nothing to do with programming (though I found "I love C#" and "I love C Plus Plus"). Please post a link here without http:// and add spacing to the URL between the periods, so that the forum software doesn't block the URL. Thanks in advance
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  22. #12
  23. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2013
    Posts
    1
    Rep Power
    0
    Originally Posted by Scorpions4ever
    Actually I do have source code . People are using it as well.
    For the compiling part? I'd love to take a look at it if you're willing! There's so much online about the first few stages but I can't find any good information on the actual COMPILING part besides reading the entire dragon book...

    Anyhow, thanks for the info!
  24. #13
  25. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,648
    Rep Power
    4248
    Actually it is an interpreter, not a compiler. If you're still interested, let me know and I'll PM you a link.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  26. #14
  27. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2014
    Location
    Seoul, South Korea
    Posts
    5
    Rep Power
    0
    Hi All of guys,

    I've been trying to make a plan making New code.

    I can't imangine of how make it in big picture.

    Can you guys recommend me about the book related?

    CHEERS,
    Patrick.

IMN logo majestic logo threadwatch logo seochat tools logo