Regular Expression ผมไม่เล็กนะครับ

Syntax
     ไวยากรณ์ คือ โครงสร้างของภาษา หรือ รูปแบบการเขียน source code
                             ถูกสร้างโดย Noam , Backus , Form [BNF]

Token
      คือ หน่วยที่เล็กที่สุด หรือหน่วยที่ย่อยที่สุด แบ่งได้อีก 4 อย่าง
             1. Reserved word  such as  if , while
             2. Constants  such as 42 , "Hello"
             3. Special symbols  such as "," , "<=" , "+"
             4. Identifiers  such as x24, putcahar

Regular Expression 
คือ หน่วยย่อยสุดของภาษา พูดถึงพวก String หรือ Token

             Ex. 1 0 *  -> คือ นิยาม
                    regular expression                      |                  regular Language
                    1 0 ตามด้วย 0 กี่ตัวก็ได้            |                 10 , 100 , 1000
             Ex. a b * a
                     regular expression                      |                  regular Language
                     a b  ตามด้วย a กี่ตัวก็ได้            |                 aba , abaa , abaaa

             grammar มีปลายทางเสมอ โดยจะจบที่ Token

non - Terminal คือ พวกที่ยังไม่สิ้นสุด
Terminal คือ พวกที่สิ้นสุดเเล้ว Token

========================================================================

รูปแบบของ [BNF] 

ตัวอย่างรูปแบบภาษา

        จุดเริ่มต้น          <> แทน non - Terminal

1. <sentence> : : = <non -phrase> <verb - phrase>

2. <non - phrase> : : = <article> <noun>
3. <article> : : = a | the                  // | เเทน หรือ
4. <noun> : : = girl | dog 
5. <verb - phrase> : : = <verb> <non phrase>
6. <verb> : : = sees | pet 

ตรวจสอบภาษา  Ex. " The girl sees a dog "
         วิธีทำ 1. เริ่มจาก sentence
                    <sentence>  =>  <non -phrase> <verb -phrase>
                                       =>  <article> <noun>  <verb -phrase>
                                       =>    the  <noun> <verb -phrase>
                                       =>    the  girl <verb -phrase>
                                       =>    the  girl <verb > <noun -phrase>
                                       =>    the  girl   sees   <noun -phrase>
                                       =>    the  girl   sees   <article> <noun>
                                       =>    the  girl   sees  a   <noun>
                                       =>    the  girl   sees   a  dog  // ทำจนกว่าจะหมด non - Terminal
         เพราะฉะนั้น ถูกต้องหมดตาม grammar

ตัวอย่างรูปแบบภาษา
1. <number> : : = <number> <digit> | <digit>
2. <digit> : : =  0 | 1 | 2 | ... | 9

ตรวจสอบภาษา  Ex2. " 2 3 4 "
         วิธีทำ      <number> => <number> <digit>
                                         => <number> <digit> <digit>
                                         => <digit> <digit> <digit>
                                         =>      2    <digit>  <digit>
                                         =>      2        3    <digit>
                                         =>      2        3         5
        เพราะฉะนั้น ถูกต้องหมดตาม grammar


ตัวอย่างรูปแบบภาษา  " คำนวณเลข 1"
1. <exp> : : = <exp> + <exp> | <exp> * <exp> | <<exp>> | <number>
2. <number> : : = <number> <digit> | <digit>
3. <digit> : : =  0 | 1 | 2 | ... | 9
ตรวจสอบภาษา  Ex2. " 3+4*5 "
วิธีทำ  ตรวจสอบด้วย Parse Tree                 <exp>

/        |        \

                                                                   <exp>    +      <exp>

                                                                       |                 /      |     \

                                                              <number>     <exp>  *   <exp>

                                                                       |                |                 |

                                                                 <digit>     <number>  <number>

                                                                       |                |                 | 

                                                                       3          <digit>       <digit>

                                                                                         |                |

                                                                                         4               5

                                                                                       

นิยามในการ บวก เเละ คูณเลข สมมุติ 3+4*5 จะต้อง นำ 4*5 ก่อน   เเล้ว ค่อย นำมา +3

         อยากจะระบายมากเลยนะครับว่า Regular Expression มันไม่เล็กเหมือนชื่อนะครับ ตอนเรียนกว่าจะเข้าใจนี้แถบคลาน ถามเพื่อนตั้งหลายคน แต่สุดท้ายก็เข้าใจแล้วก็แอบไปตายคาห้องสอบเช่นเดิมนะครับโฮ้ะๆ  o(︶︿︶)o ไว้อาลัยสามวิ

recursive แบบ เริ่มต้น ^^

What is Recursion ?
       คือ โปรแกรมย่อยที่เรียกใช้ตัวเอง

วิธีการเขียนรีเคอร์ซีฟแบบง่ายๆ คือ
        1. ต้องเข้าใจโจทย์ให้ชัดเจนก่อน
        2. หาจุดวกกลับ จุดที่หยุดการเรียกตัวเองซ้ำ
        3. หาขั้นตอนที่เรียกตัวเองซ้ำ

                  รูปแบบทั่วไปของรีเคอร์ซีฟมักจะเป็นแบบนี้

        function (){
                   if( เงื่อนไขที่ทำให้หยุดการเรียกตัวเองซ้ำ base case){
                         ส่งคืนคำตอบ
                   }else{
                         แยกปัญหาเป็นประเด็นย่อย เรียกตัวเองซ้ำ recursive case
                  }
        return คำตอบ
        }


Example  เขียน ฟังก์ชั่น รีเคอร์ซีฟ เพื่อรับค่า n เป็นชนิดจำนวนเต็ม เพื่อหาค่า n !

          วิเคราะห์ปัญหา
                 1. นิยามของ n ! คือ n * (n-1) * (n-2) * ... * 3 * 2 * 1   โดยที่ n >= 0
                 2. หาจุดวกกลับ โจทย์ข้อ นี้ คือ 0 ! เพราะค่าของ n จะลดลงเรื่อย ไปจนถึง 0
                 3. หาขั้นตอนการเรียกรีเคอร์ซีฟ จากนิยามเราจึงสรุปได้ ดังนี้
                                    n ! = n * (n-1)!   
       
                  เช่น 5 ! = 5 * 4 * 3 * 2 * 1 = 120   โดย n = 5
                  หลักการรีเคอร์ซีฟ คือ การเรียกใช้ตัวเองซ้ำ
                             5 ! = 5 * 4 !                                                                  5 * 24 = 120  
                             4 ! = 4 * 3 !                                                                  4 * 6 = 24 
                             3 ! = 3 * 2 !                                                                  3 * 2 = 6
                             2 ! = 2 * 1 !                                                                  2 * 1 = 2
                             1 ! = 1 * 0 !                                                                  1 * 1 = 1
                             0 ! = 1                       // จุดนี้ คือ base case นั้นเอง       

ตัวอย่างโปรแกรม

          #include <iostream>
          #include <stdio.h>
          using namespace std;

          float factorial(int n);

          float factorial(int n){
               float fact;
                   if(n==1){        // base case
                         fact=1;
                   }else{            // recursive case
                        fact=n*factorial(n-1);
                }
           return fact;
          }

         int main(){
            int n;
            float sum;
               cout <<"Input Number : ";
               cin >>n;

               sum=factorial(n);
               printf("factorial of %d is %.2f",n,sum);
         return 0;

          }

เป็นตัวอย่างเล็กๆ น้อยๆ ของการเขียนโปรแกรมแบบ recursive หวังว่าคงจะเป็นประโยชน์กันนะครับ ^^