Att exekvera syntaxträdet. Stackmaskiner.

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.

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

Interpreters

Approaches:

Att exekvera syntaxträdet direkt

Lisp! Exempel på kod för en execute-funktion i interpretatorn:
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)

Example source program: 2 * 3 + 4 * 5

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

Code:

push 2
push 3
*
push 4
push 5
*
+
Operations: push, pop (and throw away), +, -, *, ...
We need an opcode, plus an "immediate" or "address" field

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
+
=
Operations: lvalue, rvalue

Control flow

Operations:

Statements: IF

Example source code:
if (a > 2)
  a = a + 1;
Target code for the stack machine:
rvalue a
push 2
>
gofalse 1
lvalue a
rvalue a
push 1
+
=
label 1 -- not really an instruction
"Yacc pseudocode", with an operator+ that concatenates instruction sequences:
stmt: IF '(' expr ')' stmt1 {
  int afterwards = newlabel();
  $$ = $3 +
       instr(gofalse, afterwards) +
       $5 +
       instr(label, afterwards);
}
Or, with plain printf:
stmt: IF '(' expr ')'
      { afterwards = newlabel(); printf("gofalse %d\n", afterwards); }
      stmt1
      { printf("label%d\n", afterwards); }

Statements: WHILE

Example source code:
while (i < 0)
  i = k;
Target code for the stack machine:
label 1
rvalue i
push 0
<
gofalse 2
lvalue i
rvalue k
=
jump 1
label 2
"Yacc pseudocode":
stmt: WHILE '(' expr ')' stmt1 {
  int before = newlabel();
  int afterwards = newlabel();
  $$ = instr(label, before) +
       $3 +
       instr(gofalse, afterwards) +
       $5 +
       instr(jump, before) +
       instr(label, afterwards);
}
Example source code:
if (a > 2)
  while (a < 10)
    a = a + 1;
Target code for the stack machine:
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

Inte alltid riktigt så enkelt. Här är ett problem.

Example source code:

if (x > 2 || y > 3)
  z = 4;
Dvs: Incorrect target code for the stack machine:
rvalue x
push 2
>
gotrue 1
rvalue y
push 3
<
gofalse 2
label 1
lvalue z
push 4
=
label 2
Why is it not correct? No single-entry and single-exit "block" for the expression! So, this would have to be compiled differently:
result = x > 2 || y > 3;
Correct target code:
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


Thomas Padron-McCarthy (Thomas.Padron-McCarthy@tech.oru.se) 5 oktober 2007