วันพฤหัสบดีที่ 3 มีนาคม พ.ศ. 2554

Compiler : Code Generator

       เมื่อได้ intermediate code หรือโค้ดกลางจากกระบวนการ Parser กระบวนการ Code Generator จะสร้างผลลัพธ์สุดท้าย (target code) เป็นภาษาเครื่องหรือภาษาใดๆอย่างไรนั้น ก็ขึ้นอยู่กับข้อตกลงของอาจารย์ผู้สอนหรือตามแต่ความต้องการของผู้เขียนโปรแกรมเอง และในขณะที่ผมเรียนเรื่องนี้นั้น มีข้อตกลงร่วมกันดังนี้

ตัวอย่าง *, 2, 1, t0 จะแปลงเป็น
1. LOAD  R1  2
2. MUL  R1  1
3. STORE  R1  t0

ตัวอย่าง /, t0, 3, t1 จะแปลงเป็น
4. LOAD  R1  t0
5. DIV  R1  3
6. STORE  R1  t1

ตัวอย่าง +, 3, t1, t2 จะแปลงเป็น
7. LOAD  R1  3
8. ADD  R1  t1
9. STORE  R1  t2

ตัวอย่าง -, t2, 1, t3 จะแปลงเป็น
10. LOAD  R1  t2
11. SUB  R1  1
12. STORE  R1  t3

ตัวอย่าง =, t3,  , a จะแปลงเป็น
13. LOAD  R1  t3
14. STORE  R1  a

       จากตัวอย่างข้างต้นนี้ intermediate code ทั้งหมดสร้างจาก source code เดียวกัน ผมตั้งใจแยกมันออกเป็นตัวอย่างย่อยๆซึ่งจะสังเกตว่า เราใช้รีจิสเตอร์พักค่าหนึ่งตัวชื่อว่า R1 (แล้วแต่ข้อตกลง) และเทียบเครื่องหมาย
* เป็น MUL
/ เป็น DIV
+ เป็น ADD
- เป็น SUB
= เป็น STORE
หากมีเครื่องหมายอื่นๆ ก็แล้วแต่จะใช้คำว่าอย่างไร นอกเหนื่อจากนั้นรูปแบบก็คล้ายคลึงกันพร้อมกับใส่หมายเลขบรรทัดไปด้วย...

       เพื่อนๆที่เคยเรียนภาษา assembly (ขณะที่ผมเรียนเขียนด้วย MASM32 : Microsoft assembler 32 bit) คงจำรูปแบบคำสั่งควบคุมจำพวก if หรือ while ได้บ้าง การสร้าง intermediate code อาจแตกต่างออกไปเล็กน้อย เช่น

ตัวอย่าง source code เขียนเป็น if ( a > 10 ) { a = a - 1; }
จะถูกสร้างเป็น intermediate code ดังนี้ (แล้วแต่ข้อตกลง)
>, a, 10, t0
JLE, t0,  , label_end
-, a, 1, t1
=, t1,  , a
LBL,  ,  , label_end

       หมายความว่า ผลการเปรียบเทียบระหว่างตัวแปร a และค่าคงที่ 10 จะได้ผลลัพธ์ไปเก็บไว้ ณ ตัวแปรชื่อ t0 (ค่านี้อาจเป็น จริง หรือ เท็จ ก็ได้) ถัดมาคำสั่ง JLE จะอ่านค่าตัวแปร t0 ...เมื่อ "a น้อยกว่าหรือเท่ากับ 10" จริง (คือ t0 มีค่าเป็นจริง) คอมพิวเตอร์จะทำคำสั่ง JLE เป็นเหตุให้กระโดดไปทำคำสั่ง ณ ตำแหน่ง LBL ที่ชื่อ label_end (ที่เขียนว่า LBL,  ,  , label_end) ทันทีโดยข้ามสองคำสั่งต่อไปนี้
-, a, 1, t1
=, t1,  , a
...แต่หากเป็นตรงกันข้ามเพราะ "a มากกว่า 10" จริง (คือ t0 มีค่าเป็นเท็จ) คอมพิวเตอร์จะไม่สนใจคำสั่ง JLE ผลคือคำสั่ง
-, a, 1, t1
=, t1,  , a
จะถูกทำก่อนแล้วจึงค่อยไปทำคำสั่ง ณ ตำแหน่ง label_end เป็นลำดับ (สุดท้าย) ต่อไป...

ตัวอย่าง source code เขียนเป็น while ( a > 10 ) { a = a - 1; }
จะถูกสร้างเป็น intermediate code ดังนี้ (แล้วแต่ข้อตกลง)
LBL,  ,  , label_begin
>, a, 10, t0
JLE, t0,  , label_end
-, a, 1, t1
=, t1,  , a
JMP,  ,  , label_begin
LBL,  ,  , label_end

       intermediate code ตัวอย่างข้างต้นไม่ต่างจากตัวอย่างก่อนหน้ามากนัก เพียงแต่เพิ่มการวนรอบ (JMP) กลับไปตรวจสอบเงื่อนไข a > 10 นั้นอยู่เรื่อย จนกระทั่งเงื่อนไขดังกล่าวจะเป็นเท็จจึงยุติลง... (หรือกล่าวว่าทำคำสั่งถัดไป ณ ตำแหน่ง label_end (ที่เขียนว่า LBL,  ,  , label_end))

       อัลกอริทึมที่ใช้สำหรับกระบวนการ Code Generator มีอยู่หลายวิธี (ขอภัย เพราะผมลืมไปเกือบหมดแล้ว) เมื่อยึดเอา intermediate code จากตัวอย่างล่าสุดข้างต้น ผมเลือกใช้วิธีการที่มีรูปแบบที่แบ่งออกเป็นสองขั้นตอนใหญ่ๆ ดังนี้
- ขั้นตอนแรก บันทึกชื่อของตำแหน่ง (label) จากคำสั่ง LBL เท่านั้น โดยนับบรรทัดไปพร้อมๆกัน เริ่มจาก
---- ให้ตัวแปรชื่อ countLine คอยนับจำนวนบรรทัดที่จะถูกแปลงเป็นโค้ดเป้าหมาย เริ่มต้นค่าเป็นหนึ่ง
---- เมื่ออ่านมาพบ LBL,  ,  , label_begin ให้บันทึกชื่อ label_begin ไว้พร้อมกับระบุหมายเลขบรรทัดไว้เป็น 1
---- เมื่ออ่านมาพบ >, a, 10, t0 ค่าของ countLine จะเพิ่มขึ้นอีก 3 รวมแล้วเท่ากับ 4 (เลขสามนั้นมาจาก intermediate code นี้หนึ่งคำสั่ง ถูกแปลงเป็นโค้ดเป้าหมายจำนวนสามคำสั่ง (หรือสามบรรทัด) นั้นเอง)
---- เมื่ออ่านมาพบ JLE, t0,  , label_end ค่าของ countLine จะเพิ่มขึ้นอีก 1 รวมแล้วเท่ากับ 5 (เพราะมันจะถูกแปลงเป็นโค้ดเป้าหมายเพียงหนึ่งคำสั่ง)
---- เมื่ออ่านมาพบ -, a, 1, t1 ค่าของ countLine จะเพิ่มขึ้นอีก 3 รวมแล้วเท่ากับ 8
---- เมื่ออ่านมาพบ =, t1,  , a ค่าของ countLine จะเพิ่มขึ้นอีก 2 รวมแล้วเท่ากับ 10
---- เมื่ออ่านมาพบ JMP,  ,  , label_begin ค่าของ countLine จะเพิ่มขึ้นอีก 1 รวมแล้วเท่ากับ 11
---- เมื่ออ่านมาพบ LBL,  ,  , label_end ให้บันทึกชื่อ label_end ไว้พร้อมกับระบุหมายเลขบรรทัดไว้เป็น 11

- ขั้นตอนที่สอง อ่าน intermediate code ใหม่อีกรอบ โดยไม่สนใจคำสั่ง LBL แต่กลับสนใจชื่อ label ของคำสั่ง jump ต่างๆแทน (ในที่นี้คำสั่ง jump ได้แก่ JLE และ JMP)
---- ตั้งค่าตัวแปร countLine เป็นหนึ่งอีกครั้ง
---- เมื่ออ่านมาพบ LBL,  ,  , label_begin ให้เลยผ่านไป
---- เมื่ออ่านมาพบ >, a, 10, t0 ให้แปลงเป็นโค้ดเป้าหมาย พร้อมกับระบุหมายเลขบรรทัด
1. LOAD  R1  a
2. GT  R1  10
3. STORE  R1  t0

---- เมื่ออ่านมาพบ JLE, t0,  , label_end ให้นำชื่อ label_end เทียบหาชื่อที่ตรงกันจากชื่อ label ทั้งหมดที่ได้บันทึกไว้ในขั้นตอนแรก แล้วนำหมายเลขบรรทัดที่บันทึกไว้พร้อมกันแปลงเป็นโค้ดเป้าหมาย
4. JLE     11
---- เมื่ออ่านมาพบ -, a, 1, t1
5. LOAD  R1  a
6. SUB  R1  1
7.STORE  R1  t1

---- เมื่ออ่านมาพบ =, t1,  , a
8. LOAD  R1  t1
9. STORE  R1  a

---- เมื่ออ่านมาพบ JMP,  ,  , label_begin
10. JMP     1

ดาวน์โหลดโปรแกรม Compiler ที่เขียนด้วย Grammar 3 (Run ด้วย NetBeans IDE) ซึ่งเพิ่มเติมกระบวนการ Code Generator

ทดสอบ
       รูปด้านล่างนี้แสดงผลการทดสอบ การสร้าง target code โดยใช้ intermediate code ตามตัวอย่างล่าสุดข้างต้น (ของบทความหน้านี้) พร้อมผลลัพธ์ แต่ถ้าเพื่อนๆต้องการให้แสดงผลลัพธ์จาก intermediate code ปกติของ grammar 3 ให้เพื่อนๆยกเลิก comment บรรทัดที่ 36 และใส่ comment บรรทัดที่ 35 แทนครับ

ผลลัพธ์

อ่านเนื้อหาที่เกี่ยวข้อง ก่อนหน้า

ไม่มีความคิดเห็น:

แสดงความคิดเห็น