程序代写代做代考 computer architecture interpreter assembler Java x86 data structure c/c++ algorithm compiler Haskell ocaml F# cache mips Compilers and computer architecture: introduction

Compilers and computer architecture: introduction
Martin Berger
September 2015

Administrative matters: lecturer

Administrative matters: lecturer
􏹩 Name:MartinBerger

Administrative matters: lecturer
􏹩 Name:MartinBerger
􏹩 Email: M.F.Berger@sussex.ac.uk

Administrative matters: lecturer
􏹩 Name:MartinBerger
􏹩 Email: M.F.Berger@sussex.ac.uk
􏹩 Web: www.sussex.ac.uk/Users/mfb21/compilers

Administrative matters: lecturer
􏹩 Name:MartinBerger
􏹩 Email: M.F.Berger@sussex.ac.uk
􏹩 Web: www.sussex.ac.uk/Users/mfb21/compilers
􏹩 Lecturenotesetc: www.sussex.ac.uk/Users/mfb21/compilers/material.html
􏹩 Officehours:afterthelectures,andonrequest(please arrange by email)

Administrative matters: Dates, times and assessment

Administrative matters: Dates, times and assessment
􏹩 Lectures:Twolecturesperweek,Mondays16:00-17:00in Fulton B and Fridays 15:00-16:00 in Arts A A02.

Administrative matters: Dates, times and assessment
􏹩 Lectures:Twolecturesperweek,Mondays16:00-17:00in Fulton B and Fridays 15:00-16:00 in Arts A A02.
􏹩 Tutorials:Thursdays14:00-15:00and15:00-16:00in Chichester 1 CI204/5, and Fridays 11:00 – 12:00 and 12:00 – 13:00 also in Chichester 1 CI204/5. The TA is Alex Jeffery, email: apj21@sussex.ac.uk.
􏹩 Therewill(probably)bePALsessions,moresoon.
􏹩 Assessment:coursework(50%)andbyunseen examination (50%). The coursework consists of two parts (weighted 30% and 70% respectively). Both involve writing parts of a compiler. Due dates TBC.
􏹩 Iwillusethecourse’sStudyDirectpagefrequently.Ifyou have questions, you are free to ask me or the TA in person, but please consider asking them on Study Direct or in class, because then the answers can benefit other students too. I can set up Twitter / Facebook if you want.

Prerequisites

Prerequisites
Good Java programming skills are indispensable.

Prerequisites
Good Java programming skills are indispensable.
It helps if you have already seen e.g. regular expressions, FSMs etc. But we will cover all this from scratch.

Prerequisites
Good Java programming skills are indispensable.
It helps if you have already seen e.g. regular expressions, FSMs etc. But we will cover all this from scratch.
It helps if you have already seen a CPU, e.g. know what a register is or a stack pointer.

Course content

Course content
I’m planning to give a fairly orthodox compilers course that show you all parts of a compiler. At the end of this course you should be able to write a fully blown compiler yourself and implement programming languages.
We will also look at computer architecture, although more superficially.
This will take approximately 9 weeks, so we have time at the end for some advanced material. I’m happy to tailor the course to your interest, so please let me know what you want to hear about.

Coursework

Coursework
There will be two assessed courseworks (dates TBC). Evaluation of courseworks will (largely) be by automated tests. This is quite different from what you’ve seen so far. The reason for this new approach is threefold.
􏹩 Compilersarecomplicatedalgorithmsandit’sbeyond human capabilities to find subtle bugs.
􏹩 Realism.Inindustryyoudon’tgetpaidforbeingnice,orfor having code that “almost” works.
􏹩 Fairness.Automatictestingremovessubjectiveelement.
Note that if you make a basic error in your compiler then it is quite likely that every test fails and you will get 0 points. So it is really important that you test your code before submission thoroughly. I encourage you to share tests and testing frameworks with other students: as tests are not part of the deliverable, you make share them. Of course the compiler must be written by yourself.

Plan for today’s lecture

Plan for today’s lecture
Whirlwind overview of the course.

Plan for today’s lecture
Whirlwind overview of the course. 􏹩 Basicmaterial

Plan for today’s lecture
Whirlwind overview of the course.
􏹩 Basicmaterial
􏹩 Why study compilers?

Plan for today’s lecture
Whirlwind overview of the course. 􏹩 Basicmaterial
􏹩 Why study compilers?
􏹩 What is a compiler?

Plan for today’s lecture
Whirlwind overview of the course. 􏹩 Basicmaterial
􏹩 Why study compilers?
􏹩 What is a compiler?
􏹩 Compiler structure

Plan for today’s lecture
Whirlwind overview of the course. 􏹩 Basicmaterial
􏹩 Why study compilers?
􏹩 What is a compiler?
􏹩 Compiler structure
􏹩 Lexical analysis

Plan for today’s lecture
Whirlwind overview of the course. 􏹩 Basicmaterial
􏹩 Why study compilers?
􏹩 What is a compiler?
􏹩 Compiler structure
􏹩 Lexical analysis
􏹩 Syntax analysis

Plan for today’s lecture
Whirlwind overview of the course. 􏹩 Basicmaterial
􏹩 Why study compilers?
􏹩 What is a compiler?
􏹩 Compiler structure
􏹩 Lexical analysis
􏹩 Syntax analysis
􏹩 Semantic analysis, type-checking
􏹩 Code generation
􏹩 Advancedmaterial

Why study compilers?

Why study compilers?
To become a good programmer, you need to understand what happens ’under the hood’ when you write programs in a high-level language.

Why study compilers?
To become a good programmer, you need to understand what happens ’under the hood’ when you write programs in a high-level language.
To understand low-level languages (assembler, C/C++ and Rust) better. Those languages are of prime importance, e.g. for writing operating systems, embedded code and generally code that needs to be really fast (e.g. computer games, big data).
Most large programs have a tendency to embed a programming language. The skill quickly to write an interpreter or compiler for such embedded languages is invaluable.
But most of all: compilers are extremely amazing, beautiful and one of the all time great examples of human ingenuity. After 70 years of refinement compilers are a paradigm case of beautiful software structure (modularisation). I hope it inspires you.

Overview: what is a compiler?

Overview: what is a compiler?
A compiler is a program that translates programs from one programming language to programs in another programming language. The translation should preserve meaning (what does “preserve” and “meaning” mean in this context?).
Source program Compiler Target program
Error messages
Typically, the input language (called source language) is more high-level than the output language (called target language)

Overview: Compiler is a bridge

Example translation: source program

Example translation: source program
Here is a little program. (What does it do?)
int testfun( int n ){
int res = 1;
while( n > 0 ){
n–;
res *= 2; }
return res; }

Example translation: source program
Here is a little program. (What does it do?)
int testfun( int n ){
int res = 1;
while( n > 0 ){
n–;
res *= 2; }
return res; }
Using gcc -S this translates to the following x86 machine code …

Example translation: target program
Leh_func_begin1: pushq %rbp
Ltmp0: Ltmp1:
LBB1_1:
movq %rsp, %rbp
movl %edi, -4(%rbp) movl $1, -16(%rbp) jmp LBB1_2
movl -4(%rbp), %eax subl $1, %eax
movl %eax, -4(%rbp) movl -16(%rbp), %eax imull $2, %eax, %eax movl %eax, -16(%rbp)
movl -4(%rbp), %eax cmpl $0, %eax
jg LBB1_1
movl -16(%rbp), %eax movl %eax, -12(%rbp) movl -12(%rbp), %eax movl %eax, -8(%rbp) movl -8(%rbp), %eax popq %rbp
LBB1_2:
ret Leh_func_end1:
.globl _main .align 4, 0x90

Compilers have a beautifully simple structure
Source program
Analysis phase
Code generation
Generated program

Compilers have a beautifully simple structure
Source program
Analysis phase
Code generation
Generated program
In the analysis phase two things happen:

Compilers have a beautifully simple structure
Source program
Analysis phase
Code generation
Generated program
In the analysis phase two things happen:
􏹩 Creatingaconvenient(foracomputer) representation of the source program structure for further processing. (Abstract syntax tree (AST), symbol table).
􏹩 Analysingiftheprogramiswell-formed(e.g. checking for syntax and type errors).

Compiler structure

Compiler structure
Compilers have a beautifully simple structure. This structure was arrived at by breaking a hard problem (compilation) into several smaller problems and solving them separately. This has the added advantage of allowing to retarget compilers (changing source or target language) quite easily.
Source program
Lexical analysis
Syntax analysis
Semantic analysis, e.g. type checking
Intermediate code generation
Optimisation
Code generation
Translated program

Compiler structure

Compiler structure
Source program
Lexical analysis
Syntax analysis
Semantic analysis, e.g. type checking
Intermediate code generation
Optimisation
Code generation
Translated program
Interesting question: when do these phases happen?
In the past, all happend at … compile-time. Now some happen at run-time in Just-in-time compilers (JITs). This has profound influences on choice of algorithms and performance.

Compiler structure

Compiler structure
Source program
Lexical analysis
Syntax analysis
Semantic analysis, e.g. type checking
Intermediate code generation
Optimisation
Code generation
Translated program
Another interesting question: do you note some thing about all these phases?
The phases are purely functional, in that they take one input, and return one output. Functional programming languages like Haskell, Ocaml, F#, or Scala are ideal for writing compilers.

Phases: Overview
􏹩 Lexicalanalysis
􏹩 Syntacticanalysis(parsing)
􏹩 Semanticanalysis(type-checking) 􏹩 Intermediatecodegeneration
􏹩 Optimisation
􏹩 Codegeneration

Phases: Lexical analysis

Phases: Lexical analysis
Source program
Lexical analysis
Syntax analysis
Semantic analysis, e.g. type checking
Intermediate code generation
Optimisation
Code generation
Translated program

Phases: Lexical analysis

Phases: Lexical analysis
What is the input to a compiler?

Phases: Lexical analysis
What is the input to a compiler?
A (often long) string, i.e. a sequence of characters.

Phases: Lexical analysis
What is the input to a compiler?
A (often long) string, i.e. a sequence of characters.
Strings are not an efficient data-structure for a compiler to work with (= generate code from). Instead, compilers generate code from a more convenient data structure called “abstract syntax trees” (ASTs). We construct the AST of a program in two phases:
􏹩 Lexicalanlysis.Wheretheinputstringisconvertedintoa list of tokens.
􏹩 Parsing.WheretheASTisconstructedfromatokenlist.

Phases: Lexical analysis

Phases: Lexical analysis
In the lexical analysis, a string is converted into a list of tokens. Example: The program

Phases: Lexical analysis
In the lexical analysis, a string is converted into a list of tokens. Example: The program
int testfun( int n ){
int res = 1;
while( n > 0 ){
n–;
res *= 2; }
return res; }

Phases: Lexical analysis
In the lexical analysis, a string is converted into a list of tokens. Example: The program
int testfun( int n ){
int res = 1;
while( n > 0 ){
n–;
res *= 2; }
return res; }
Is (could be) represented as the list
T_int, T_ident ( “testfun” ), T_left_brack,
T_int, T_ident ( “n” ), T_rightbrack,
T_left_curly_brack, T_int, T_ident ( “res” ),
T_eq, T_num ( 1 ), T_semicolon, T_while, …

Phases: Lexical analysis
T_int, T_ident ( “testfun” ), T_left_brack,
T_int, T_ident ( “n” ), T_rightbrack,
T_left_curly_brack, T_int, T_ident ( “res” ),
T_eq, T_num ( 1 ), T_semicolon, T_while, …
Why is this interesting?
􏹩 Savesmemory(notparticularlyrelevantnow,butvery important in the past).
􏹩 Abstractsfromirrelevantdetail(e.g.syntaxofkeywords, whitespace).