Grammar และ Derivation

Grammar และ Derivation
ในการออกแบบภาษาการโปรแกรมคอมพิวเตอร์นั้น จะมีการกำหนดไวยากรณ์ (grammar) เพื่อสร้างรูปแบบ (syntax) ของภาษาทั้งหมด
ในภาษาที่มีการคอมไพล์ก็จะมีการทำ Syntax analysis ในเวลาคอมไพล์เพื่อตรวจดูว่าโปรแกรมที่เขียนนั้นถูกต้องตามภาษาหรือไม่  ส่วนภาษาที่ไม่มีการคอมไพล์หรือกลุ่มที่มีการนำไปใช้ในลักษณะ Interpretation  จะมีการตรวจสอบ syntax ในเวลารันไทม์ กระบวนการในการวิเคราะห์ Syntax ของภาษาเพื่อดูว่าโปรแกรมที่เขียนนั้นเป็นไปตามรูปแบบที่กำหนดหรือไม่ สามารถกระทำได้ 2 วิธีคือใช้
1. Language Recognizers คือ device ซึ่งจะอ่านอักขระในเซตของอักขระทั้งหมดเข้ามาเรื่อยๆ แล้วพิจารณาว่าเป็นส่วนหนึ่งในภาษาหรือไม่  กลไกการทำงานนั้นอาจพิจารณาการทำงานเทียบเคียงกับภาษาไทยมี 44 ตัวอักษร มีวรรณยุกต์ 21 ตัว Recognizer จะทำการอ่านอักขระทั้งหมดเพื่อพิจารณาว่าเป็นประโยคภาษาไทยหรือไม่
ฉันอ่านหนังสือ   
ด้หก่าหกสดาากสห่ด

จากข้อความข้างต้นหาก Recognizer อ่านจะค่อยๆอ่านอักขระเข้ามาซึ่ง ก็จะตอบได้ว่า  ข้อความ "ฉันอ่านหนังสือ" เป็นภาษาไทย  ส่วนอีกข้อความหนึ่งไม่ใช่ภาษาไทย

2. Language Generators คือ device ซึ่งจะสร้างประโยคของภาษา  สมมติว่าต้องการตรวจสอบภาษาไทยว่าประโยค "ฉันอ่านหนังสือ" เป็นภาษาไทยหรือไม่  ในการทำงาน Generator จะนำไวยากรณ์ของภาษาเข้ามาตรวจสอบ  สมมติว่าไวยากรณ์ของภาษาไทยกำหนดไว้ว่า ประโยคจะต้องประกอบด้วยประธาน กิริยา  และ กรรม ดังนั้น  Generator จะพยายามสร้างประโยคซึ่งสอดคล้องกับรูปแบบในไวยากรณ์  ซึ่งประโยคสอดคล้องกับ Syntax ดังนั้นจะตัดสินได้ว่าประโยคนี้เป็นส่วนหนึ่งของภาษา
   ประธาน           กิริยา          กรรม
   ฉัน                 อ่าน           หนังสือ
การสร้างประโยคเพื่อตรวจสอบ syntax ของภาษาเรียกว่า Derivation 

การทำ Derivation เพื่อสร้างประโยคของภาษาจะเริ่มจากการสร้างประโยคจาก Start symbol
Grammar:
<program> → begin <stmt_list> end
<stmt_list> → <stmt>  | <stmt> ; <stmt_list>
<stmt> → <var> = <expression>
<var> → A | B | C
<expression> → <var> + <var> | <var> – <var> | <var>

 ต้องการวิเคราะห์ว่า ประโยค  begin  A=B+C ; B = C end เป็นส่วนหนึ่งของภาษาหรือไม่
การทำ Derivation จะได้ดังนี้
<program> => begin <stmt_list> end
                  => begin <stmt> ; <stmt_list> end
                  => begin <var> = <expression> ; <stmt_list> end
                  => begin A = <expression> ; <stmt_list> end
                  => begin A = <var> + <var> ; <stmt_list> end
                  => begin A = B + <var> ; <stmt_list> end
                  => begin A = B + C ; <stmt_list> end
                  => begin A = B + C ; <stmt> end
                  => begin A = B + C ; <var> = <expression> end
                  => begin A = B + C ; B = <expression> end
                  => begin A = B + C ; B = <var> end
                  => begin A = B + C ; B = C end

ดังนั้น Generator จะสรุปว่าประโยคนั้นเป็นส่วนหนึ่งของภาษา  เพราะสามารสร้างประโยคได้
สิ่งจำเป็นในการทำ Derivation
1. ต้องกำหนดไวยากรณ์  ในไวยากรณ์ประกอบด้วย
- Start symbol เช่น <program> คือ start symbol
- Nonterminal symbol  คือข้อความใน < > ซึ่งจะมี Production rule เกี่ยวข้องอย่างน้อย 1 rule
- Terminal symbol คือ lexeme หรือหน่วยเล็กที่สุดของภาษา

Production rule คือกฎในแต่ละบรรทัด 
<program> → begin <stmt_list> end
<stmt_list> → <stmt>  | <stmt> ; <stmt_list>
<stmt> → <var> = <expression>
<var> → A | B | C
<expression> → <var> + <var> | <var> – <var> | <var>
 ในตัวอย่าง A, B และ C คือ Terminal symbol

ในการทำ Derivation นั้น การแทนที่ (replace) Nonterminal symbol ในแต่ละขั้นตอนนั้นจะต้องเลือกแทนที่ด้วย Production rule เพียงหนึ่ง Production rule เท่านั้น โดยนำประโยคในด้านขวามือไปแทนที่ Nonterminal symbol ของประโยคในขั้นตอนก่อนหน้า
จาก Derivation ด้านบน สามารถแสดงตำแหน่งที่แทนที่ (สีน้ำเงิน) ได้ดังนี้
<program> => begin <stmt_list> end
                  => begin <stmt> ; <stmt_list> end
                  => begin <var> = <expression> ; <stmt_list> end
                  => begin A = <expression> ; <stmt_list> end
                  => begin A = <var> + <var> ; <stmt_list> end
                  => begin A = B + <var> ; <stmt_list> end
                  => begin A = B + C ; <stmt_list> end
                  => begin A = B + C ; <stmt> end
                  => begin A = B + C ; <var> = <expression> end
                  => begin A = B + C ; B = <expression> end
                  => begin A = B + C ; B = <var> end
                  => begin A = B + C ; B = C end

การแทนที่ในการทำ Derivation สามารถเลือกแทนที่ในตำแหน่งใดก็ได้  อย่างไรก็ตามอาจพิจารณาลักษณะการแทนที่ออกเป็น 2 ลักษณะคือ Left-most derivation (เช่นในตัวอย่าง) และ Right-most derivation