Bài giảng Xây dựng chương trình dịch: Bài 12 - Nguyễn Thị Thu Hương

21/1/2010<br /> <br /> Nội dung<br /> z<br /> z<br /> <br /> Bài 12<br /> <br /> Tổng quan về sinh mã đích<br /> Máy ngăn xếp<br /> z<br /> <br /> Sinh mã đích<br /> <br /> z<br /> <br /> z<br /> z<br /> <br /> Sinh mã cho các lệnh cơ bản<br /> Xây dựng bảng ký hiệu<br /> z<br /> <br /> Nguyễn Thị Thu Hương<br /> <br /> Tổ chức bộ nhớ<br /> Bộ lệnh<br /> <br /> z<br /> z<br /> <br /> Biến<br /> Tham số<br /> Hàm, thủ tục và chương trình<br /> Lớp KHMT K50<br /> <br /> 1<br /> <br /> Chương trình đích<br /> „<br /> „<br /> „<br /> „<br /> „<br /> <br /> 2<br /> <br /> Chương trình đích được dịch từ<br /> <br /> Viết trên một ngôn ngữ trung gian<br /> Là dạng Assembly của máy giả định (máy ảo)<br /> Máy<br /> y ảo làm việc<br /> ệ với bộ<br /> ộ nhớ stack<br /> Việc thực hiện chương trình thông qua một<br /> interpreter<br /> Interpreter mô phỏng hành động của máy ảo<br /> thực hiện tập lệnh assembly của nó<br /> <br /> Mã nguồn<br /> „ Mã trung gian<br /> „<br /> <br /> 3<br /> <br /> 4<br /> <br /> 1<br /> <br /> 21/1/2010<br /> <br /> Máy ngăn xếp<br /> z<br /> <br /> Máy ngăn xếp<br /> <br /> Máy ngăn xếp là một hệ thống tính toán<br /> <br /> Code buffer<br /> <br /> Sử dụng ngăn xếp để lưu trữ các kết quả trung gian<br /> của quá trình tính toán<br /> z Kiến trúc đơn giản<br /> z Bộ lệnh đơn giản<br /> Máy ngăn xếp có hai vùng bộ nhớ chính<br /> z Khối lệnh: chứa mã thực thi của chương trình<br /> z Ngăn xếp: sử dụng để lưu trữ các kết quả trung gian<br /> z<br /> <br /> z<br /> <br /> Lớp KHMT K50<br /> <br /> PC<br /> <br /> DL<br /> <br /> LA 0,4<br /> <br /> RA<br /> <br /> ST<br /> <br /> B<br /> <br /> SL<br /> T ↑<br /> <br /> P1<br /> P2<br /> V1<br /> V2<br /> tmp1<br /> <br /> Lớp KHMT K50<br /> <br /> 5<br /> <br /> T<br /> <br /> 6<br /> <br /> Máy ngăn xếp<br /> z<br /> <br /> Thanh ghi<br /> z PC (program counter): con trỏ lệnh trỏ tới<br /> lệnh hiện tại đang thực thi trên bộ đệm<br /> chương trình<br /> z B (base) : con trỏ trỏ tới địa chỉ gốc của<br /> vùng nhớ cục bộ. Các biến cục bộ được<br /> truy xuất gián tiếp qua con trỏ này<br /> z T (top); trỏ tới đỉnh của ngăn xếp<br /> <br /> Lớp KHMT K50<br /> <br /> RV<br /> <br /> INC 4<br /> LC 1<br /> <br /> Máy ngăn xếp<br /> z<br /> <br /> Stack<br /> <br /> JMP 2<br /> <br /> 7<br /> <br /> Bản hoạt động (activation record/stack frame)<br /> z Không gian nhớ cấp phát cho mỗi chương trình con (hàm/thủ<br /> tục/chương trình chính) khi chúng được kích hoạt<br /> z Lưu giá trị tham số<br /> z Lưu giá trị biến cục bộ<br /> z Lưu các thông tin khác<br /> z Giá trị trả về<br /> ề của hàm – RV<br /> z Địa chỉ cơ sở của bản hoạt động của chương trình con<br /> gọi tới (caller) – DL<br /> z Địa chỉ lệnh quay về khi kết thúc chương trình con – RA<br /> z Địa chỉ cơ sở của bản hoạt động của chương trình con<br /> bao ngoài – SL<br /> z Một chương trình con có thể có nhiều bản hoạt động<br /> Lớp KHMT K50<br /> <br /> 8<br /> <br /> 2<br /> <br /> 21/1/2010<br /> <br /> Máy ngăn xếp<br /> Procedure P(I : integer);<br /> Var a : integer;<br /> Function Q;<br /> Var x : char;<br /> Begin<br /> …<br /> return<br /> E d<br /> End;<br /> Procedure R(X: integer);<br /> Var y : char;<br /> Begin<br /> …<br /> y = Call Q;<br /> …<br /> End;<br /> Begin<br /> …<br /> Call R(1);<br /> …<br /> End;<br /> …<br /> <br /> Máy ngăn xếp<br /> <br /> …<br /> RV<br /> DL<br /> RA<br /> SL<br /> Param I<br /> Local x<br /> …<br /> RV<br /> DL<br /> RA<br /> SL<br /> Local x<br /> …<br /> RV<br /> DL<br /> RA<br /> SL<br /> param x<br /> Local y<br /> Lớp KHMT K50<br /> <br /> z<br /> z<br /> P frame<br /> <br /> z<br /> R frame<br /> <br /> z<br /> <br /> RV (return value): Lưu trữ giá trị trả về cho mỗi hàm<br /> DL (dynamic link): Sử dụng để hồi phục ngữ cảnh<br /> của chương trình gọi (caller) khi chương trình được<br /> gọi (callee) kết thúc<br /> RA (return address): Sử dụng để tìm tới lệnh tiếp<br /> theo của caller khi callee kết thúc<br /> SL (static link): Sử dụng để truy nhập các biến phi<br /> cục bộ<br /> <br /> Q frame<br /> <br /> Lớp KHMT K50<br /> <br /> 9<br /> <br /> Máy ngăn xếp<br /> <br /> Máy ngăn xếp<br /> z<br /> <br /> Bộ lệnh<br /> <br /> op<br /> <br /> p<br /> <br /> 10<br /> <br /> q<br /> <br /> z<br /> <br /> Bộ lệnh<br /> <br /> op<br /> <br /> q<br /> <br /> LA<br /> <br /> Load Address<br /> <br /> t:=t+1; s[t]:=base(p)+q;<br /> <br /> J<br /> <br /> LV<br /> <br /> Load Value<br /> <br /> t:=t+1; s[t]:=s[base(p)+q];<br /> <br /> FJ<br /> <br /> False Jump<br /> <br /> if s[t]=0 then pc:=q; t:=t-1;<br /> <br /> HL<br /> <br /> Halt<br /> <br /> Halt<br /> <br /> ST<br /> <br /> Store<br /> <br /> s[s[t-1]]:=s[t]; t:=t-2;<br /> <br /> Call<br /> <br /> s[t+2]:=b; s[t+3]:=pc;<br /> b:=t+1; pc:=q;<br /> <br /> LC<br /> <br /> Load Constant<br /> <br /> t:=t+1; s[t]:=q;<br /> <br /> LI<br /> <br /> Load Indirect<br /> <br /> s[t]:=s[s[t]];<br /> <br /> INT<br /> <br /> Increment T<br /> <br /> t:=t+q;<br /> <br /> DCT<br /> <br /> Decrement T<br /> <br /> t:=t-q;<br /> <br /> CALL<br /> EP<br /> EF<br /> <br /> Lớp KHMT K50<br /> <br /> 11<br /> <br /> Jump<br /> <br /> p<br /> <br /> Exit<br /> Procedure<br /> Exit<br /> Function<br /> <br /> pc:=q;<br /> <br /> s[t+4]:=base(p);<br /> <br /> t:=b-1; pc:=s[b+2]; b:=s[b+1];<br /> t:=b; pc:=s[b+2]; b:=s[b+1];<br /> Lớp KHMT K50<br /> <br /> 12<br /> <br /> 3<br /> <br /> 21/1/2010<br /> <br /> Máy ngăn xếp<br /> z<br /> <br /> Bộ lệnh<br /> <br /> op<br /> <br /> p<br /> <br /> Máy ngăn xếp<br /> <br /> q<br /> <br /> z<br /> <br /> op<br /> <br /> p<br /> <br /> q<br /> <br /> RC<br /> <br /> read one character into s[s[t]]; t:=t-1;<br /> <br /> AD<br /> <br /> Add<br /> <br /> t:=t-1; s[t]:=s[t]+s[t+1];<br /> <br /> RI<br /> <br /> Read Integer<br /> <br /> read integer to s[s[t]]; t:=t-1;<br /> <br /> SB<br /> <br /> Subtract<br /> <br /> t:=t-1; s[t]:=s[t]-s[t+1];<br /> <br /> WRC<br /> <br /> Write<br /> Character<br /> <br /> write one character from s[t]; t:=t-1;<br /> <br /> ML<br /> <br /> Multiply<br /> <br /> t:=t-1; s[t]:=s[t]*s[t+1];<br /> <br /> WRI<br /> <br /> Write Integer<br /> <br /> write integer from s[t]; t:=t-1;<br /> <br /> DV<br /> <br /> Divide<br /> <br /> t:=t-1; s[t]:=s[t]/s[t+1];<br /> <br /> WLN<br /> <br /> New Line<br /> <br /> CR & LF<br /> <br /> NEG<br /> <br /> Negative<br /> <br /> s[t]:=-s[t];<br /> <br /> CV<br /> <br /> Copy Top of<br /> s[t+1]:=s[t]; t:=t+1;<br /> Stack<br /> <br /> Lớp KHMT K50<br /> <br /> Lớp KHMT K50<br /> <br /> 13<br /> <br /> Máy ngăn xếp<br /> Bộ lệnh<br /> EQ<br /> NE<br /> GT<br /> LT<br /> GE<br /> LE<br /> <br /> op<br /> <br /> p<br /> <br /> t:=t-1;<br /> s[t]:=0;<br /> t:=t-1;<br /> Not Equal<br /> s[t]:=0;<br /> Greater<br /> t:=t-1;<br /> Than<br /> s[t]:=0;<br /> t:=t-1;<br /> Less Than<br /> s[t]:=0;<br /> Greater or t:=t-1;<br /> Equal<br /> s[t]:=0;<br /> Less<br /> or t:=t-1;<br /> Equal<br /> s[t]:=0;<br /> Equal<br /> <br /> q<br /> <br /> if s[t] = s[t+1] then s[t]:=1 else<br /> if s[t] != s[t+1] then s[t]:=1 else<br /> <br /> z<br /> <br /> if s[t] > s[t+1] then s[t]:=1 else<br /> if s[t] < s[t+1] then s[t]:=1 else<br /> if s[t] >= s[t+1] then s[t]:=1 else<br /> if s[t]