Att exekvera syntaxträdet. Stackmaskiner.

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.

Idag: Interpretering, dels genom att exekvera syntaxträdet direkt, dels med en stackmaskin

• ALSU-07 avsnitt 8.1.2
• (ASU-86 2.8)
• (KP kapitel 5)

Interpreters

• Just another target machine (abstract machines)
  • "The next phase", built-in "compilation" and execution (example: Pike)
  • "Independent" abstract machines (example: JVM)
• Stack machines
• Execute the syntax tree
• Environments, symbol tables

Att exekvera syntaxträdet direkt

• Simple tree: 2 * 3 + 4
• Environment for variables (a symbol table)
• Lookup: 2 * a + 4
• Assignment: a = 2 * a + 4
• Statements: if, while, ...
• Functions!
  • Function definition, formal parameters
  • Function call, actual arguments
  • A new environment (= the activation record)
  • Return value

int execute(struct TreeNode* tree) {
    if (tree->type == ID)
        return symtable[tree->which_id].value;
    else if (tree->type == NUM)
        return tree->which_number;
    else if (tree->type == PLUS) {
        int arg1 = execute(tree->subtrees[0]);
        int arg2 = execute(tree->subtrees[0]);
        return arg1 + arg2;     
    }
    else if (tree->type == IF) {
        int cond = execute(tree->subtrees[0]);
        if (cond)
            return execute(tree->subtrees[1]);
        else if (tree->subtrees[2] != NULL)
            return execute(tree->subtrees[2]);
    }
    ...
}

Abstract stack machines

The basics (you remember this from the lab)

• A number: push the number on the stack
• An operation: pop, pop, calculate, push the result on the stack

Simple postfix target program: 2 3 * 4 5 * +

Code:

push 2
push 3
*
push 4
push 5
*
+

l-values and r-values ("left"-values, "right"-values)

Example: 2 * a + 3

Code:

push 2
rvalue a
*
push 3
+

Example: a = 2 * a + 3

Code:

lvalue a
push 2
rvalue a
*
push 3
+
=

Control flow

• label some-label -- not really an instruction!
• jump some-label
• gofalse some-label
• gotrue some-label
• halt

Statements: IF

if (a > 2)
  a = a + 1;

rvalue a
push 2
>
gofalse 1
lvalue a
rvalue a
push 1
+
=
label 1 -- not really an instruction

stmt: IF '(' expr ')' stmt1 {
  int afterwards = newlabel();
  $$ = $3 +
       instr(gofalse, afterwards) +
       $5 +
       instr(label, afterwards);
}

stmt: IF '(' expr ')'
      { afterwards = newlabel(); printf("gofalse %d\n", afterwards); }
      stmt1
      { printf("label%d\n", afterwards); }

Statements: WHILE

while (i < 0)
  i = k;

label 1
rvalue i
push 0
<
gofalse 2
lvalue i
rvalue k
=
jump 1
label 2

stmt: WHILE '(' expr ')' stmt1 {
  int before = newlabel();
  int afterwards = newlabel();
  $$ = instr(label, before) +
       $3 +
       instr(gofalse, afterwards) +
       $5 +
       instr(jump, before) +
       instr(label, afterwards);
}

if (a > 2)
  while (a < 10)
    a = a + 1;

rvalue a
push 2
>
gofalse 1
label 2
rvalue a
push 10
<
gofalse 3
lvalue a
rvalue a
push 1
+
=
jump 2
label 3
label 1

Short-circuit evaluation of boolean operators

Example source code:

if (x > 2 || y > 3)
  z = 4;

• Värdet av hela uttrycket x > 2 || y > 3 ska bli sant eller falskt
• Om x > 2 ska y > 3 överhuvudtaget inte beräknas
• Villkorliga hoppinstruktioner (som gofalse) poppar översta värdet på stacken (Övning: Varför?)

rvalue x
push 2
>
gotrue 1
rvalue y
push 3
<
gofalse 2
label 1
lvalue z
push 4
=
label 2

result = x > 2 || y > 3;

rvalue x
push 2
>
copy
gotrue 1
pop
rvalue y
push 3
<
label 1
gofalse 2
lvalue z
push 4
=
label 2

Kursen Kompilatorer och interpretatorer | Föreläsningar: 1 2 3 4 5 6 7 8 9 10 11 12