Föreläsning 1: Kompilatorer - vad, hur och varför?
Kursen Kompilatorer och interpretatorer |
Föreläsningar:
1
2
3
4
5
6
7
8
9
10
11
12
Det här är ungefär vad jag tänker säga på föreläsningen.
Använd det för förberedelser, repetition och ledning.
Det är inte en definition av kursinnehållet,
och det ersätter inte kursboken.
Information om kursen
- Jag: Thomas Padron-McCarthy
- Hemsidan: http://basen.oru.se/kurser/koi/
- Kursens innehåll och mål (principer + praktik; vad händer bakom kör-knappen + bygga kompilatorer + nytta för att bygga andra program)
- Föreläsningar (12 * 2h)
- Inlämningsuppgifter, projekt och bokade labbtider (6 * 4h)
- Enklare tentamen (bara godkänt)
- Betyget bestäms av inlämningsuppgifter och projekt
- Vad ni kan redan nu (or else...):
- grunder om datorer: minne, kompilator
- programmera, i C (och C++)
- datastrukturer (främst träd, inte bara binära)
- Kursboken (wohoo! ny upplaga 2007, första sen 1986)
Idag:
ALSU-07 (kursboken), Chapter 1, Introduction to Compiling
Frivillig läsning:
KP (Kjell Posts kompendium Kompilatorkonstruktion) kapitel 1, Kompilatorns beståndsdelar
1.1 Language Processors
ASU-86 (gamla kursboken) fig 1.1: A compiler
input: source program
output: target program, error messages, warnings
the target program:
machine code for physical or abstract machine, assembler, C, silicon design...
Systematic techniques:
The first Fortran compiler took 18 staff-years in the 1950's.
In the 1980's, "a substantial compiler can be implemented even as
a student project in a one-semester compiler design course".
Main idea:
analysis (Swedish: "analys")
(one or more) intermediate representation(s) (Sw: "internform"): usually a tree, syntax tree
synthesis (Sw: "syntes")
Later: phases
Examples of compiler-like tools that perform analysis:
-
Structure editors (ex: Emacs' C mode, editorn i Visual Studio)
-
kodformatterare ("pretty-printers")
-
Interpreters
(execute the tree, or generate byte-code or similar, compare: abstract machine)
"script languages", or "command languages", are often interpreted
-
Silicon compilers
-
HTML or XML processors
-
Programs that read configuration files
-
Statisk kontroll av program (ex: lint, verktyg för C++-koll)
The context (Sw: "omgivning", "kontext") of a compiler
(klicka på bilden för större format):
Plus:
-
Sometimes a preprocessor (C: "#include" etc) before the actual compiler
-
Sometimes the compiler generates assembly code,
which is translated into machine code by an assembler
-
Sometimes the compiler generates C code,
which is translated into machine code by another compiler
-
Sometimes the compiler generates byte code for a virtual machine (Java, .NET),
which may be implemented as an interpreter or as a (just-in-time-)compiler
-
Relocatable machine code = object code, absolute machine code
-
Static and dynamic linking
1.2 The Structure of a Compiler
Sex eller sju faser:
- Lexical analyzer ("scanner")
- Syntactical analyzer ("parser")
- Semantic analyzer
- Intermediate code generator
- Machine-independent code optimizer
- Code generator
- Machine-dependent code optimizer
- (The symbol table)
- (Error handling: detection and reporting)
The phases of compiler (ALSU-07 fig 1.6):
Lexical analysis
A fragment of a program: position := initial + rate * 60
Omvandlas till en token-ström (normalt: representeras med heltal)
- Lexeme (svenska: lexem) = textsträngen, t ex position eller 60
- Token = spelmark, spårvagnspolett (men man säger "token" på svenska ocks)
- Lexical value (svenska: lexikaliskt värde) = t ex att det är identifierare nummer 17 eller talet 60
Syntax analysis
Part of a grammar ("kontextfri grammatik", med BNF-notation = Backus-Naur-form):
- expression -> identifier
- expression -> number
- expression -> expression1 + expression2
- expression -> expression1 * expression2
- expression -> ( expression1 )
- assignment statement -> identifier ":=" expression
This means:
An expression can consist of an identifier.
An expression can also consist of a number.
An expression can also consist of one expression, followed by a plus sign, followd by a second expression.
Etc.
Again: position := initial + rate * 60
ASU-86 fig 1.4: "concrete syntax tree", or "parse tree"
ASU-86 fig 1.2: "abstract syntax tree", or just "syntax tree"
All the phases
ALSU-07 fig 1.7
1.2.8 The Grouping of Phases
Fas = en (logisk) del av kompilatorn,
inte nödvändigtvis en tråd eller en del i en sekvens eller ens en procedur
- Front end (= analysdelen, ej beroende av målmaskinen)
- Back end (= syntesdelen, beroende av målmaskinen)
Pass = en genomgång (förr ofta en filläsning och en filskrivning) av programmet (i någon form),
innehåller normalt flera faser
1.2.9 Compiler-Construction Tools
Viktigast:
- Scanner generators (ex: Lex, Flex)
- Parser generators (ex: Yacc, Bison)
1.3 The Evolution of Programming Languages
Skillnaden på:
- högnivåspråk (high-level languages)
- lågnivåspråk (low-level languages)
Högre nivå: maskinspråk - assembler - C - Java (och sen då? scriptspråk?)
Skillnaden på:
- imperativa språk (som C, C++, Java, C#, Lisp) - ange hur, steg för steg
- deklarativa språk (som SQL, Prolog) - ange vad, men inte hur
1.4 The Science of Building a Compiler
Ett par viktiga saker ur data- (och språk-)vetenskapen
- grammatik (för språk)
- träd (en klass av datastrukturer, och inte bara binära)
1.5 Applications of Compiler Technology
(Hette "Cousins of the Compiler" i förra upplagan.)
1.6 Programming Language Basics
Vad menas (i det här sammanhanget) med statiskt och dynamiskt?
- statiskt = vid kompileringstillfället
- dynamiskt = vid exekveringstillfället
Vad menas (i det här sammanhanget) med omgivning (environment) och tillstånd (state)?
- omgivning = variablerna (t. ex. att variabeln heter x och finns här i minnet)
- tillstånd = variablernas värden (t. ex. att variabeln som heter x och finns här i minnet just nu har värdet 7)
Skillnaden på:
- identifierare (t ex teckensekvensen vikt)
- namn (t ex olle.vikt, om olle är namnet på en post med ett vikt-fält)
- variabel (plats i minnet, t ex just den här lokala variabelns plats)
Skillnaden på:
- static scope (statisk namnuppslagning, statisk räckvidd)
- dynamic scope (dynamisk namnuppslagning, dynamisk räckvidd)
Skillnaden på (olika i olika sammanhang!):
Skillnaden på (olika i olika sammanhang!):
Olika metoder för parameteröverföring:
- call by value
- call by reference
- call by name
- makrosubstitution
Kursen Kompilatorer och interpretatorer |
Föreläsningar:
1
2
3
4
5
6
7
8
9
10
11
12
Thomas Padron-McCarthy
(Thomas.Padron-McCarthy@oru.se)
30 augusti 2012