วันอังคารที่ 21 ตุลาคม พ.ศ. 2557

สอนเขียนโปรแกรม Compiler เพื่อแสดงผล Animation ด้วยภาษา JAVA เบื้องต้น (Part 2 Parser)

จาก Part 1 เราได้ส่วนของ Scanner ไปแล้ว ต่อไปจะเป็นส่วนที่สอง คือ Parser ซึ่ง Parser ก็คือตัวที่จะทำการประมวลผล Token ที่รับเข้ามาว่ามันถูกจัดเรียงได้อย่างถูกต้องตามหลักไวยากรณ์ของภาษาโปรแกรมนั้นๆหรือไม่ เพื่อที่จะนำไปใช้ในส่วนที่ 3 (SyntaxTree) ต่อไป

ลิ้งค์รายละเอียด part 2 https://www.cs.duke.edu/courses/spring12/cps140/assign/proj2all.pdf

2. Parser


ในการประมวลผลว่า code ของโปรแกรมถูกต้องตามหลักไวยากรณ์หรือไม่ เราจะใช้วิธีการที่เรียกว่า SLR Parser มีตัวอย่างง่ายๆดังนี้ http://chulee.wikispaces.com/file/view/PL4.pdf/362081836/PL4.pdf

จากตัวอย่างจะเห็นได้ว่ามีสิ่งที่ต้องเตรียมในการทำ SLR Parser คือ เราจะต้องมี grammar หรือ rule ซึ่งก็คือกฏของไวยากณ์ในโปรแกรม และอีกอย่างหนึ่งก็คือ ตาราง parsetable ซึ่งแสดงอยู่ในเอกสารรายละเอียดของส่วนที่ 2 ดังนี้

Grammar

(0) P’ → P

(1) P → z i i b L t

(2) L → S ;

(3) L → L S ;

(4) S → c v i i D

(5) S → m v i i D

(6) S → h i i

(7) S → o v

(8) S → o v i

(9) S → l v

(10) S → r i L d

(11) D → n

(12) D → s

(13) D → e

(14) D → w

ParseTable

ในส่วนของ ParseTable จากเอกสารจะเห็นว่าเป็นตารางซึ่งยากต่อการ copy ไปใช้ต่อ ดังนั้น ParseTable จะเแปลงเป็นไฟล์แยกออกมาต่างหากเพื่อให้ง่ายต่อการ copy text เพื่อนำไปใช้เขียนโปรแกรมต่อ โดยมี url ดังลิ้งค์ด้านล่างนี้
https://www.cs.duke.edu/courses/spring12/cps140/assign/parsedata

เริ่มเขียน Code


1. สร้างคลาสชื่อว่า Parser โดยมีค่า Attribute ดังนี้

Untitled

 

  • private Stack stack = new Stack(); แสต็กเอาไว้เก็บค่าระหว่างขั้นตอนการประมวลผลด้วยวิธี SLR Parser ซึ่งจะเก็บ Object หลายประเภทจึงไม่ใส่ว่าเป็น stack ชนิดใด (เป็น stack ที่เก็บ Object)

  • private ArrayList<Token> tokens; ใช้เก็บ ArrayList ที่ได้จากการทำ Scanner ในส่วนที่ 1

  • private ArrayList<String> grammars = new ArrayList<>(); ใช้ในการเก็บกฏไวยากรร์เพื่อใช้ในการทำ SLR Parser

  • private ArrayList<String> rulesOutput = new ArrayList<String>(); ใช้เก็บ Output ที่แสดงผลว่า แต่ละ step ในการทำ SLR Parser ใช้กฏไวยากรณ์ข้อใด

  • private ArrayList<String> derivationOutput = new ArrayList<String>(); ใช้เก็บ Output ที่แสดงผลการ Derivation ในแต่ละ step ในการทำ SLR Parser

  • private HashMap<String, Integer> parseTableHeader = new HashMap<String, Integer>(); ใช้เก็บ index ส่วนหัวของตาราง ParseTable ที่เป็นตัวอักษร ให้เป็นการเข้าถึง index นั้นด้วยตัวเลขแทน

  • private String[][] parseTable = ..... // ใช้เก็บข้อมูลของตาราง ParseTable ที่ถูกแปลงจาก  https://www.cs.duke.edu/courses/spring12/cps140/assign/parsedata ให้มาอยู่ในรูปของ Array2 มิติ ซึ่งมีผลดีคือสามารถช่วยให้เราเขียนโปรแกรมได้สั้นลงอย่างมาก เพราะสามารถเข้าถึงข้อมูลในแต่ละ index ได้ทันที
    ซึ่งมีวิธีการแปลงคือให้ดูจากเอกสาร https://www.cs.duke.edu/courses/spring12/cps140/assign/proj2all.pdf หน้า 6-7 คือให้เขียนตารางในหน้า 6 ให้อยู่ในรูปของ Array 2 มิติ แล้วนำ ข้อมูลในหน้า 7 มาต่อท้าย และส่วนไหนที่เป็นช่องว่างให้แทนด้วยเครื่องหมาย "&" สุดท้ายแล้วจะได้ Array2 มิติที่มีข้อมูลดังนี้

  • private String[][] parseTable = { { "&", "z", "i", "b", "t", ";", "c", "v", "m", "h", "o", "l", "r", "d", "n", "s", "e", "w", "$", "P", "L", "S", "D" },{ "0", "s2", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "1", "&", "&", "&" },{ "1", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "acc", "&", "&", "&", "&" },{ "2", "&", "s3", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "3", "&", "s4", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "4", "&", "&", "s5", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "5", "&", "&", "&", "&", "&", "s8", "&", "s9", "s10", "s11", "s12", "s13", "&", "&", "&", "&", "&", "&", "&", "6", "7", "&" },{ "6", "&", "&", "&", "s14", "&", "s8", "&", "s9", "s10", "s11", "s12", "s13", "&", "&", "&", "&", "&", "&", "&", "&", "15", "&" },{ "7", "&", "&", "&", "&", "s16", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "8", "&", "&", "&", "&", "&", "&", "s17", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "9", "&", "&", "&", "&", "&", "&", "s18", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "10", "&", "s19", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "11", "&", "&", "&", "&", "&", "&", "s20", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "12", "&", "&", "&", "&", "&", "&", "s21", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "13", "&", "s22", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "14", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "r1", "&", "&", "&", "&" },{ "15", "&", "&", "&", "&", "s23", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "16", "&", "&", "&", "r2", "&", "r2", "&", "r2", "r2", "r2", "r2", "r2", "r2", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "17", "&", "s24", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "18", "&", "s25", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "19", "&", "s26", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "20", "&", "s27", "&", "&", "r7", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "21", "&", "&", "&", "&", "r9", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "22", "&", "&", "&", "&", "&", "s8", "&", "s9", "s10", "s11", "s12", "s13", "&", "&", "&", "&", "&", "&", "&", "28", "7", "&" },{ "23", "&", "&", "&", "r3", "&", "r3", "&", "r3", "r3", "r3", "r3", "r3", "r3", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "24", "&", "s29", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "25", "&", "s30", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "26", "&", "&", "&", "&", "r6", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "27", "&", "&", "&", "&", "r8", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "28", "&", "&", "&", "&", "&", "s8", "&", "s9", "s10", "s11", "s12", "s13", "s31", "&", "&", "&", "&", "&", "&", "&", "15", "&" },{ "29", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "s33", "s34", "s35", "s36", "&", "&", "&", "&", "32" },{ "30", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "s33", "s34", "s35", "s36", "&", "&", "&", "&", "37" },{ "31", "&", "&", "&", "&", "r10", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "32", "&", "&", "&", "&", "r4", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "33", "&", "&", "&", "&", "r11", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "34", "&", "&", "&", "&", "r12", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "35", "&", "&", "&", "&", "r13", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "36", "&", "&", "&", "&", "r14", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" },{ "37", "&", "&", "&", "&", "r5", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&", "&" } };


2. สร้าง Constructor โดยให้รับ ArrayList ที่ได้จากการทำ Scanner ในส่วนที่ 1 และใน constructor นี้จะทำการ instance variable ต่างๆที่จำเป็นในการทำ SLR Parser ด้วย

Untitled

 

เมื่อรับ ArrayListToken มาแล้วให้เพิ่มสมาชิกเข้าไปอีก 1 ตัว คือ "$" เพื่อใช้ในการทำ SLR Parser หลังจากนั้นให้ เพิ่มกฏของไวยากรณ์เข้าไปใน grammars ตามลำดับโดยดูจากรูปนี้ หรือตามเอกสารในส่วนที่ 2

Untitled

ต่อไปให้เพิ่มสมาชิกลงใน parseTableHeader โดยให้ดูจาก array2มิติ parseTable แถวที่ 0 ว่ามีชื่อว่าอะไรบ้าง (ไม่นับรวมส่วนที่เป็นช่องว่าง) ให้กำหนดค่าตัวเลขลงไป โดยให้ใช้ตัวอักษาเป็น key ของ hashmap โดยตัวเลขที่เพิ่มเข้าไปก็คือ index ของตัวอักษรตำแหน่งนั้น อย่างในโปรแกรม Mouse Cat นี้มีสมาชิก HashMap ทั้งหมด 22 ตัว  และเมื่อเพิ่มเสร็จแล้วก็เป็นการจบ constructer

Untitled

3. การทำ SLR Parser

สร้างเมธอดชื่อว่า checkSyntax เพื่อเริ่มทำ SLR Parser โดยอ้างอิงจากอัลกอริทึมจะได้ code ประมาณนี้ (อาจจะมีบัค)

Untitled

 

Untitled

 

สร้างฟังก์ชัน shift และ reduce

Untitled

 

Untitled

 

 

การแสดงผล Output ต้อง พิมพ์จากด้านหลังไปด้านหน้าทั้ง ruleOutput และ derivationOutput เพื่อที่จะให้แสดงผลลัพธ์ได้อย่างถูกต้อง

Untitled

 

ทดสอบ Input Output


ตัวอย่าง code ทดสอบจากลิ้งค์นี้ https://www.cs.duke.edu/courses/spring12/cps140/assign/studentdata/

Untitled

Untitled

 

Output แบบเต็ม

code

size 10 10
begin
mouse jerry 8 5 west ;
hole 7 7 ;
cat tom 5 5 north ;
move jerry ;
clockwise jerry ;
clockwise jerry ;
clockwise jerry ;
halt

Output

P -> size 10 10 begin L halt
L -> L S ;
S -> clockwise jerry
L -> L S ;
S -> clockwise jerry
L -> L S ;
S -> clockwise jerry
L -> L S ;
S -> move jerry
L -> L S ;
S -> cat tom 5 5 D
D -> north
L -> L S ;
S -> hole 7 7
L -> S ;
S -> mouse jerry 8 5 D
D -> west
size 10 10 begin L halt
size 10 10 begin L S ; halt
size 10 10 begin L clockwise jerry ; halt
size 10 10 begin L S ; clockwise jerry ; halt
size 10 10 begin L clockwise jerry ; clockwise jerry ; halt
size 10 10 begin L S ; clockwise jerry ; clockwise jerry ; halt
size 10 10 begin L clockwise jerry ; clockwise jerry ; clockwise jerry ; halt
size 10 10 begin L S ; clockwise jerry ; clockwise jerry ; clockwise jerry ; halt
size 10 10 begin L move jerry ; clockwise jerry ; clockwise jerry ; clockwise jerry ; halt
size 10 10 begin L S ; move jerry ; clockwise jerry ; clockwise jerry ; clockwise jerry ; halt
size 10 10 begin L cat tom 5 5 D ; move jerry ; clockwise jerry ; clockwise jerry ; clockwise jerry ; halt
size 10 10 begin L cat tom 5 5 north ; move jerry ; clockwise jerry ; clockwise jerry ; clockwise jerry ; halt
size 10 10 begin L S ; cat tom 5 5 north ; move jerry ; clockwise jerry ; clockwise jerry ; clockwise jerry ; halt
size 10 10 begin L hole 7 7 ; cat tom 5 5 north ; move jerry ; clockwise jerry ; clockwise jerry ; clockwise jerry ; halt
size 10 10 begin S ; hole 7 7 ; cat tom 5 5 north ; move jerry ; clockwise jerry ; clockwise jerry ; clockwise jerry ; halt
size 10 10 begin mouse jerry 8 5 D ; hole 7 7 ; cat tom 5 5 north ; move jerry ; clockwise jerry ; clockwise jerry ; clockwise jerry ; halt
size 10 10 begin mouse jerry 8 5 west ; hole 7 7 ; cat tom 5 5 north ; move jerry ; clockwise jerry ; clockwise jerry ; clockwise jerry ; halt

จบการทำงานของส่วนที่ 2 (Parser)


ต่อส่วนที่ 3(SyntaxTree)
เขียนโดย ที่
ป้ายกำกับ: , , , , ,

2 ความคิดเห็น:

สมัครสมาชิก: ส่งความคิดเห็น (Atom)