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

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

ASU-86 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:

The context (Sw: "omgivning", "kontext") of a compiler (klicka på bilden för större format):

The context of a compiler

Plus:

1.2 The Structure of a Compiler

Sex eller sju faser:
  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)
The phases of compiler (ALSU-07 fig 1.6):

ALSU-07 fig 1.6, Phases of a compiler

Lexical analysis

A fragment of a program: position := initial + rate * 60
Omvandlas till en token-ström (normalt: representeras med heltal)

Syntax analysis

Part of a grammar ("kontextfri grammatik", med BNF-notation = Backus-Naur-form):

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.4, Parse tree for...

ASU-86 fig 1.2: "abstract syntax tree", or just "syntax tree"

ASU-86 fig 1.2, Syntax tree for...

All the phases

ALSU-07 fig 1.7

ALSU-07 fig 1.7, Translation of a statement

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 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:

1.3 The Evolution of Programming Languages

Skillnaden på: Högre nivå: maskinspråk - assembler - C - Java (och sen då? scriptspråk?) Skillnaden på:

1.4 The Science of Building a Compiler

Ett par viktiga saker ur data- (och språk-)vetenskapen

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? Vad menas (i det här sammanhanget) med omgivning (environment) och tillstånd (state)? Skillnaden på: Skillnaden på: Skillnaden på (olika i olika sammanhang!): Skillnaden på (olika i olika sammanhang!): Olika metoder för parameteröverföring:

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