อ่านตอนก่อนหน้านี้ได้ที่ #Compiler
จากบทที่แล้ว เราอธิบายเรื่องการสร้าง Rule สำหรับภาษาไปแล้ว วันนี้จะมาต่อเรื่องการสร้างตัวที่จะไปอ่าน source code ของภาษาเราแล้วแปลงมันเป็น AST ให้
 |
| จำได้ไหมว่า AST คืออะไร หึหึ |
ก่อนจะรู้จักตัวแปลงตัวนั้น มารู้จักTokenกันก่อน
สมมุติว่าเรามีโค้ดภาษา Nartra แบบนี้ (ใครยังไม่รู้จักภาษานาร์ตรา กลับไปอ่านตอนเก่าเลยนะ 55+)
start MyFirstProgram :
let
x , y , z : Integer ;
c , r , : Char ;
begin
x := 1 ;
y := 100 ;
if x < y then
my_func( x , y , 1 )
end
end
สำหรับ คนที่เขียนโปรแกรมคงรู้สินะว่าเวลาเรามีไฟล์ที่เราเขียนด้วยภาษาโปรแกรมเช่น xxx.c (สำหรับภาษาซี) หรือจะเป็น xxx.java (สำหรับภาษาจาว่า) แน่นอนว่าเราสร้างภาษาใหม่ขึ้นมาเราก็ต้องกำหนดกันหน่อยว่า file-extension (นามสกุล) ของไฟล์ภาษาเราจะชื่ออะไร
เอาเป็นว่าชื่อ .nartra ละกัน ตรงๆ เลย
เวลา ที่เราอ่านไฟล์เข้ามาน่ะ มันจะอยู่ในรูปของตัวแปรประเภท "String" (ภาษาทางการคือ สายอักขระ แต่เรียกว่า ประโยคยาวๆ น่าจะเข้าใจกว่า) และแน่นอนว่า สตริงก็เป็นได้แค่สตริง มันทำอะไรไม่ได้เลย!
ดันนั้น จุดนี้เองที่ Token จะเข้ามามีบทกับเขาแล้ว
ภาษาโปรแกรมมี Syntax ที่ตายตัว เวลาโปรแกรมเมอร์เขียนโปรแกรมก็มักจะเขียนมาเป็นคำๆ ใช่มั้ยล่ะ ดังนั้นสิ่งแรกที่เราต้องทำคือตัดคำโดดๆ พวกนี้น่ะให้มันออกมาอยู่ในรูป ก้อนอะไรสักอย่างหนึ่ง
อย่างในตัวอย่างโค้ดนี้ เราก็เริ่มตัดไปเลย จาก [start] [MyFirstProgram] [:] [let] ไปเรื่อยๆ จนจบที่ตัวสุดท้ายเลย
พอตัดเสร็จ เราจะเรียกเจ้าตัวพวกนี้แหละว่าโทเค่น (Token) แต่ Token มีความพิเศษมากกว่าสตริงปกติคือมันจะประกอบด้วย kind + spelling (ถ้าเป็นสตริงจะมีแค่ spelling บอกว่าสะกดยังไงแค่นั้น)
แล้วอะไรคือ kind ?
สำหรับ ใครที่ไม่เข้าใจคำว่า kind งั้นขอเปลี่ยนเป็นคำว่า Type แทนละกัน น่าจะเข้าใจมากกว่า ... ถูกแล้ว มันคือตัวที่บอกว่าชิ้นส่วนประโยคนี้ (Tokenตัวนี้) เป็นTokenชนิดอะไรนั่นเอง
start --> kind = START let --> kind = LET : --> kind = COLON ; --> kind = SEMICOLON , --> kind = COMMA x --> kind = Identifier Integer --> kind = Identifier
ตัวอย่าง kind ที่เราเจอกันบ่อยๆ แต่ละสัญลักษณ์จะมีชื่อเรียกของตัวเองเลย ยกเว้นพวกคำที่ประกอบกันขึ้นมาเป็นชื่อ เช่น x, y, z, Int, Char ซึ่งส่วนใหญ่จะเป็นชื่อตัวแปรนั่นแล เจ้าพวกนี้เราจะเรียกรวมๆ ว่า Identifier นะ
**สำหรับ เรื่องการตัดสตริงยาวๆ ให้ออกมาเป็นชิ้นๆ Token นั้นทำได้ยังไงเราจะพูดกันต่อในบทต่อไปเรื่องการสร้าง Scanner สำหรับตัด Token ละกันนะ
แปลง source code เป็น AST ด้วย Parser
หลังจากเรามี Token (หลายตัวเลย) มาเรียงแถวต่อกันรอให้แปลงเป็น AST แล้ว ก็ต้องมีคนมาทำหน้าที่แปลงโดยอ่าน Token ไปทีละตัวแล้วค่อยๆ สร้าง AST ขึ้นมาซึ่งเราจะเรียกมันว่า "Parser" นั่นเอง
เรา สามารถเขียน Parser ตัวเดียวแล้วให้มันแปลงโค้ดทั้งก้อนเลยก็ยังได้ (เรียกว่า Single Pass Parser) โดยส่วนใหญ่เราจะไม่ทำอย่างนั้น แต่จะใช้เทคนิคที่เรียกว่า Multi Pass Parser
เอา ล่ะสิ ถ้าการแปลงโค้ดทั้งหมดทีเดียว Single Pass Parser มันไม่ดีนัก เราเลยมาใช้ Multi Pass Parser แทน ชื่อก็บอกอยู่แล้วว่า "มัลติ" แปลว่า หลายๆ สินะ?
งั้นมาดูกันว่าทำไมการแปลงแบบ multi มันถึงดีกว่าแบบ single
สมมุติว่าเราจะแปลง source --> AST แบบ single ละกัน
เนื่องจากภาษาเราชื่อ Nartra ดังนั้นเราขอสร้างพนักงานแปลงโค้ดชื่อ parseNartra ขึ้นมาหนึ่งคนละกัน
ใน บทแรกๆ เราพูดถึง AST ไปแล้วว่ามันคือโครงสร้างของโค้ดต้นฉบับเลย แต่อยู่ในรูปของ Tree ละนะ แล้วเป็น Tree ยังไงก็กลับไปดูบทที่แล้วตอนเรากำหนด rule ของภาษานั่นแหละ
แต่..!
ไม่ว่าโปรแกรมมันจะเล็กแค่ไหน ส่วนใหญ่ AST เนี่ยมันก็มีขนาดไม่ธรรมดาแน่นอน (หมายถึงใหญ่หลายชั้นเลยล่ะ)
เอาง่ายๆ เลยแค่เห็น rule ที่เราตั้งขึ้นมาก็ไม่อยากจะทำแล้ว เพราะมันเยอะมาก! ถ้าอย่างนั้นลองคิดถึงตอนเขียนโปรแกรมสิ ว่ามันจะยากขนาดไหนกัน
เขียนวิธีการแปลง rule ทั้งหมดให้อยู่ในฟังก์ชั่น parseNartra ตัวเดียวเลยคงไม่ใช่ความคิดที่ดีใช่ม๊ะ (ฮา)
เจ้า parseNartra ของเราจึงบอกว่า...
เจ้า parseNartra จึงเรียก parseDclns, parseFunctions, parseBody และ parseName (ที่ลืมวาดในรูปไป ขอโทด T__T)
แล้วทำไม parseNartra ถึงเรียกเจ้าพวกนี้มาล่ะ แค่ 4 ตัวด้วย
ถ้าเราย้อนกลับไปดู rule ของ Nartra ซึ่งเป็นตัวใหญ่ที่สุดของภาษาโปรแกรมจะพบว่า
Nartra ::= start Name : Dclns Functions Body
ตามกฏของ Nartra บอกไว้ว่ามันประกอบด้วย Name, Dclns, Functions กับ Body ... ส่วน [start] กับ [:] นี่เราถือว่าพวกมันอยู่ใส่วนของ start symbol หรือ พวกคำช่วย ไม่เกี่ยวกับโปรแกรมเราแต่อย่างใด
สรุปคือให้มองหาแค่ส่วน ที่เป็น non-terminal symbol เท่านั้นแหละ parseNartra จะเรียกใช้เจ้าพวกนี้ให้ทำหน้าที่ parse โค้ดส่วนย่อยๆ ให้
...ซึ่งเราจะมาดูกันต่อในครั้งหน้าในหัวข้อ parse + accept Token ล่ะ วันนี้แค่นี้ก่อนละกัน ^__^
