การให้ความหมาย

<< ตรวจสอบไวยากรณ์ | # >>

- ดาวน์โหลด CT414_1_54_v2
- รองรับการประกาศตัวแปร (dim) และสตรัก (struct)
- ฟ้องการประกาศตัวแปรซ้ำ, ฟ้องการประกาศฟิวด์ซ้ำ และฟ้องการกำหนดไทป์ที่ยังไม่ได้ประกาศ

- ดาวน์โหลด CT414_1_54_v3
- รองรับการให้ไทป์ (Type) ทั้งแบบธรรมดา (int, float, string) และแบบสตรัก (struct)
*** ทดสอบด้วยการกำหนดจุด debug ณ เมธอด T แล้ว debug โดยใช้ช่อง Watches พิมพ์ varList และ structList

- ดาวน์โหลด CT414_1_54_v4
- ทำงาน comment (ดูไฟล์ Lexical.java ส่วนการตัด comment) สำหรับ Parser ได้แล้ว
- เปลี่ยนชื่อตัวแปร local บางชื่อ (ไม่มีผลใดๆต่อ version ที่ผ่านมา แค่เปลี่ยนชื่อเฉยๆ) ได้แก่ fieldList เป็น fields
- ระบุค่าแอตทริบิวต์ name ของคลาส Symbol เป็น "_unknown"
- ระบุค่าแอตทริบิวต์ codeName และ codeType ของคลาส Token เป็น -1 ทั้งคู่
- ฟ้องการเรียกใช้งานตัวแปรแบบปกติและแบบสตรัก

       ผมต้องไปรายงานตัวทางทหารกับอำเภอแล้วครับ เสียใจด้วยที่เขียนให้ได้เท่านี้ พยายามดูโค้ดแล้วสร้างความเข้าใจทีละขั้นตอน เชื่อมั่นและมีไฟ สำหรับ source code ที่ให้ ให้ถือว่าเป็นแนวทางนะครับ อย่าได้ยึดติดว่าต้องเขียนอย่างนี้อย่างนั้นเสมอไป เขียนไปตามขั้นตอนและอัลกอลิทึมของตัวเองให้เข้าใจก่อนเป็นดีที่สุด สวัสดีครับเพื่อนๆ

---

ตรวจสอบไวยากรณ์

<< ตัดคำ | การให้ความหมาย >>

       ตัดคำสำเร็จแล้ว ผลลัพธ์ที่ได้ต้องมี token stream และ symbol table สองอย่างนี้เป็นที่ถกเถียงกันเหลือเกินว่า อย่างไหนจำเป็น อย่างไหนไม่จำเป็น แท้จริงก็จำเป็นทั้งคู่ หากว่ากันตามตำราที่อาจารย์ใช้สอนแล้ว หน้าที่ของทั้งสองมีดังนี้ครับ
- token stream สำหรับ token ทั้งหมดที่ตัดได้จาก source code เรียงร้อยกันไปเรื่อยๆ
- symbol table สำหรับ token ที่ซ้ำกันเก็บแค่อันครั้งเดียวและอยู่ในรูปแบบตัวเลขโค้ด (ตั้งเอาเอง)
ดังตัวอย่าง สมมติ source code ดังนี้

A() {
}
main() {
}

ก็จะได้ token stream ดังนี้
- กำหนดให้เครื่องหมาย [ และ ] แทนหนึ่ง token

[ "A" : "identifier" ][ "(" : "separator" ][ ")" : "separator" ]
[ "{" : "separator" ][ "}" : "separator" ]
[ "main" : "keyword" ][ "(" : "separator" ][ ")" : "separator" ]
[ "{" : "separator" ][ "}" : "separator" ]

และมี symbol table ดังนี้

[ 0 : "A" : "identifier" ][ 1 : "(" : "separator" ][ 2 : ")" : "separator" ]
[ 3 : "{" : "separator" ][ 4 : "}" : "separator" ][ 5 : "main" : "keyword" ]

       โดยปกติแล้ว parser หรือเรียกกว่า "การแปล" จะมีสองขั้นตอนสำคัญคือ
1. ตรวจสอบไวยากรณ์ (syntax)
2. การให้ความหมาย (semantic)

เพราะเวลาจวนตัวผมแล้ว ดังนั้นให้เพื่อนดาวน์โหลด net beans project ชื่อ CT414_1_54_v1 ต่อไปนี้
- ดาวน์โหลด CT414_1_54_v1
- ภายในจะมี folder ชื่อ CT414_1_54 ให้ใช้ NetBeans IDE (ของผมคือ v 6.9.1) เปิดขึ้นมา
- ใน project ดังกล่าว ณ มุมมอง Projects ผมแบ่ง package ออกสองกลุ่ม ได้แก่
              - compiler
              - problem

package ชื่อ 'compiler' สำหรับงาน compiler ตาม grammar ของเทอม 1/54
package ชื่อ 'problem' สำหรับเฉลยโจทย์ทดสอบที่ผมตั้งถามเพื่อนๆ

เปิด package 'compiler' ออกจะเห็น package ย่อยอีกดังนี้
       - lexical
       - parsre
       - codegen

package ชื่อ 'compiler.lexical' รวบรวมคลาสทั้งหมดที่เกี่ยวข้องกับการตัดคำ (100%)
package ชื่อ 'compiler.parser' รวบรวมคลาสทั้งหมดที่เกี่ยวข้องกับการตรวจสอบไวยากรณ์และให้ความหมาย (50%) ซึ่งขณะนี้สำเร็จเพียงการตรวจสอบไวยากรณ์ ยังเหลือการให้ความหมายที่กำลังเขียนอยู่
package ชื่อ 'compiler.codegen' รวบรวมคลาสทังหมดที่เกี่ยวข้องกับการสร้าง machine code (0%)

ผมใช้ source code ของน้อง "PetPraUMa" ทดสอบแล้ว (ไฟล์ชื่อ SourceCode1.txt) ไม่ปรากฏความผิดพลาดใดๆ ให้เพื่อนๆทดสอบบ้าง โดยมีขั้นตอนคือ
- เปิด package ชื่อ 'compiler' จะพบไฟล์สกุล .java ชื่อ Main และไฟล์สกุล .txt อีกสองไฟล์ ได้แก่ SourceCode.txt และ SourceCode1.txt ไฟล์สกุล .txt ทั้งสองนี้ใช้ทดสอบไวยากรณ์ของ grammar ถูกต้องทุกประการ
- คลิกขวาที่ไฟล์ Main.java เลือก RunFile แล้วสังเกตผลลัพธ์ โชคดีครับ

<< ตัดคำ | การให้ความหมาย >>

ตัดคำ

<< อ่าน EBNF ให้เข้าใจ | ตรวจสอบไวยากรณ์ >>

       หลังจากเรื่อง EBNF ก็มาถึงการตัดคำ (Lexical) ตัดคำทำไม? ก็เพื่อแยกแต่ละส่วนของ source code ออกมา แยกมันทำไม? ก็เพื่อนำมาตรวจสอบว่า source code ที่ได้นั้นถูกต้องตามหลักไวยากรณ์ของภาษาหรือไม่ อ่าว~แล้วตัวภาษาเอามาจากไหน จาก grammar ที่นิยามด้วย EBNF นั่นไง พอเข้าใจนะครับ

คำหรือต่อไปนี้จะเรียกว่า token มีหลายประเภท โดยทั่วไปแบ่งออกสี่ประเภท ดังนี้
- keyword บางคนก็เรียกเป็น reserved words ตอนนี้อย่าเพิ่งสงสัยเลยว่ามันต่างกันอย่างไร (ตัวอย่างภาษา C)
- operator ได้แก่ + - * / และอื่นๆ
- separator ได้แก่ { } [ ] ( ) ; , . และอื่นๆ
- identifier หมายถึง ชื่อใดๆที่ตั้งตามหลักการตั้งชื่อหรือข้อตกลงร่วมกันกับอาจารย์ เช่น A myFunction B Phai น้องส้มโอน่ารัก เป็นต้น

สมมุติว่าเรามี source code ดังต่อไปนี้

A() {
}
main() {
}

เมื่อนำมาทำงานตัดคำ จะได้ว่า

keyword : main
operator :
separator : ( ) { }
identifier : A

โจทย์ที่ 2 จงเขียนโปรแกรมตัดคำจากสายสตริง (string) ต่อไปนี้ ให้ได้ผลลัพธ์ดังข้างต้น
- กำหนดคลาสทดสอบชื่อ Test2
- กำหนดตัวแปร local variable ชื่อ sourceCode มีค่า "A() { } main() { }"

class Test2 {
       public static void main(String[] args) {
              String sourceCode = "A() { } main() { }";
       }
}

ทดลองแก้ปัญหาเองก่อน ติดตรงไหน ไวยากรณ์ภาษา Java หรือเปล่า หรือติดที่คิดอัลกอริทึมไม่ออก ค่อยเป็นค่อยไปนะครับ

สำหรับเรื่องตัดคำผมคิดว่าหลายคนคงทำได้แล้ว ดังนั้นหากไม่มี request ให้เสนอวิธีการ (ในแบบของผม) ผมจึงขอข้ามส่วนนี้ไปก่อนนะครับ

<< อ่าน EBNF ให้เข้าใจ | ตรวจสอบไวยากรณ์ >>

---

อ่าน EBNF ให้เข้าใจ

<< CT414 ภาค 1/54 | ตัดคำ >>

       จากตัวอย่างหน้าที่ผ่านมา เราจะแยกคลาสสำหรับทดสอบซึ่งมีเมธอด main ออกมาต่างหาก และเขียนคลาสที่เกี่ยวข้องกับงานทั้งหมดขึ้นมาใหม่ อาจมีเพียงหนึ่งคลาสหรือมากกว่าก็อยู่ที่การออกแบบเป็นหลักครับ เนื่องจากเวลามีน้อย เนื้อหาหน้านี้เราไปทำความรู้จัก EBNF กันก่อนเลย

EBNF ที่เราจะใช้ศึกษาก็คือโจทย์หรือ grammar ที่น้อง "PetPraUMa" ได้โพสต์ไว้ในกระดานข่าวของภาควิชาวิทยาการคอมฯ ให้ดาวน์โหลดมาดูพร้อมกันได้เลย คลิกที่นี่ ดังที่ได้ยกมาบางส่วนด้านล่างนี้

<S> ::= <Sp> main() { <B> }
<Sp> ::= id() { <B> } <Sp>
<Sp> ::= empty_string

<B> ::= <T> <S1>

<T> ::= <ET> dim id <T1> as <T2> ; <T>
<T> ::= empty_string

<ET> ::= extern
<ET> ::= empty_string

<T1> ::= , id <T1>
<T1> ::= empty_string

...เรื่อยไปนะครับ

EBNF ใช้อธิบายโครงสร้างของภาษาหรือที่เรียกว่า "กฏไวยากรณ์" (syntax) ตัวผลิตจะอยู่ทางซ้ายของเครื่องหมาย ::= ส่วนผลิตผลจะอยู่ทางขวาของเครื่องหมาย ::=

EBNF ประกอบด้วย non-terminal และ terminal
นิยามอย่างง่ายที่สุด non-terminal สามารถแบ่งแยกได้เป็น non-terminal หรือ terminal อีกเท่าใดก็ได้
ส่วน terminal ไม่สามารถแบ่งแยกได้อีกแล้ว

ข้อตกลงทั่วไปสำหรับ non-terminal คือต้องเปิดด้วยเครื่องหมาย < และปิดด้วยเครื่องหมาย > เช่น <S> <B> <T> เป็นต้น ทว่าบางทีอาจารย์ท่านก็เขียนเพียงตัวอักษรเฉยๆ แต่อย่างไรก็คือ non-terminal เหมือนกัน ได้แก่ id ซึ่งย่อมาจาก identifier หมายถึงการตั้งชื่อตามกฎการตั้งชื่อตัวแปรของภาษาใดๆ (เรากำหนดเอาเองหรือเลียนแบบภาษา C ก็ได้)

และข้อตกลงทั่วไปสำหรับ terminal คือเป็นตัวอักษรเฉยๆ (ไม่นับ id นะครับ) จาก grammar ข้างต้น เช่น main เครื่องหมาย ( เครื่องหมาย ) เครื่องหมาย { เครื่องหมาย } เหล่านี้เป็นต้น

สุดท้ายสำหรับ empty_string นั้นหมายถึง ว่างเปล่า คือเลือกที่จะไม่ผลิตสิ่งใดหรือกล่าวว่าไม่มีผลิตผลใดๆ

ควรทราบว่า non-terminal อาจเขียนด้วยตัวพิมพ์ใหญ่ เช่น S B T เฉยๆ ไม่มีเครื่องหมาย < และ > ครอบก็เป็นได้ ขึ้นอยู่กับข้อตกลงและตำราที่ใช้เป็นหลัก ส่วน terminal ก็อาจเขียนเป็นตัวพิมพ์เล็กที่อาจมีเครื่องหมาย " และ " ครอบหรือไม่ก็ได้

เราควรอ่าน grammar ให้เป็น คือสามารถนำมันมาสร้างเป็น source code ได้ ตัวอย่าง

<S> ::= <Sp> main() { <B> }
<Sp> ::= id() { <B> } <Sp>
<Sp> ::= empty_string

ในเมื่อ <S> เป็น non-terminal เริ่มต้นของ grammar นี้ ตัวมันสามารถผลิต <Sp> main() { <B> } อย่างนี้จะสร้างเป็น source code อย่างง่ายที่สุดอย่างไร
- กำหนดให้ <Sp> ผลิตได้ empty_string
- กำหนดให้ <B> ผลิตได้ empty_string
ดังนั้น source code จึงเป็น

main() {
}

อ่านถึงตรงนี้พอเข้าใจไหมครับ ทีนี้หากว่า <Sp> ไม่ได้ผลิตเป็น empty_string แต่กลับได้เป็น id() { <B> } <Sp> และกำหนดให้ <B> ผลิตได้ empty_string ดังเดิม เมื่อนั้นหน้าตา source code ก็จะออกมาอย่างนี้

A() {
}
main() {
}

หรือ

A() {
}
myFunction() {
}
main() {
}

หรือทำนองใดๆ พอเข้าใจนะครับ คล้ายกับการประกาศฟังก์ชันแบบ inline ในภาษา C (ฟังก์ชันในภาษา C เรียกการเขียนฟังก์ชันใดๆไว้ก่อน main ว่า inline function มันจะจองหน่วยความจำเท่าที่ตัวฟังก์ชันระบุทันที โดยไม่สนใจว่าฟังก์ชันดังกล่าวจะถูกเรียกใช้หรือไม่ก็ตาม ต่างจากการเขียนฟักง์ชันหลัง main ซึ่งจะจองหน่วยความจำก็ต่อเมื่อเกิดการเรียกใช้ฟังก์ชันจากภายใน main เท่านั้น)

จาก source code ข้างต้นจะเห็นว่าตำแหน่ง id ของตัวผลิต <Sp> สามารถเปลี่ยนเป็นชื่อใดๆก็ได้ตามหลักการตั้งชื่อตัวแปรทั่วไป เช่น A myFunction B Phai น้องส้มโอน่ารัก หรือใดๆตราบเท่าที่เราต้องการ (ต้องอยู่ในข้อตกลงของอาจารย์ด้วยนะ)

สงสัยหรือต้องการให้เพิ่มเติมอย่างไรก็แสดงความเห็น (comment) ด้านล่างนี้ได้เลยครับ หากเข้าใจแล้วให้คลิกลิงค์สู่หน้าต่อไป

<< CT414 ภาค 1/54 | ตัดคำ >>

---

CT414 ภาค 1/54

       สวัสดีครับเพื่อนๆ หนนี้ผมจะแนะนำการเขียนโปรแกรม Compiler ด้วยภาษา Java โดยอ้างอิงโจทย์ของน้อง "PetPraUMa" แห่ง "กระดานข่าว-ภาควิชาวิทยาการคอมพิวเตอร์" และประโยชน์ทั้งหมดขอยกให้กับเพื่อนใน Facebook ที่ชื่อ "Tong Slumberous" ครับ

       ไหนๆก็รู้จักกันแล้ว ใครเขียนภาษา Java เป็นแล้วให้ข้ามส่วนนี้ไปได้เลย (อ่านหน้าต่อไปด้านล่างครับ) ถ้าใครเพิ่งเริ่มเขียนภาษา Java โปรดอ่านสักนิด เผื่อว่าเราจะได้เข้าใจในแนวทางเดียวกัน

       Java ยากไหม ผมว่าไม่ยากเท่าความพยายามของเราหรอกครับ ถามก่อนว่าภาษา C เขียนเป็นไหม ถ้ายังไม่เป็นก็ควรเรียนรู้ไว้ เพราะ C เป็นภาษาโครงสร้างที่มีลำดับการทำงานจากบนลงล่าง ใช้เป็นภาษาพื้นฐานเพื่อเรียนรู้การเขียนโปรแกรมนั้นดี บ้างว่าเขียน Java ไปเลยไม่ดีกว่าหรือ ผมก็ว่าเป็นมุมมองที่ไม่แปลกอะไร เพราะอย่างไรภาษาที่เป็น OOP อย่าง Java หรือ C# ก็ยังต้องแบ่งคลาสออกเป็นเมธอด และเนื้อแท้ภายในเมธอดก็คือลำดับที่เป็นโครงสร้างดั่งภาษา C นั่นแหละครับ จะต่างกันที่แนวคิดและกลวิธีการเขียนเท่านั้นเอง

       เอาล่ะ ควรรู้ Java ระดับไหนถึงจะเขียน Compiler ได้ ตามความเข้าใจของผมควรรู้เกี่ยวกับ เมธอด main, ชนิดข้อมูล, การประกาศตัวแปร, การใช้ตัวแปร, การแยกออกเป็นเมธอด (แบ่งเป็นฟังก์ชัน), การเรียกใช้เมธอด, การผ่าน arguments ให้เมธอด, การ override, การ overloading และ constructor เป็นอย่างน้อย เยอะไปใช่ไหม ก็นะ มันจำเป็นต้องเรียนรู้ ถือเสียว่าเดินทางไปเที่ยวในโลกของ Java หรือภาษาที่เป็น OOP ก็แล้วกันนะครับ แต่อย่างไรผมก็จะคุยเรื่องเหล่านี้ให้ฟังทั้งหมด เราต้องคิดไปด้วยกัน โอเคนะ งั้นมาเริ่มกันเลย

Class
       คลาส ให้เข้าใจว่า คือการเขียนขึ้นเพื่อห่อหุ้ม หุ้มมันทำไม ก็เพื่อจัดหมวดหมู่ครับ ตัวอย่างเช่น มีกระเป๋าดินสอ กระเป๋าสตางค์ กระเป๋าใส่เสื้อผ้า กระเป๋าสำหรับใส่หนังสือไปเรียน กระเป๋าสำหรับเดินทาง เป็นต้น ถามว่าทั้งหมดนั่นกระเป๋าใช่ไหม ก็ว่าใช่ ล้วนเป็นกระเป๋าทั้งนั้น แต่มีหน้าที่แตกต่างกันไปเพื่อความเป็นระเบียบเรียบร้อยไงล่ะ ทีนี้มาดูสิ่งที่ควรอยู่ในกระเป๋าของภาษา Java กัน ที่ควรรู้จักตอนนี้คือ Attribute และ Method

Attribute
       ภาษา C เขาเรียกกันว่า "ตัวแปร" (variable) แต่ละภาษามีวิธีประกาศตัวแปรแตกต่างกัน ขึ้นอยู่กับโครงสร้างทางไวยากรณ์ (syntax) ของภาษานั้นๆ ดูภาษา C กันก่อน

int a = 100;

แรกสุดเลยคือ int คือชนิดข้อมูลหรือ type เป็นชนิด integer สำหรับจำนวนเต็ม (เต็มลบ เต็มศูนย์และเต็มบวก)
ถัดมาคือ a หรือ identifier เราตั้งชื่อว่า a เฉยๆ
ถัดมาคือ = หรือ operator มีความหมายว่าให้ค่าทางซ้ายเท่ากับค่าทางขวา
ถัดมาคือ 100 หรือ constant ที่มีค่าหนึ่งร้อย
และสุดท้ายคือ ; หรือ separator เขียนเพื่อระบุว่าจบประโยคการประกาศตัวแปรแล้วนะ

เพียงเท่านี้เครื่องคอมฯของเราก็เข้าใจแล้วว่า ให้จัดการหน่วยความจำสำหรับเก็บค่า 100 และเรียกพื้นที่หน่วยความจำดังกล่าวว่า a ทีนี้หากต้องการค่า 100 มาใช้งานก็เพียงแต่เรียกชื่อ a

ต่อไปเมื่อต้องการนำค่า 100 แสดงผลทางจอภาพเราก็เขียนเป็นคำสั่ง

cout << a << endl;

หรือ

cout << 100 << endl;

ก็ได้ทั้งนั้น เด็กๆใช่ไหมล่ะ พอเข้าใจนะครับ ทีนี้มาดูภาษา Java กันบ้าง หากต้องการเลียนแบบก็เขียนได้ว่าอย่างนี้

int a = 100;

เหมือนกันอย่างแกะ เหลือแค่ศัพท์ที่เขาไม่เรียกกันว่าตัวแปร แต่จะเรียกว่า "แอตทริบิวต์" (attribute) นอกจากนี้เจ้าแอตทริบิวต์เนี่ยยังสามารถเพิ่มระดับความปลอดภัย (access modifier) ให้กับมันได้อีก ซึ่งเป็นคุณสมบัติประการหนึ่งที่ภาษา OOP พึงมี ได้แก่

public หมายถึง ใครๆก็เรียกใช้ได้ ระดับความปลอดภัยอ่อนสุด
ไม่ระบุ หมายถึง default คล้ายกับระดับความปลอดภัยภายใน folder, งานใดๆใน folder เดียวกันจึงเรียกใช้ได้
protected หมายถึง เฉพาะคลาสที่สืบทอดต่อๆกันมาจึงเรียกใช้ได้ ระดับความปลอดภัยปานกลาง
private หมายถึง ระดับความปลอดภัยสูงสุด คลาสเดียวกันเท่านั้นที่จะเรียกใช้ได้

เวลาประกาศตัวแปร ภาษา Java กำหนดให้สามารถระบุระดับความปลอดภัยแก่แอตทริบิวต์ จะใช้ระดับไหนขึ้นอยู่กับงานของเราและกลวิธีการออกแบบคลาสของเราเป็นหลักครับ ตัวอย่างเช่น

private int a = 100;

แบบนี้จำกัดให้ a ใช้ได้เฉพาะในคลาสของตัวเองเท่านั้น คลาสอื่นอย่าแหยม แต่ถ้า

public int a = 100;

แบบนี้คลาสใดๆก็สามารถเรียกใช้ a ได้ทั้งนั้น และในขั้นต้นนี้ผมแนะนำให้รู้จักเพียงสองระดับความปลอดภัย นั่นคือ private และ public

Method
       ดูภาษา C ก่อน ต่อไปนี้เป็นการประกาษฟังก์ชันเพื่อนำตัวเลขจำนวนเต็มสองจำนวนมาบวกกัน แล้วส่งผลลัพธ์ที่ได้กลับไปยังที่เรียกใช้

int summation(int x, int y) {
       return x + y;
}

และถ้าเป็นภาษา Java ล่ะ

int summation(int x, int y) {
       return x + y;
}

เป๊ะ เหมือนกันทั้งหมด นอกจากนี้เรายังสามารถเพิ่มระดับความปลอดภัยให้กับเมธอด (method) เช่นเดียวกับแอตทริบิวต์ครับ



โจทย์ที่ 1 เขียนโปรแกรมบวกเลขสองจำนวนด้วยภาษา Java
- กำหนดให้คลาสชื่อว่า Calculate
- กำหนดให้เมธอดที่ทำงานบวกชื่อว่า summation

class Calculate {
       public int summation(int x, int y) {
              return x + y;
       }
}

ทีนี้ก็เรียกใช้ที่คลาส Test1 ซึ่งมีเมธอด main

class Test1 {
       public static void main(String[] args) {
              Calculate cal = new Calculate();
              System.out.println(cal.summation(10, 20));
       }
}

ใครยังไม่เข้าใจหรือสงสัย หรือผมผิดพลาดประการใดสามารถแสดงความเห็น (comment) ได้ด้านล่างของหน้านี้เลยครับ

หากเข้าใจแล้วเรามาต่อกันเลย อ่านหน้าถัดไป

---