Language ProcessorsCOMS W4115Prof. Stephen A. EdwardsSpring 2007Columbia UniversityDepartment of Computer ScienceInterpreterSource ProgramInput Interpreter OutputCompilerSource ProgramCompilerInput Executable Program OutputBytecode InterpreterSource ProgramCompilerBytecodeInput Bytecode Interpreter OutputJust-in-time CompilerSource ProgramCompilerBytecodeInputJust-in-time CompilerMachine CodeOutputLanguage Speeds ComparedLanguage Impl.C gccOcaml ocamlSML mltonC++ g++SML smlnjCommon Lisp cmuclScheme biglooOcaml ocamlbJava javaPike pikeForth gforthLua luaPython pythonPerl perlRuby rubyEiffel seMercury mercuryAwk mawkHaskell ghcLisp repIcon iconTcl tclJavascript njsScheme guileForth bigforthErlang erlangAwk gawkEmacs Lisp xemacsScheme stalinPHP phpBash bashbytecodes native code JIT Threaded codehttp://www.bagley.org/˜doug/shootout/Separate Compilationfoo — An Executablefoo.oLinker ld:foo.sAssembler as:foo.cC compiler cc:bar.obar.sbar.c· · · libc.aprintf.o fopen.o malloc.o · · ·Archiver ar:Preprocessor“Massages” the input before the compiler sees it.•Macro expansion•File inclusion•Conditional compilationThe C Preprocessor#include <stdio.h>#define min(x, y) \((x)<(y))?(x):(y)#ifdef DEFINE_BAZint baz();#endifvoid foo(){int a = 1;int b = 2;int c;c = min(a,b);}cc -E example.c givesextern intprintf(char*,...);... many more declarationsfrom stdio.hvoid foo(){int a = 1;int b = 2;int c;c = ((a)<(b))?(a):(b);}Compiling a Simple Programint gcd(int a, int b){while (a != b) {if (a > b) a -= b;else b -= a;}return a;}What the Compiler Seesint gcd(int a, int b){while (a != b) {if (a > b) a -= b;else b -= a;}return a;}i n t sp g c d ( i n t sp a , sp in t sp b ) nl { nl sp sp w h i l e sp( a sp ! = sp b ) sp { nl sp sp sp sp if sp ( a sp > sp b ) sp a sp - = sp b; nl sp sp sp sp e l s e sp b sp - = spa ; nl sp sp } nl sp sp r e t u r n spa ; nl } nlText file is a sequence of charactersLexical Analysis Gives Tokensint gcd(int a, int b){while (a != b) {if (a > b) a -= b;else b -= a;}return a;}int gcd ( int a , int b ) {while ( a != b ) { if ( a> b ) a -= b ; else b -= a; } return a ; }A stream of tokens. Whitespace, comments removed.Parsing Gives an ASTfuncint gcd argsargint aargint bseqwhile!=a bif>a b-=a b-=b areturnaint gcd(int a, int b){while (a != b) {if (a > b) a -= b;else b -= a;}return a;}Abstract syntax tree built from parsing rules.Semantic Analysis ResolvesSymbolsSymbolTable:int aint bfuncint gcd argsargint aargint bseqwhile!=a bif>a b-=a b-=b areturnaTypes checked; references to symbols resolvedTranslation into 3-Address CodeL0: sne $1, a, bseq $0, $1, 0btrue $0, L1 % while (a != b)sl $3, b, aseq $2, $3, 0btrue $2, L4 % if (a < b)sub a, a, b % a -= bjmp L5L4: sub b, b, a % b -= aL5: jmp L0L1: ret aint gcd(int a, int b){while (a != b) {if (a > b) a -= b;else b -= a;}return a;}Idealized assembly language w/ infinite registersGeneration of 80386 Assemblygcd: pushl %ebp % Save FPmovl %esp,%ebpmovl 8(%ebp),%eax % Load a from stackmovl 12(%ebp),%edx % Load b from stack.L8: cmpl %edx,%eaxje .L3 % while (a != b)jle .L5 % if (a < b)subl %edx,%eax % a -= bjmp .L8.L5: subl %eax,%edx % b -= ajmp .L8.L3: leave % Restore SP,
View Full Document
Unlocking...