เมื่อได้ 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 แทนครับ
ผลลัพธ์
อ่านเนื้อหาที่เกี่ยวข้อง ก่อนหน้า
ไม่มีความคิดเห็น:
แสดงความคิดเห็น