Föreläsning 1: Kompilatorer - vad, hur och varför?

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

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")

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

1. Lexical analyzer ("scanner")
2. Syntactical analyzer ("parser")
3. Semantic analyzer
4. Intermediate code generator
5. Machine-independent code optimizer
6. Code generator
7. Machine-dependent code optimizer
8. (The symbol table)
9. (Error handling: detection and reporting)

Lexical analysis

• 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

• expression -> identifier
• expression -> number
• expression -> expression₁ + expression₂
• expression -> expression₁ * expression₂
• expression -> ( expression₁ )
• 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

1.2.8 The Grouping of Phases

• Front end (= analysdelen, ej beroende av målmaskinen)
• Back end (= syntesdelen, beroende av målmaskinen)

1.2.9 Compiler-Construction Tools

• Scanner generators (ex: Lex, Flex)
• Parser generators (ex: Yacc, Bison)

1.3 The Evolution of Programming Languages

• högnivåspråk (high-level languages)
• lågnivåspråk (low-level languages)

• 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

• grammatik (för språk)
• träd (en klass av datastrukturer, och inte bara binära)

1.5 Applications of Compiler Technology

1.6 Programming Language Basics

• statiskt = vid kompileringstillfället
• dynamiskt = vid exekveringstillfället

• 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)

• 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)

• static scope (statisk namnuppslagning, statisk räckvidd)
• dynamic scope (dynamisk namnuppslagning, dynamisk räckvidd)

• procedur
• funktion
• metod

• definition
• deklaration

• 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