ก่อนเข้าสู่ตัวอย่างวิธีการออกแบบ รบกวนเพื่อนๆอ่านบทความหน้านี้ก่อนครับ Compiler : ออกแบบ Grammar และขออนุญาตใช้ความคิดเห็นของเพื่อนชื่อ boyle หรือเพื่อน บอย เป็นโครงหลักของเนื้อหานะครับ อ่านความคิดเห็นของ boyle (อยู่ด้านล่างของหน้า)
ต่อไปนี้เป็นข้อตกลงใหม่ระหว่างผมกับเพื่อนๆนะครับ เนื่องจากการเขียนเครื่องหมาย < และ > ค่อนข้างลำบากสำหรับผมนิดหน่อย (เพราะต้องเขียนหน้า html และพอ update หน้าเพจแล้วมันเช้าใจว่าผมเขียนแท็ก html จึงแสดงผลผิดเพี้ยน) เอาเป็นว่า
- สำหรับ non-terminal ผมจะเขียนด้วยพิมพ์ใหญ่ เช่น START, VARIABLE เป็นต้น
- สำหรับ terminal ผมจะเขียนด้วยพิมพ์เล็กมีเครื่องหมาย " และ " ครอบด้วย เช่น "start", "variable" เป็นต้น
- ใช้เครื่องหมาย ::= แทนการผลิตจาก non-terminal เป็น terminal นะครับ (เพื่อนๆจะใช้เครื่องหมายลูกศร -> ก็ได้)
เพื่อนๆหลายคนสงสัยว่าเมื่อเริ่มออกแบบ grammar นั้นควร ออกแบบอย่างไร ควรเริ่มจากเปลี่ยน source code ตัวอย่างเป็น grammar ดีไหม หรือจาก grammar เป็น source code ดีกว่า...อื่ม อันนี้แล้วแต่ความเข้าใจและความถนัดของแต่ละคนครับ (ยิ้ม)
ส่วนตัวผมแล้วต้องใช้ทั้งสองแบบ กล่าวคือใช้แบบ source code เปลี่ยนเป็น grammar ก่อนห้าสิบเปอร์เซ็นต์ แล้วที่เหลือก็ใช้แบบ grammar เปลี่ยนเป็น source code ครับ เพราะอย่างไรก็ต้องจินตนาการถึง source code อื่นๆที่สามารถเกิดขึ้นได้อยู่ดี หรือกล่าวว่าเราไม่สามารถเขียน source code ทั้งหมดออกมาได้ แต่สามารถกำหนดรูปแบบของมันได้โดยใช้ grammar นั่นเอง เอาละครับมาเริ่มกันเลยนะ (ยิ้มให้อีกแล้วนะ)
ตัวอย่างที่ 1
var a
ง่ายๆก่อนนะครับ source code นี้เริ่มต้นด้วยคำว่า var แล้วตามด้วยตัวแปรชื่อ a แน่นอนว่าต่อไป a อาจเปลี่ยนเป็น b หรือ c หรือ love_you อะไรก็ได้จริงไหมครับ (ก็มันเป็นชื่อตัวแปร) ส่วนคำว่า var นั่นไม่เปลี่ยนแปลงเพราะมันเป็นคำสงวน ดังนั้นหากเป็นผมจะออกแบบ grammar ดังนี้ครับ
START ::= "var" VARIABLE
VARIABLE ::= LETTER { LETTER | DIGIT | "_" }
LETTER ::= a | b | c | ... | x | y | z | A | B | C | ... | X | Y | Z
DIGIT ::= 0 | 1 | 2 | ... | 7 | 8 | 9
***หมายเหตุ
- เครื่องหมาย { และ } หมายถึงผลิตเป็นจำนวนเท่าใดก็ได้ หยุดได้ตามต้องการ หรือเรียกว่า zero or more
- เครื่องหมาย | หมายถึง หรือ
ตัวอย่างที่ 2
var a, b, c : int
source code ข้างต้นนี้เพิ่มการประกาศแบบหลายตัวในครั้งเดียว และยังกำหนดชนิดข้อมูล (type) ได้อีกต่างหาก เช่น int หรือ float หรือ double หรือ หรือ char หรือ string หรือ bool เป็นต้น (จินตนานการเอานะครับ ว่ามันอาจเป็นอะไรได้อีก ก็กำหนดลงใน grammar เลย) จาก grammar ในตัวอย่างที่ 1 เราเพิ่ม grammar ส่วนที่เหลือดังนี้ครับ
START ::= "var" VARIABLE { "," VARIABLE } ":" TYPE
TYPE ::= "int" | "float" | "double" | "char" | "string" | "bool"
ตัวอย่างที่ 3
b:real
c: bool
d : string
ตัวอย่างนี้เราสามารถประกาศตัวแปรหรือกำหนดชนิดข้อมูลให้กับตัวแปรได้ภายหลังครับ ดังนั้นผมจึงเปลี่ยนแปลง grammar ในตัวอย่างที่ 2 เสียก่อน (เขียนแต่หลักๆนะครับ) แล้วเพิ่ม grammar ของตัวอย่างที่ 3 เข้าไปดังนี้
START ::= DECLARE1 | { DECLARE2 }
DECLARE1 ::= "var" VARIABLE { "," VARIABLE } ":" TYPE
DECLARE2 ::= VARIABLE ":" TYPE
grammar ข้างต้นนี้เราสามารถกระทำตาม source code ของตัวอย่างที่ 3 ได้ไม่จำกัดจำนวนครั้ง ทว่าสำหรับตัวอย่างที่ 2 นั้นสามารถกระทำได้เพียงครั้งเดียว ดังนั้นหากต้องการให้สามารถประกาศตัวแปรในตัวอย่างที่ 2 ได้ไม่จำกัดจำนวนครั้งเช่นกัน จึงปรับปรุงโดยเพิ่มเครื่องหมาย { } ครับ
START ::= { DECLARE1 } | { DECLARE2 }
ตัวอย่างที่ 4
While() do; ตามด้วย source code อื่นๆแล้วจบด้วย end;
เข้าสู่ while ลูปแล้วนะครับ หมายความว่าหากเป็นโปรแกรมจริงๆมันจะกระทำตามรอบที่ถูกกำหนดเป็น expression หรือเงื่อนไข (condition) ดังนั้นเราอาจออกแบบ grammar ได้ดังนี้
START ::= VARIABLE_DECLARATION | BODY
VARIABLE_DECLARATION ::= { DECLARE1 } | { DECLARE2 }
BODY ::= { WHILE }
WHILE ::= "while" "(" EXPR ")" "do" ";" STATEMENT "end" ";"
***หมายเหตุ
- EXPR หมายถึง expression หมายถึงเงื่อนไขตรรกศาสตร์หรือการคำนวณค่าต่างๆ ที่ให้ผลเป็น true หรือ false หรือค่า (value) ซึ่งจะแสดงในภายหลัง
- STATEMENT ในที่นี้หมายถึงการกำหนดค่าให้ตัวแปร การใช้ while หรือ if หรือการเรียกฟังก์ชัน เป็นต้น ซึ่งจะแสดงภายหลัง
- grammar ไม่มีผลบังคับให้เกิดรอบนะครับ เราออกแบบ grammar เพื่อกำหนด syntax ของภาษาเท่านั้น ส่วนรอบเราใช้ semantic ช่วยสร้างโค้ดภาษาเครื่องก่อน แล้วโค้ดภาษาเครื่องจึงทำให้เกิดรอบจริงๆอีกทีหนึ่ง หากมันสามารถรันได้จริงอะนะ
ตัวอย่างที่ 5
if() then ตามด้วย source code อื่นๆแล้วจบด้วย end;
ก็คล้ายกับตัวอย่างที่ 4 ครับเพียงแต่เพิ่ม if เข้ามา สามารถออกแบบเพิ่มได้ดังนี้ครับ
BODY ::= WHILE | { IF }
IF ::= "if" "(" EXPR ")" "then" STATEMENT "end" ";"
และหากว่า if นี้มี else ด้วยแล้ว ซึ่งอาจมีหน้าตา source code ดังนี้
if ( a > b ) then
a = a + 1;
else
b = b * 10;
end;
เช่นนั้นสามารถปรับเปลี่ยน grammar ได้ดั่งใจฝัน (เวอร์จริงๆ)
IF ::= "if" "(" EXPR ")" "then" STATEMENT [ "else" STATEMENT ] "end" ";"
STATEMENT ::= { ASSIGNMENT | WHILE | IF }
ASSIGNMENT ::= VARIABLE "=" EXPR ";"
***หมายเหตุ
- เครื่องหมาย [ และ ] หมายถึง มี หรือ ไม่มี ก็ได้ หากมีสามารถมีได้เพียงหนึ่ง หรือเรียกว่า zero or one
เป็นอย่างไรบ้างครับ จากตัวอย่างข้างต้นพอเข้าใจไหม ค่อยๆลองเขียนนะครับ ผิดถูกอย่างไรให้ลองไล่ด้วย source code ที่ต้องการให้เป็นไปทีละประโยค ขาดก็แก้ไข เกินก็ตัดออก ต่อไปนี้คือ grammar ทั้งหมดตั้งแต่เริ่มต้น (ไม่มีรายละเอียดของ EXPR นะครับ)
START ::= VARIABLE_DECLARATION | BODY
VARIABLE_DECLARATION ::= { DECLARE1 } | { DECLARE2 }
DECLARE1 ::= "var" VARIABLE { "," VARIABLE } ":" TYPE
DECLARE2 ::= VARIABLE ":" TYPE
VARIABLE ::= LETTER { LETTER | DIGIT | "_" }
LETTER ::= a | b | c | ... | x | y | z | A | B | C | ... | X | Y | Z
DIGIT ::= 0 | 1 | 2 | ... | 7 | 8 | 9
TYPE ::= "int" | "float" | "double" | "char" | "string" | "bool"
BODY ::= { WHILE } | { IF }
WHILE ::= "while" "(" EXPR ")" "do" ";" STATEMENT "end" ";"
IF ::= "if" "(" EXPR ")" "then" STATEMENT [ "else" STATEMENT ] "end" ";"
STATEMENT ::= { ASSIGNMENT | WHILE | IF }
ASSIGNMENT ::= VARIABLE "=" EXPR ";"
เราสามารถปรับเปลี่ยน grammar ให้ดียิ่งขึ้น โดยเปลี่ยนการผลิตของ non-terminal ชื่อ BODY และ STATEMENT เสียใหม่ แน่นอนว่าผลของมันทำให้ grammar สามารถกำหนดค่าให้ตัวแปร (ASSIGNMENT) ได้ก่อนการใช้ while หรือ if อีกด้วย ดังนี้
BODY ::= { STATEMENT }
STATEMENT ::= ASSIGNMENT | WHILE | IF
หากเราต้องการให้ grammar สามารถประกาศตัวแปร (VARIABLE_DECLARATION) ภายใน while หรือ if ได้ ก็เพียงแต่ปรับ grammar เป็นดังนี้
STATEMENT ::=
ASSIGNMENT | WHILE | IF | VARIABLE_DECLARATION
ตัวอย่างที่ 6
Program CT414; //ประกาศฟัง์ชันชื่อ CT414
var a:int
b:real
c:bool
Begin
While( a > b + 2 ) do;
a = a - 1;
end;
sub(); //เรียกซับฟังก์ชันชื่อ sub ในในฟังก์ชันอีกที
end;
Begin //เริ่มต้นฟังก์ชัน main
CT414(); //เรียกซับฟังก์ชันชื่อ CT414
end. //สิ้นสุดฟังก์ชัน main
ตัวอย่าง source code ข้างต้นนี้ก็ไม่ยากนัก หากเพื่อนๆสามารถเข้าใจตัวอย่างก่อนหน้านี้ได้ทั้งหมด (ค่อยเป็นค่อยไปนะครับ ผมให้กำลังใจ และเข้าใจผู้ที่เริ่มต้นออกแบบทุกคน เพราะผมก็ไม่มีใครสอนเป็นพิเศษ ใช้ทั้งความจำและการสังเกตเรียนรู้ด้วยตัวเองเรื่อยมา ผิดถูกอย่างไรขออภัยด้วยครับ) เราอาจแบ่ง grammar ออกเป็นสองส่วนเสียก่อน ดังนี้ (rewrite grammar เดิม เขียนเฉพาะหลักๆนะครับ)
START ::= { FUNCTION_DECLARATION } MAIN
กำหนดให้ FUNCTION_DECLARATION คือส่วนการประกาศฟังก์ชัน เช่น Program CT414 และให้ MAIN คือส่วน main function
FUNCTION_DECLARATION ::=
"Program" VARIABLE ";" FUNCTION_BODY
FUNCTION_BODY ::= VARIABLE_DECLARATION "Begin" BODY "end" ";"
MAIN ::= "Begin" BODY "end" "."
สุดท้ายปรับ STATEMENT ให้สามารถเรียกซับฟังก์ชัน (sub function หรือฟังก์ชันย่อย) ดังต่อไปนี้จึงเป็นอันว่าแล้วเสร็จครับ
STATEMENT ::=
ASSIGNMENT | WHILE | IF | VARIABLE_DECLARATION
| CALL_FUNCTION
CALL_FUNCTION ::= VARIABLE "(" [ ARGUMENT ] ")" ";"
***หมายเหตุ
- ARGUMENT นี้หมายถึง ตัวแปรหรือค่าคงที่ (const) หรือ EXPR ที่ต้องการส่งให้กับฟังก์ชัน เพราะบางฟังก์ชันสามารถรับค่าได้ แต่บางฟังก์ชันก็ไม่สามารถรับค่าได้ ดังนั้นควรออกแบบให้ มี หรือ ไม่มี ก็ได้ จึงเลือกใช้เครื่องหมาย [ ] ครับ
หวังว่าเนื้อหาเหล่านี้คงช่วยให้เพื่อนๆสามารถออกแบบ grammar ได้เองในระดับหนึ่ง ถือว่าเป็นการเล่าสู่กันฟังแล้วกันนะครับ โอกาศหน้าค่อยเจอกันใหม่ พยายามเข้านะครับ ^^
อ่านเนื้อหาที่เกี่ยวข้อง ถัดไป
ขอบคุณครับสำหรับคำแนะนำครับ
ตอบลบจะลองอ่านและลองออกแบบดูครับ
ขอบคุณครับ
บอย
ยังไม่เข้าใจแกรมม่า
ตอบลบ