เล่าสู่ประสบการณ์ การเขียนภาษา computer แบบง่าย ๆ ของผม

ความยากในการสร้างภาษาของตัวเองนั้น โดยปกติจะแปรผันไปตาม features ที่มันมี

ดังนั้น blog นี้จะเป็น blog แบบ walk through ประสบการณ์ที่ผมเคยผ่านมา รวมถึงอาจจะเป็น guides สำหรับใครบางคนที่อยากทำภาษาของตัวเองแบบง่าย ๆ ละกัน

เริ่มแรกเลยถ้าเราอยากทำอะไรง่าย ๆ เราก็ควรคิดอะไรง่าย ๆ เข้าไว้ แต่ก็ควรเข้าใจ พื้นฐานของภาษาต่าง ๆ ไว้ด้วยว่าเพราะอะไรถึงต้อง design แบบนั้น

BSM — โปรแกรมพิมเลข A ถึง 1

Step 1. Why? and Design

Why? คือ ทำไปให้ใครใช้? หรือ อยากไปทำไม? ทำไมถึงอยากทำ? มีเป้าหมายเป็นอะไร

อย่างเช่นของผม ส่วนใหญ่คือ ทำภาษาของตัวเองแล้วมันดูเท่ดี เลยอยากทำ :)

ควรเลือกเป็น compiler หรือ interpreter ดี?
คำตอบคือ แล้วแต่เลยครับว่าจุดประสงค์ของภาษาเราเป็นยังไง

ต่อมาคือ Design ครับว่า syntax และ grammar เราจะเป็นแบบไหน โดยความยากส่วนใหญ่ที่จะทำให้การ coding ของเรายากขึ้นส่วนนึงก็มาจากสิ่งนี้แหละครับ

อย่าง blog ในคราวนี้เราจะสร้างภาษาชื่อ BSM กัน
โดย BSM จะมี syntax คล้าย ๆ กับ ภาษา assembly แต่ features ไม่เยอะเท่า และเป็น interpreted language

// list คำสั่งใน BSM
SET <A> <VALUE> // Set register <A> with <VALUE>

CMP <A> <B> // Compare value <A> with value <B>

JMPZ <LINE> // Jump to <LINE> if T reg is zero
JMP <LINE> // Jump to <LINE> ifT reg is not zero

ADD <A> <VALUE> // Add <A> reg by <VALUE>
SUB <A> <VALUE> // Subtract <A> reg by <VALUE>
MULT <A> <VALUE> // Multiple <A> reg by <VALUE>
DIV <A> <VALUE> // Divine <A> reg by <VALUE>

PRNT <VALUE> //Print <VALUE> to screen
CALL <FUNCTION> // Call function

พอ list คำสั่งเสร็จแล้วก็ มาถึงขั้นของ syntax ครับ

// มาดูกันที่ syntax เริ่มต้นของภาษาเรากันดีกว่า
FUNCTION_NAME:
    SET A, 5
    ADD A, 2
    PRNT A
START:
    CALL FUNCTION_NAME

// จะเห็นได้ว่า syntax ของไม่เรานั้นจะใช้ 1 คำสั่งต่อ 1 บรรทัดดังนั้น
// BSM ไม่สนใจ space นั่นหมายความว่า การเว้นวรรคไม่มีผลใน syntax
// space จะมีผลก็ต่อเมื่อ เราใช้งาน คำสั่งในภาษา
// 1 บรรทัดจะใช้ได้เพียงแค่ 1 คำสั่งเท่านั้น
// การประกาศ function ทำได้ด้วยการ ใส่ชื่อ function และลงท้ายด้วย colon
// คำสั่งไหนที่ไม่อยู่ใน Function จะถือว่า คำสั่งนั้นจะอยู่ใน Function START เพราะ BSM จะ
// run Function START เป็น default

หลังจากที่เราวางโครง syntax ของเราแล้วก็ถึงเวลาที่เราจะ ย่อย ideas ของเราให้อยู่ใน รูปที่เข้าใจง่ายกว่าคำพูดด้วย

PEG (Parsing Expression Grammar)

แต่บอกก่อนว่า syntax ของ PEG ที่ผมเขียนนั้นจะไม่ตรงกับ PEG ของจริงเท่าไหร่ เอาเป็นว่ามันคือ pseudo PEG ก็แล้วกัน เราละไว้ในฐานที่เข้าใจ

// NOTE: จะขอย่อคำว่า command เป็น cmd และ function เป็น func นะครับ
program = (function | command) ('\n' (function | command))*
// ( cmd หรือ func ) จำเป็นจะต้องมี newline ขั้นกลางถึงจะ มี cmd หรือ func ต่อไปได้

function = [a-zA-Z]+ ':' ('\n' command)*
// [a-zA-Z] ต่อกันและมี ':' คั่น โดยการจะขึ้น command ข้างในได้จำเป็นต้องมี newline คั่น

command = [A-Z]+ (' ' params)?
// A-Z โดยมี space คั่น ก่อนจะมี params ได้ละถ้าไม่มีก็ไม่เป็นไร

params = value (',' value)*
// value ตามด้วย value ถัดๆไปจะมี ',' คั่นถ้ามี

value = [A-Z] | [0-9]+
// หมายถึง ตัวอักษร A-Z หรือ เลขที่เรียงต่อกัน

ws = ' ' -> skip
// ข้าม space ไปหากไม่มีการเรียกใช้ใน syntax

และนี่คือคำอธิบายเบื้องต้นสำหรับ PEG ของ BSM ครับ

Step 2. เขียน Lexer และ Parser

ก่อนที่เราจะมาพูดถึง Lexer เราต้องมาทำความรู้จักกับ Tokenizer ก่อนครับ

Tokenizer คืออะไร?
มันคือโปรแกรมที่สามารถตัดประโยคเป็นคำเล็กๆ
เช่น I programmed this language => [I, programmed, this, language]

Tokenizer? Lexer? คืออย่างเดียวกันมั้ย

โดย concept แล้ว lexer เป็น tokenizer ครับ โดยปกติ tokenizer จะแค่หั่นประโยคเป็น คำสั้นๆ แต่ lexer จะหั่นแล้วมีข้อมูลเพิ่มเติมติดมาด้วยเช่น token นี้มาจาก บรรทัดไหนอะไรประมาณนั้น

ดังนั้นสรุปเลยว่า Lexer คือ Tokenizer ชนิดนึงครับ

Parser คืออะไร?
สั้น ๆง่าย ๆ คือ ตัวแปลง tokens ให้เป็น data structure ตัวอื่น เช่น Parse tree, Abstract syntax tree, Action tree และ อื่นๆ ซึ่งสามารถนำไปใช้งานต่อได้ง่ายกว่า tokens เพราะ parser จะทำการตรวจสอบความถูกต้อง ของ syntax แล้ว

Lexer เขียนรวมกับ Parser ได้ไหม?
คำตอบคือ ได้ครับ แต่จะเพิ่มยุ่งยากในบางงานที่มี syntax ซับซ้อน แต่ผมจะเขียนรวมกันไปเลยเพราะ BSM มี syntax ไม่ซับซ้อน

คราวก็ถึงตาของ BSM ว่าผมจะเขียน Lexer และ Parser ยังไง
โดยภาษาที่ผมใช้เขียน BSM นั้นจะเป็นภาษา rust ครับ

fn parse(input: &str) -> Result<Vec<FUNCTION>, &str> {
    let mut funcs: Vec<FUNCTION> = Vec::new();
    let mut insts: Vec<INSTRUCTION> = Vec::new();
    let mut name = "START";
    for line in input.split("\n") {
        let trimmed = line.trim();
        let key = trimmed[0..4].trim();
        let params: Vec<&str> = trimmed[key.len() + 1..].split(",").map(|v| v.trim()).collect();
        match key {
            "SET" | "ADD" | "SUB" | "MULT" | "DIV" | "CMP" => {
                check_params(2, params.len())?;
                check_register(params[0])?;
                check_value(params[1])?;
                insts.push((key.to_string(), params))
            }
            "JMPZ" | "JMP" => {
                check_params(1, params.len())?;
                check_number(params[0])?;
                insts.push((key.to_string(), params))
            }
            "PRNT" => {
                check_params(1, params.len())?;
                check_value(params[0])?;
                insts.push((key.to_string(), params))
            }
            "CALL" => {
                check_params(1, params.len())?;
                check_function(&funcs, params[0])?;
                insts.push((key.to_string(), params))
            }
            _ => {
                return Err("Your Code is bad");
            }
        }
    }
    funcs.push((name.to_string(), insts.clone()));
    insts.clear();
    Ok(funcs)
}

หากยังจำกันได้ว่า parser จะแปลง input ให้กลายเป็น data structure ตัวอื่นๆ
ซึ่งอันนี้ก็อยู่ในรูปของ Array<Function> ที่ง่ายต่อการเอาไป interpret ครับ

Step 3. นำ output จาก Parser ไปใช้

คราวนี้มาถึงขั้นตอนเกือบสุดท้ายกันแล้ว คือการเอา output จาก parser ของเราไปใช้ต่อ

เช่น
- นำไปแปลงเป็น ภาษาอื่นๆที่ เราเรียกกันว่า transpiling
- นำไป interpreting

Compiler ก็นับว่าเป็น Transpiler ชนิดนึงนะถ้าดูแค่หลักการทำงาน
แปลง tree ตัวนึงให้กลายเป็น ภาษาเครื่องไรงี้

แต่ BSM ของผมเป็น interpreter ดังนั้นเราก็มาทำกันเลย แต่ก่อนจะมาเขียนกันเราต้องอย่าลืมว่า ใน design ของเรามีสิ่งที่เรียก function อยู่ชื่อ คำสั่ง CALL โดยเราจะต้องมาคิดถึงเรื่องพฤติกรรมของ CALL กันก่อนว่าหลังจากใช้ CALL แล้วเราจะกระโดดไป Function แล้วกลับมาที่ Function ที่เรียก CALL หรือไม่

ซี่งภาษาของผมหลังจาก CALL function แล้วจะกลับมาที่ Function เดิมด้วยดังนั้นเราจึงต้องมีสิ่งที่เรียกว่า Stack เพื่อเก็บ state การทำงานก่อนหน้าเอาไว้ เมื่อเราใช้งาน Function เราจะ Push state เข้าไปใน stack หลังจากนั้นก็ Pop state ออกเมื่อ function ที่เรา CALL ทำงานเสร็จ

และนี่คือ code คร่าวของ interpreter ของผมครับ

fn bsm(input: &str) -> Result<(), &str> {
  ....
  let funcs = parse(input)?;
  let start_fn_idx = find_function(&funcs, "START")?;
  let mut stack: Vec<(usize, usize)> = vec![(start_fn_idx, 0)];
  // loop ไปเรื่อยๆ
  loop {
    let (fn_idx, mut index) = match stack.pop() {
        Some(e) => e,
        None => {
            // หยุดเมื่อ stack หมด
          break;
        }
    };
    // ทำงานจนกว่า function จะจบ
    while index < funcs[fn_idx].1.len() {
      let (inst, params) = &funcs[fn_idx].1[index];
      index += 1;
      match inst.as_str() {
        ...
        "JMP" => {
            if T != 0 {
                index = to_number(params[0])? as usize - 1;
            }
        }
        "JMPZ" => {
            if T == 0 {
                index = to_number(params[0])? as usize - 1;
            }
        }
        "PRNT" => {
            println!("{}", convert(A, B, C, params[0])?);
        }
        "CALL" => {
            let idx = find_function(&funcs, params[0])?;
            stack.push((fn_idx, index)); // เก็บ state ของ function เก่า
            stack.push((idx, 0)); // push state ของ function ใหม่
            break;
        }
        ...
      }
    }
  }
}

แล้วก็จบกันไปแล้วครับกับ blog การสร้างภาษาแบบสั้น ๆ
แจก wrap ครับตามไปอ่าน code กันได้

GitHub - boon4681/bsm: BSM, Assembly but it's boon4681

แล้วมาเจอกันใหม่ใน blog ต่อไปของผมในการมาสอนเขียน interpreter ครับ
อาจจะมาเป็น part เลยเนอะ รอติดตามกันได้เลย