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
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]); } ... }
Simple postfix target program: 2 3 * 4 5 * +
Code:
Operations: push, pop (and throw away), +, -, *, ...push 2 push 3 * push 4 push 5 * +
Example: 2 * a + 3
Code:
push 2 rvalue a * push 3 +
Example: a = 2 * a + 3
Code:
Operations: lvalue, rvaluelvalue a push 2 rvalue a * push 3 + =
Target code for the stack machine:if (a > 2) a = a + 1;
"Yacc pseudocode", with an operator+ that concatenates instruction sequences:rvalue a push 2 > gofalse 1 lvalue a rvalue a push 1 + = label 1 -- not really an instruction
Or, with plain printf: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); }
Target code for the stack machine:while (i < 0) i = k;
"Yacc pseudocode":label 1 rvalue i push 0 < gofalse 2 lvalue i rvalue k = jump 1 label 2
Example source code:stmt: WHILE '(' expr ')' stmt1 { int before = newlabel(); int afterwards = newlabel(); $$ = instr(label, before) + $3 + instr(gofalse, afterwards) + $5 + instr(jump, before) + instr(label, afterwards); }
Target code for the stack machine: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
Example source code:
Dvs:if (x > 2 || y > 3) z = 4;
Why is it not correct? No single-entry and single-exit "block" for the expression! So, this would have to be compiled differently:rvalue x push 2 > gotrue 1 rvalue y push 3 < gofalse 2 label 1 lvalue z push 4 = label 2
Correct target code: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