compiler-text.dvi

Size: px

Start display at page:

Download "compiler-text.dvi"

ふじよしえいさか
5 years ago
Views:

1 : 1. (source program) 2. (object code) 3. 1

2 2.2 C if while return C input() output() fun var ( ) main() C (C-Prime) C A B C 2.3 Pascal P 1 C LDC load constant LOD load STR store AOP arithmatic operation STP stop UJP unconditional jump FJP jump on false XST expand stack COP comparison operation MST mark stack RLN read line WLN write line CAL call RET return 1: P 4 p, i, b, t 2 p p (instruction) i p 1 2 (base) b t C P P ( )

3 p P t i b 2: 3 LDC AOP WLN STP output(7+8-9); LDC 0 7 LDC 0 8 AOP 0 0 LDC 0 9 AOP 0 1 WLN 0 0 STP LDC = 7 = LDC 7 = AOP 15 = LDC 15 = AOP 6 = WLN (a) (b) (c) 3: 2.4 C C (scanner) (token) (identifier) ( ) (reserved word) 3.4 C 2 4 3

4 if else while return var fun void int + - * / % > >= < <= ==!= = ( ) {, ; 2: VAR IDENT(x) SEMICOLON var x; FUN VOID IDENT(main) LPAREN RPAREN LBRACE = IDENT(x) BECOMES NUMBER(5) SEMICOLON x = 5; RBRACE END OF INPUT (a) (b) 4: 3.2 (parser) (recursive descend parser) 1 C (program), (declaration), (definition), (statement), (expression), (comparison), (arithmetic), (term), (factor), (atom) ( B ) program 5 C ( B) program (1) var declaration ( ) (2) fun definition 0 (3) end of input program 5 token_type read_token 1 VAR FUN var fun error void program() { if (token_type() == VAR) { read_token(); declaration(); while (token_type() == FUN) { read_token(); definition(); if (token_type()!= END_OF_INPUT) { error(); 5: statement 6 4

5 program VAR IDENT(x) SEMICOLON FUN VOID IDENT(main) LPAREN RPAREN LBRACE IDENT(x) BECOMES NUMBER(5) SEMICOLON RBRACE END OF INPUT = var declaration ident ; fun definition. end of input void ident ( ) { statement ident = expression ;. number (a) (b) 6: 3.3 (code generation) (syntax-directed translation) (arithmetic expression) arithmetic 7 AOP 7 instruction PLUS, MINUS +, - term (term) 3(a) 3(b) void arithmetic() { int op; term(); op = token_type(); while (op == PLUS op == MINUS) { read_token(); term(); if (op == PLUS) instruction(aop, 0, 0); else instruction(aop, 0, 1); op = token_type(); 7: 8(a) 1 sub() main() 8(b) main() main() sub() (call) sub() 5

6 (return) main() main() var x, y; fun int sub(a) { var x, z; sub() var y; main() sub() main() (a) (b) 8: C D C A E 3.4 (symbol table) 9(a) 1 x, y x, 9(b) 9(c) XST STR, LOD 3 4 x, y var x, y; x = 5; y = x; x 0 y 1 XST 0 2 LDC 0 5 STR 0 0 LOD 0 0 STR 0 1 XST 0-2 STP 0 0 (a) (b) (c) 9: 6

7 8(a) x, y 2 sub a 3 x, z 10(a) sub() x sub() 0 2 (3.5 ) ( 3 ) sub() a x, z sub() main() z sub() main() 6 main 7 y 10(b) main() y main() main() y x y sub a x z 0 1 int int x 0 y 1 sub int int main void void y 3 (a) sub() (b) main() 10: 3.5 (activation record) (stack frame) RA (return address) OB (old base) RV (return value) RA OB RV 8 main() 12(a) sub() 12(b) sub() sub() 12(c) 7

8 t b RA OB RV 11: t sub() z x a RA OB b RV t sub() RA OB b RV t z x a z x a RA OB RV main() b y RA OB RV y x y RA OB RV y x y RA OB RV y x (a) main() (b) sub() (c) sub() 12: 8

9 (if, while) [1] A. V. M. S. R. J. D [2] A. W [3] 1989 [4] T [5] B. W. D. M. C [6] S. P. 3 G. L. C

10 A (1) output(7+8-9); (2) var in, out; in = input(); out = -in; output(out); (3) var i; i = 1; while (i < 10) { if (i%2!= 0) output(i); i = i+1; (4) var x; fun void double() { x = x*2; x = 100; double(); output(x); (5) var x, pow; fun void powself(x) { var i; i = 0; while (i < x) { pow = pow*x; i = i+1; x = input(); pow = 1; powself(x); output(pow); (6) var num; fun int gcd(m, n) { if (n == 0) return m; else return gcd(n, m%n); var m, n; num = 3; while (num > 0) { m = input(); n = input(); output(gcd(m, n)); num = num-1; 10

11 B [ var ]? [ fun ] end of input program ident, ; declaration void ident ( [ ident, ]? ) { [ var ]? definition int ident ( [ ident, ]? ) { [ var ]? ident ( [, ]? ) ; statement ident = ; if ( ) [ else ]? while ( ) { return? ; [ ==!= ] expression [ > >= < <= ] comparison [ + - ] arithmetic [ * / % ] term [ + - ]? number ( ) ident ident ( [, ]? ) factor atom [ ] α β α β α? α α ε α α 0 α β β α 1 α[βα] 11

12 C LDC 0 n load constant t t+1 ; s[t] n n LOD r a load t t+1 ; r ( 0 1) a s[t] s[base(r)+a] LDA r a load address t t+1 ; r a s[t] base(r)+a ILD 0 0 indirect load s[t] s[s[t]] STR r a store s[base(r)+a] s[t] ; t t 1 r a ISR 0 0 indirect store s[s[t 1]] s[t] ; AOP 0 n arithmetic COP 0 n comparison t t 2 s[t 1] s[t 1] op s[t] ; 2 operation t t 1 n = 0,1,2,3,4 op +,,,div,mod s[t 1] s[t 1] op s[t] ; 2 operation t t 1 (0 1) n = 0,1,2,3,4,5 op >,,<,,=, RLN 0 0 read line t t+1 ; 1 readline(s[t]) WLN 0 0 write line writeline(s[t]) ; STP 0 0 stop t t 1 UJP 0 a unconditional p a jump FJP 0 a jump on false p a if s[t] = 0 ; t t 1 XST 0 n expand stack t t+n 1 a 0 a n MST 0 0 mark stack s[t+1] 0 ; (RV) s[t+2] b ; t t+3 (OB) (RA) CAL n a call s[t n] p ; (RA) b t (3+n)+1 ; p a a (n ) RET 0 n return t b+n 1 ; p s[b+2] ; b s[b+1] RA OB (n 0 1) LDA, ILD, ISR 3 12

13 D (1) LDC AOP COP LOD STR RLN WLN (2) if ( ) 1 else 2 while ( ) FJP FJP 1 UJP 2 UJP (3) [ void int ] (, ) { [ var ]? XST RET (4) ( ) ( 1,, n ) XST UJP MST CAL main() XST STP MST 1. n CAL (5) return? ; ( ) STR ( ) RET 13

14 E var num; 0: XST 0 1 1: UJP 0 42 fun int gcd(m, n) { 2: XST 0 0 if (n == 0) 3: LOD 1 4 4: LDC 0 0 5: COP 0 4 6: FJP 0 11 return m; 7: LOD 1 3 8: STR 1 0 9: RET 0 1 else 10: UJP 0 19 return gcd(n, m%n); 11: MST : LOD : LOD : LOD : AOP : CAL : STR : RET : RET 0 1 var m, n; 20: XST 0 2 num = 3; 21: LDC : STR 0 0 while (num > 0) { 23: LOD : LDC : COP : FJP 0 41 m = input(); 27: RLN : STR 1 3 n = input(); 29: RLN : STR 1 4 output(gcd(m, n)); 31: MST : LOD : LOD : CAL : WLN 0 0 num = num-1; 36: LOD : LDC : AOP : STR : UJP : RET : MST : CAL : XST : STP

( ) ( ) lex LL(1) LL(1)

( ) ( ) lex LL(1) LL(1) () () lex LL(1) LL(1) http://www.cs.info.mie-u.ac.jp/~toshi/lectures/compiler/ 29 5 14 1 1 () / (front end) (back end) (phase) (pass) 1 2 1 () () var left, right; fun int main() { left = 0; right = 10;