Transcript Chapter 2 - lillie

Chapter 2
Language Processors


Fall 2013
 Translators
and Compilers
 Interpreters
 Real and Abstract Machines
 Interpretive Compilers
 Portable Compilers
 Bootstrapping
 Case Study: The Triangle Language
Processor
Chart 2

Translator: a program that accepts any text expressed in
one language (the translator’s source language), and
generates a semantically-equivalent text expressed in
another language (its target language)
o Chinese-into-English
o Java-into-C
o Java-into-x86
o X86 assembler
Chart 3

Assembler: translates from an assembly language into the
corresponding machine code
o Generates one machine code instruction per source instruction

Compiler: translates from a high-level language into a lowlevel language
o Generates several machine-code instructions per source command.
Chart 4


Disassembler: translates a machine code into the
corresponding assembly language
Decompiler: translates a low-level language into a high-level
language
Question: Why would you want a disassembler or decompiler?
Chart 5


Source Program: the source language text
Object Program: the target language text
Compiler
Source
Program
Syntax Check
Context Constraints
Generate Object Code
Object
Program
Semantic Analysis
Chart 6
• Object program semantically equivalent to source program
 If source program is well-formed

Why would you want to do:
o Java-into-C translator
o C-into-Java translator
o Assembly-language-into-Pascal decompiler
Chart 7
P
L
P = Program Name
L = Implementation Language
M
M = Target Machine
P
L
For this to work, L must equal M, that
is, the implementation language must be
the same as the machine language
M
S
T
L
Chart 8
S-into-T Translator is
itself a program that
runs on machine L
S = Source Language
T = Target Language
L = Translator’s Implementation Language
P
S
S
T
P
T
M
M
•
•
•
•
Chart 9
Translating a source program P
Expressed in language T,
Using an S-into-T translator
Running on machine M
sort
sort
Java Java x86 x86
x86
x86
•
•
•
•
Translating a source program sort
Expressed in language Java,
Using a Java-into-x86 translator
Running on an x86 machine
The object program is running on
the same machine as the compiler
Chart 10
sort
x86
x86
sort
sort
Java Java PPC PPC
x86
download
sort
PPC
PPC
x86
•
•
•
•
•
Translating a source program sort
Expressed in language Java,
Using a Java-into-PPC translator
Running on an x86 machine
Downloaded to a PPC machine
Cross Compiler: The object program is running
on a different machine than the compiler
Chart 11
sort
Java Java
x86
x86
•
•
•
•
C
sort
C
sort
x86 x86
C
x86
x86
x86
Translating a source program sort
Expressed in language Java,
Using a Java-into-C translator
Running on an x86 machine
•
•
•
•
Then translating the C program
Using an C-into x86 compiler
Running on an x86 machine
Into x86 object program
Two-stage Compiler: The source program is
translated to another language before being
translated into the object program
Chart 12
sort
x86

Translator Rules
o Can run on machine M only if it is expressed in machine code M
o Source program must be expressed in translator’s source language
S
o Object program is expressed in the translator’s target language T
o Object program is semantically equivalent to the source program
Chart 13

Accepts any program (source program) expressed in a
particular language (source language) and runs that source
program immediately
o Does not translate the source program into object code prior to
execution
Chart 14
Interpreter
Source
Program
Fetch Instruction
Analyze Instruction
Execute Instruction
• Source program starts to run as soon
as the first instruction is analyzed
Chart 15
Program
Complete

When to Use Interpretation
o Interactive mode – want to see results of instruction before entering
next instruction
o Only use program once
o Each instruction expected to be executed only once
o Instructions have simple formats

Disadvantages
o Slow: up to 100 times slower than in machine code
Chart 16

Examples
o Basic
o Lisp
o Unix Command Language (shell)
o SQL
Chart 17
S
L
P
S
S
M
M
graph
Basic
Basic
x86
x86
Chart 18
S interpreter expressed in language L
Program P expressed in
language S, using
Interpreter S, running on
machine M
Program graph written in
Basic running on a Basic
interpreter executed on an
x86 machine

Hardware emulation: Using software to execute one set of
machine code on another machine
o Can measure everything about the new machine except its speed
o Abstract machine: emulator
o Real machine: actual hardware
An abstract machine is functionally equivalent to a real
machine if they both implement the same language L
Chart 19
New Machine Instruction
(nmi) interpreter written in C
nmi
C
nmi interpreter written in C
nmi
C
nmi
M M
C
M
nmi interpreter expressed in
machine code M
The nmi interpreter is translated
into machine code M using the
C compiler
M
Compiler to translate C
program into M machine code
P
nmi
nmi
M
M
Chart 20
P
nmi
nmi

Combination of compiler and interpreter
o Translate source program into an intermediate language
o It is intermediate in level between the source language and ordinary
machine code
o Its instructions have simple formats, and therefore can be analyzed
easily and quickly
o Translation from the source language into the intermediate language
is easy and fast
An interpretive compiler combines fast
compilation with tolerable running speed
Chart 21
Java
JVM
M
JVM code interpreter
running on machine M
JVM
M
P
Java
Java into JVM translator
running on machine M
Java
JVM
M
M
P
JVM
P
JVM
JVM
M
M
A Java program P is first translated into JVM-code,
and then the JVM-code object program is interpreted
Chart 22

A program is portable if it can be compiled and run on any
machine, without change
o A portable program is more valuable than an unportable one,
because its development cost can be spread over more copies
o Portability is measured by the proportion of code that remains
unchanged when it is moved to a dissimilar machine
• Language affects portability
• Assembly language: 0% portable
• High level language: approaches 100% portability
Chart 23

Language Processors
o Valuable and widely used programs
o Typically written in high-level language
• Pascal, C, Java
o Part of language processor is machine dependent
• Code generation part
• Language processor is only about 50% portable
o Compiler that generates intermediate code is more portable than a
compiler that generates machine code
Chart 24
1. Start with the
following
Java
JVM
Java
JVM
C
JVM
C
C
M
JVM
JVM
Java
JVM
2. Rewrite interpreter in C
JVM
M
P
Java
Java
JVM
M
JVM
M
JVM
M
3. Compile the compiler
Chart 25
Java
M
Note: C M Compiler exists; rewrite
JVM interpreter from Java to C
P
JVM
P
JVM
JVM
M
M
4. Java program P is translated into
JVM program P and run using ghe
JVM intrepreter

The language processor is used to process itself
o Implementation language is the source language

Bootstrapping a portable compiler
o A portable compiler can be bootstrapped to make a true compiler –
one that generates machine code – by writing an intermediatelanguage-into-machine-code translator

Full bootstrap
o Writing the compiler in itself
o Using the latest version to upgrade the next version

Half bootstrap
o Compiler expressed in itself but targeted for another machine

Bootstrapping to improve efficiency
o Upgrade the compiler to optimize code generation as well as to
improve compile efficiency
Chart 26
Bootstrap an interpretive compiler to generate machine code
JVM
M
JVM
JVM
M
Java Java
Java
JVM
JVM JVM
JVM
1, First, write a
JVM-coded-intoM translator in
Java
M
JVM
M
JVM
M
JVM JVM
JVM
2. Next, compile
translator using
existing interpreter
JVM
M
M
Java
Java
JVM
JVM JVM
M
M
M
Chart 27
JVM
M
4. Translate Javainto-JVM-code
translator into
machine code
P
Java
M
M
3. Use
translator to
translate
itself
M
Java
JVM
M
M
P
JVM
JVM
5. Two stage
Java-into-M
compiler
M
M
M
M
P
M
Full bootstrap
v1
Ada-S
M
Ada-S
C
1. Write Ada-S
compiler in C
2. Compile v1
using the C
compiler
M
v1
Ada-S Ada-S
Ada-S
M
M
M
4. Use v1 to compile v2
Chart 28
C
M
M
Ada-S
M
M
M
Ada-S
3. Convert the C version of
Ada-S into Ada-S version of
Ada-S
M
M
v2
v2
Ada-S
Ada-S
M
C
v2
v1
v1
v3
v3
M
Ada
v3
Ada
M
Ada-S
5. Extend Ada-S
compiler to (full)
Ada compiler
M
Ada
v2
Ada-S Ada-S
M
M
M
6. Compile full
version of Ada
using Ada-S
compiler
M
M
Half bootstrap
Ada
HM
Ada
TM
Ada
4. Use existing Ada
compiler fro HM
to compile the
Ada compiler that
run on HM but
generates code
for TM
TM
Ada
3.Rewrite Ada compiler that generates
HM code to Ada compiler that
generates machine code for machine
TM
2. Ada compiler
that generates
machine code for
machine H
expressed in HM
1. Ada compiler
that generates
machine code for
machine H
expressed in Ada
Ada
Ada
HM
HM
Ada
Ada
Ada
5. Make sure the compiler
works properly
TM
P
Ada
HM HM
HM
Ada
HM
HM
Ada
Ada
Ada
TM
Ada
TM
TM
P
TM
P
TM
TM
TM
TM
HM
HM
Chart 29
6. Use the compiler to compile itself. Now
have an Ada compiler that generates TM
code that runs on machine TM
Bootstrap to improve efficiency
v1
Ada
v2
v1
Ada
Ms
Ada
Ms
Ada
Ms
Ada
Mf
2. Rewrite v1 to run on M-fast in Ada
1. Start with v1 targeted to M-slow written in Ada and
compiled to run on M-slow
4. Compile a program using v2; it will compile slow but run fast
3. Use v1 to compile v2
v2
v2
Ada
Ada
Mf
v1
Ada
Ada
Ms
Mf
Ms
P
Ada
v2
Ada
Mf
Mf
Mf
M
v3
v2
Ada
Ada
5. Use v2 to compile v2 to produce v3
which will be the fast compiler.
Chart 30
P
Ms
Ms
M
P
Mf
v2
Ada
Ada
Ms
Ms
M
Mf
Mf