อ่านตอนก่อนหน้านี้ได้ที่ #Compiler
จากบทความที่แล้ว เรารู้กันแล้วว่าคอมไพเล่อร์จะทำงานด้วย 3 ขั้นตอนโดยเริ่มจาก Syntactic Analysis ก่อน
Syntax แกรมม่าในภาษาโปรแกรม
ทุกภาษามีกฎของมัน แต่ถ้าเป็นภาษาโปรแกรม มันจะต่างจากภาษาที่คนใช้คุยกันสักหน่อย เพราะว่าเวลาเราคุยกันเอง ถ้าเราพูดผิดบางคำหรือบางประโยค อีกฝ่ายก็ยังเข้าใจได้ แต่คอมมันไม่ได้ฉลาดขนาดนั้น ดังนั้นการพิมพ์ ภาษาคอม ก็จำเป็นต้องพิมพ์ให้มันถูกต้องเป๊ะๆ ห้ามผิดแม้แต่ตัวเดียว
แล้ว เจ้ากฏในภาษาโปรแกรม (ที่ปกติเราจะเรียกกฏของภาษาว่าแกรมม่า) เนี่ยนะ มันมีชื่อว่า "Syntax" การจะพิมพ์ภาษาโปรแกรมอะไรก็ต่าง เราต้องรู้ซินแท็กของภาษานั้นซะก่อน
ตัวอย่างเช่น
ขอหยิบภาษาอังกฤษมาใช้ละกัน สมมุติเราจะว่างโครงซินแท็กของภาษาอังกฤษฉบับ mini !
Sentence = Subject Verb Object .
เรากำหนดขึ้นมาว่าประโยคเนี่ย มันต้องประกอบด้วย ประธาน + กริยา + กรรม แล้วตามด้วย . จุดฟูลสะต๊อป
อ่ะ! แบบนี้ก็แปลว่าอะไรที่เป็นประโยคได้ก็จะต้องประกอบด้วย 3 สิ่งนี้สินะ แต่มันยังไม่จบ!
เราต้องเขียนให้ละเอียดกว่านี้ถ้าเราจะสอนคอมไพเล่อร์ เพราะว่าตอนนี้มันยังไม่รู้ว่าอะไรบ้างที่เป็น Subject, Verb, Object ได้บ้าง
ดังนั้นเราต้องเพิ่มกฏลงไปอีก กลายเป็น
Sentence = Subject Verb Object . Subject = I หรือ a Noun หรือ the Noun Verb = is หรือ am หรือ have Object = Noun
เพิ่มกฏอีก 3 ตัวเข้าไปเพื่อบอกว่า Subject, Verb, Object เนี่ยมันเป็นอะไรได้บ้าง (สมมุติว่ามีคำแค่นี้ละกัน)
แล้วก็ ... แต่! อีกแล้ว คอมไพเล่อร์ยังไม่รู้เลยนะว่า Noun คืออะไร? แสดงว่าเราก็ต้องสอนมันด้วย ว่า Noun เนี่ยเป็นอะไรได้บ้าง
Sentence = Subject Verb Object . Subject = I หรือ a Noun หรือ the Noun Verb = is หรือ am หรือ have Object = Noun Noun = student หรือ book
เอาล่ะ พอแค่นี้ก่อนละกัน
ตอน นี้คือเราสร้างกฏให้กับภาษาเสร็จแล้ว เริ่มโดยการสร้างกฏอย่างง่ายก่อน แล้วก็ดูว่าแต่ละตัวมันไปต่อได้อีกไหม ถ้าไปต่อได้อีกก็แตกออกมาเป็นกฏย่อยๆ ไปเรื่อยๆ จนมาหยุดที่ตัวสุดท้ายที่แตกมันต่อไปไม่ได้แล้ว เราจะเรียกเจ้าพวกตัวสุดท้ายนี้ว่า "Terminal Symbols"
หลังจากยกตัวอย่างแบบเป็นภาษาคนกันเรียบร้อยแล้ว ลองมาดูในมุมมองคอมไพเล่อร์กันหน่อยว่ามันเป็นยังไงบ้าง
**ถ้าอ่านแล้วไม่รู้เรื่องก็ข้ามๆ ไปนะ เนื้อหามันซับซ้อน แต่พยายามจะเรียบเรียงให้ง่ายที่สุดละกัน
context free grammar
หรือเรียกย่อๆ ว่า CFG นั่นคือสิ่งที่เอาไว้บอกว่าภาษานี้มีโครงสร้าง syntax ยังไง เขียนผสมกันแบบไหนถึงจะถูกหลัก
ซึ่งมันประกอบด้วย 4 ส่วนคือ T N S P
- production rules - รูปแบบการผสม 3 ตัวบนนั่นแหละ ใช้กฏ BNF (Bachus-Naur Form) ซึ่งเดี๋ยวเราจะพูดกันต่อไป
- terminal symbol - เป็นส่วนเล็กที่สุด นั่นคือ word (คำ)
- non-terminal symbol - เป็นการผสมกันของส่วนเล็กๆ เป็นส่วนใหญ่หนึ่งก้อน เช่น phrases (วลี), clauses (อนุประโยค), sentences (ประโยค)
- start symbol - สัญลักษณ์เริ่มต้นที่ช่วยประกอบให้เต็มประโยค
Bachus-Naur Form
บาคัส-นอร์ ฟอร์ม หรือที่ต่อไปจะเรียก BNF พอ เป็นรูปแบบประโยคที่เราต้องคิดมาก่อนว่าภาษาของเรามี syntax เขียนยังไงได้บ้างตามสัญลักษณ์
LHS ::= RHS
LHS (Left-hand side) หมายถึงอะไรที่เราเขียนในฝั่งซ้าย จะใส่ non-terminal symbol ลงไป
RHS (Right-hand side) หมายถึงด้านขวา เป็นจุดที่บอกว่า non-terminal ทางฝั่งซ้ายตัวนี้น่ะ มันเกิดมาจากการรวมของอะไรได้บ้าง
ตัวอย่างเช่น
Command ::= single-Command Command ::= Command ; single-Command
หรือใช้สัญลักษณ์ | ในการบอกว่ามันเป็นได้หลายค่า ก็จะแปลงเป็นแบบนี้
Command ::= single-Command | Command ; single-Command
จาก การตั้ง BNF แบบนี้จะอ่านได้ว่า ถ้าเราจะสร้างสิ่งที่เรียกว่า "command" ขึ้นมาสักตัว มันจะต้องประกอบขึ้นมาจาก "single-command" 1 ตัว หรืออาจจะมาจาก command แล้วตามด้วย "single-command" แต่ว่าต้องคั่นด้วย ; นะ
มายกตัวอย่างกันหน่อยสำหรับคนที่ไม่เข้าใจ
ตัวอย่างเช่น ถ้าเรามีคำสั่ง A กับ B ถือว่าเป็น single-command อย่างละตัวละกันนะ
เราจะสามารถผสม Command ขึ้นมาได้เป็น
A //ตามกฏแรก 1 single-command สามารถถือว่าเป็น Command ได้ A ; B //ตามกฏที่ 2 บอกว่า ถ้าอยากได้มากกว่า 1 ตัว ก็เอา Command วางข้างหน้าแล้วตามด้วย ; A ; A ; B //เช่นกัน แต่ซ้อมไปอีกชั้น
ก็คือดูว่าอะไรเป็น Command ได้นั่นแหละ ก็เอามาผสมกันได้
แต่เขียนแบบนี้เขาบอกว่ามันเข้าใจยาก (แต่ส่วนใหญ่ที่สอนมา แบบหลังกว่าจะเข้าใจกัน ก็นานอยู่นะ ฮา) เขาจึงสร้าง EBNF ขึ้นมาอีก
Extended BNF
เพื่อที่จะเขียน BNF ได้อย่างง่ายขึ้น (จริงเหรอ?) เขาเลยสร้าง EBNF ขึ้นมาโดยใช้คอมเซ็ปว่า
EBNF = BNF + Regular Expression
ซึ่งเมื่อเราเอา Regular-Expression (ต่อไปจะเรียกสั้นๆ ว่า RegExp เร็กเอ็กซ์) มาใช้มันจะเหลือแค่
Command ::= ( single-Command ; ) * single-Command
เห็นมั้ย! ว่ามันยากขึ้น เอ๊ย...ง่ายขึ้น แต่นั่นก็ต่อเมื่อคุณรู้จักวิธีการเขียน RegExp แล้วเท่านั้น
งั้นเราก็มาดูกันก่อนดีกว่าว่า RegExp คืออะไร
Regular Expression
ถ้าคุณต้องการจะเขียนโปรแกรมเช็กว่า string ตัวนี้เป็นรูปแบบที่ถูกต้องของ e-mail รึเปล่าจะทำยังไง
สมมุติ ว่ารูปแบบที่เราต้องการเป็นแบบง่ายๆ คือนำหน้าด้วย A-Z แล้วก็ 0-9 อะไรแบบไหนก็ได้ ตามด้วย @ ก่อนจะเป็น A-Z, 0-9 อีกที (ชื่อเว็บ) ก่อนจะจบด้วย .com ประมาณนี้ละกัน
อืม เวลาอธิบายให้คนเข้าใจ บอกแบบนี้มันก็ได้ไง แต่ถ้าจะบอกคอมพิวเตอร์ล่ะ จะบอกยังไง
คำตอบก็คือใช้ RegExp ไง
โดยเราต้องรู้ก่อนนะ ว่าสัญลักษณ์ที่ใช้ใน RegExp มีอะไรบ้าง
*
ใช้สำหรับบอกว่า "0 ตัวหรือมากกว่านั้น" เช่นคุณต้องการบอกว่า อยากได้ A ที่นี่ กี่ตัวก็ได้นะ หรือไม่มีเลยก็ยังไง เราก็จะเขียนแบบนี้
A*
หมายความว่า ไม่ว่าจะเป็น
"A", "AAA", "AAAAAAAAA" หรือแม้แต่ " " ก็ยังได้
+
คล้ายกับ * แต่หมายความว่า "ตั้งแต่ 1 ตัวขึ้นไป" มันก็เหมือน * นั่นแหละ แต่ * จะยอมให้ " " (ค่าว่าง) ผ่านด้วย แต่ + จะไม่ยอม เพราะมันบอกว่าต้องการอย่างน้อย 1 ตัวอย่างไงล่ะ
A+
หมายความว่า
"A", "AAA", "AAAAAAAAA" จะผ่านหมด แต่สำหรับ " " จะไม่ผ่านนะ
?
ใช้สำหรับบอกว่า "0 ตัว หรือ 1 ตัวเท่านั้น"
A?
หมายความว่า
"A" หรือ " " เท่านั้น ได้แค่ 2 แบบนี้เท่านั้น แบบอื่นหมดสิทธิ
|
สำหรับโปรแกรมเมอร์ น่าจะคุ้นสัญลักษณ์นี้ เพราะมันคือ "OR" ที่แปลว่า "หรือ" นั่นแหละ
A | B
หมายความว่า
"A" ก็"ด้ หรือจะเป็น "B" ก็ยังได้นะ แต่ไม่เอา "AB" นะ เลือกสักตัวนึง
แล้วถ้าเป็นอย่างนี้
A B+ C ( DE )? F G*
จะแปลว่าอะไรน่ะ
อ่ะ ก็ลองมาแปลงกันดู
- มันขึ้นด้วย A ธรรมดา แปลว่าต้องขึ้นด้วย "A"
- ตามมาเป็น B+ ก็แปลว่าตัวต่อไปจะต้องมี "B" อย่างน้อย 1 ตัว แต่มีมากกว่านั้นได้นะ
- ตามด้วย C ก็คือ "C" นั่นแหละ ไม่มีอะไรพิเศษ
- ทีนี้เรามี D กับ E อยู่ใน (...) แปลว่าต้องคิดมันเป็นชุดเดียวกัน แล้วเจ้าสองตัวนี้มี ? ต่อก็แปลว่าจะมี "DE" หรือ ไม่มีเลยก็ได้ล่ะ
- ตามด้วย F 1ตัวเป็น "F"
- แล้วจบด้วย G กี่ตัวก็ได้ หรือจะไม่มีเลยก็ได้ ไม่แคร์ (ฮา)
งั้น ค่าที่เป็นไปได้จากการเขียน RegExp แบบนี้ก็ประมาณนี้
A BBBBB C DE F G A B C F A BB C DE F GGGGGGGG
ส่วนพวกที่ไม่ตรงรูปแบบก็จะเป็นประมาณ
A B C D F G //DE ต้องมาด้วยกันเพราะอยู่ใน (...) A C DE DE F //B ต้องมีอย่างน้อน 1 ตัว แต่นี่หายไปเลย แล้ว DE มีอย่างมากได้แค่ 1 ตัว นี่มาซะ2
เอาล่ะ งั้นกลับมาที่ EBNF ต่อ
Extended BNF (ต่อ)
หลังจากเรารู้แล้วว่า RegExp คืออะไร ก็คงอ่านออกแล้วว่า EBNF ข้างล่างหมายถึงอะไร
Command ::= ( single-Command ; ) * single-Command
แปลว่า Command นั้นจะประกอบขึ้นมาจาก ["single-Command" ตามด้วย ";"] กี่ชุดก็ได้เพราะใช้ * ก่อนจะจบด้วย "single-Command" 1 ตัว
เช่น ถ้าเราบอกว่า single-Command ของเราคือ x=1 หรือ x=2 หรือ x=3
เอามาผสมกันก็จะได้ Command แบบนี้
x=1 x=1 ; x=2 x=1 ; x=2 ; x=3
เอาอีกตัวอย่างหนึ่งละกัน ลองมาเขียน EBNFของ "Identifier" กันดู
โอเค ก่อนจะเขียนได้ เราต้องรู้ก่อนว่าอะไรคือ Identifier ... มันคือตัวที่เอาไว้อ้างถึงอะไรที่เราสนใจ หรือพูดง่ายๆ ก็คือตัวแปรนั่นเอง
สำหรับ คนที่เคยเขียนโปรแกรมมาก่อน คงรู้แล้วสินะ (ถือว่ารู้แล้วนะ) ว่าการจะประกาศตัวแปรหรือตั้งชื่อตัวแปรนี่แหละ จะต้องใช้สัญลักษณ์มาประกอบกัน ภาษาโปรแกรมส่วนใหญ่มักจะอนุญาตแค่
- ขึ้นด้วยตัวอักษร A-Z
- หลังจากนั้นจะเป็นตัวอักษรหรือตัวเลขก็ได้
- สามารถใช้ _ ประกอบด้วยได้
ตัวอย่างตัวแปรที่เจอบ่อยๆ ก็เช่น x, y, num1, total_price อะไรประมาณนี้
งั้นมาดูกัน!
ขั้นแรกเลย เรากำหนด EBNF แบบคร่าวๆ ขึ้นมาก่อน
Identifier ::= ( Letter | _ ) ( Letter | Digit | _ ) *
กฏง่ายๆ คือการตั้งชื่อตัวแปรต้องขึ้นด้วย ตัวอักษร หรือจะเป็น _ ก็ได้ แล้วตามด้วย ตัวอักษร หรือ ตัวเลข หรือ _ กี่ตัวก็ได้
แต่ก็ยังไม่จบแค่นั้น เพราะเราต้องบอกด้วยว่า Letter กับ Digit ที่เขียนไปน่ะ มันประกอบมาจากอะไรได้บ้าง
สุดท้ายก็จะออกมาเป็นแบบนี้
Identifier ::= ( Letter | _ ) ( Letter | Digit | _ ) * Letter ::= a | b | c | ... | z Digit ::= 0 | 1 | 2 | ... | 9
แบบนี้ถึงจะเสร็จ เพราะว่าพวก a, b, c กับ 0, 1, 2 คือตัวเล็กสุด มันแตกไม่ได้แล้ว
บทนี้เอาแค่นี้ก่อนนะ เดี๋ยวบทต่อไปเราจะมาพูดกันต่อเรื่อง "Syntactic Analysis Parsing" หรือการร่างโครงสร้างภาษาโปรแกรมของเราแบบละเอียดขึ้น จะได้รู้ว่า Command, Expression, Identifier, Type-denoter พวกนั้นคืออะไรกัน
