parser — ไวยากรณ์ที่กลายเป็น function

บทที่ 2 ออกแบบต้นไม้ไว้เสร็จแล้ว แต่ยังไม่มีใครประกอบมันขึ้นมาจากลำดับ token

งานนั้นเป็นของ parser และวิธีที่คอร์สนี้ใช้ชื่อว่า Recursive Descent

หลักของมันสั้นกว่าที่ชื่อทำให้กลัว คือกฎไวยากรณ์หนึ่งข้อเท่ากับ function หนึ่งตัว แล้วปล่อยให้ function เรียกกันตามที่กฎอ้างถึงกัน

ไวยากรณ์อยู่ในหัวของ file เดียวกับ parser

หัวข้อนี้แสดงไวยากรณ์ทั้งชุดที่เขียนไว้ในหัวของ parser.rs พร้อมวิธีอ่านสัญลักษณ์ในนั้น

Grammar คือชุดกฎที่บอกว่าลำดับ token แบบไหนนับเป็นโปรแกรมที่ถูกต้อง

//! program     → declaration* EOF
//! declaration → classDecl | funDecl | varDecl | statement
//! classDecl   → "class" IDENTIFIER "{" function* "}"
//! funDecl     → "fun" function
//! function    → IDENTIFIER "(" parameters? ")" block
//! varDecl     → "var" IDENTIFIER ( "=" expression )? ";"
//! statement   → exprStmt | printStmt | block | ifStmt | whileStmt | forStmt | returnStmt
//! expression  → assignment
//! assignment  → ( call "." )? IDENTIFIER "=" assignment | logic_or
//! logic_or    → logic_and ( "or" logic_and )*
//! logic_and   → equality ( "and" equality )*
//! equality    → comparison ( ( "!=" | "==" ) comparison )*
//! comparison  → term ( ( ">" | ">=" | "<" | "<=" ) term )*
//! term        → factor ( ( "-" | "+" ) factor )*
//! factor      → unary ( ( "/" | "*" ) unary )*
//! unary       → ( "!" | "-" ) unary | call
//! call        → primary ( "(" arguments? ")" | "." IDENTIFIER )*
//! primary     → NUMBER | STRING | "true" | "false" | "nil" | "this"
//!             | "(" expression ")" | IDENTIFIER

สัญลักษณ์ที่ต้องอ่านออกมีสี่ตัว

→ อ่านว่า “ประกอบขึ้นจาก”
| คืออย่างใดอย่างหนึ่ง
* คือซ้ำกี่ครั้งก็ได้ รวมทั้งศูนย์ครั้ง
? คือมีหรือไม่มีก็ได้

ชื่อของกฎกับชื่อของ function ใน file เดียวกันตรงกันทุกตัว อ่านไวยากรณ์จบแล้วเดาโครงของ code ออกทันที

การวางไวยากรณ์ไว้ใน file เดียวกับ parser ไม่ใช่เรื่องความสวยงาม เอกสารที่อยู่คนละที่กับสิ่งที่มันอธิบายจะเหลื่อมกันในที่สุด และชั้นที่ผิดคือชั้นที่คนอ่านก่อน

ลำดับความสำคัญคือลำดับการเรียก

หัวข้อนี้แสดงว่าลำดับความสำคัญถูกเข้ารหัสด้วยลำดับที่ function เรียกกัน ไม่ใช่ด้วยตารางที่เขียนแยกไว้

Precedence ในตำราส่วนใหญ่ถูกอธิบายด้วยตารางที่ไล่จากตัวที่จับแน่นที่สุดลงมา ใน recursive descent ตารางแบบนั้นไม่มีอยู่จริง

    /// loop `while` ที่พอกต้นไม้ทับซ้ายเรื่อยๆ คือที่มาของ "ซ้ายไปขวา":
    /// `1 - 2 - 3` กลายเป็น `(- (- 1 2) 3)` ไม่ใช่ `(- 1 (- 2 3))`
    fn term(&mut self) -> PResult<Expr> {
        let mut expr = self.factor()?;
        while self.matches(&[TokenKind::Minus, TokenKind::Plus]) {
            let tok = self.previous().clone();
            let op = if tok.kind == TokenKind::Minus { BinaryOp::Sub } else { BinaryOp::Add };
            let right = self.factor()?;
            expr = binary(expr, op, tok.line, right);
        }
        Ok(expr)
    }

    fn factor(&mut self) -> PResult<Expr> {
        let mut expr = self.unary()?;
        while self.matches(&[TokenKind::Slash, TokenKind::Star]) {
            let tok = self.previous().clone();
            let op = if tok.kind == TokenKind::Slash { BinaryOp::Div } else { BinaryOp::Mul };
            let right = self.unary()?;
            expr = binary(expr, op, tok.line, right);
        }
        Ok(expr)
    }

term เรียก factor ก่อนเสมอ แปลว่า factor เก็บ * กับ / ไปครบแล้ว ก่อนที่ term จะได้เห็น + ตัวแรกด้วยซ้ำ

ผลคือการคูณกลายเป็นลูกของการบวกโดยอัตโนมัติ และไม่มีใครเขียนกฎข้อนั้นไว้ที่ไหนเลย

flowchart TD
    A["expression"] --> B["assignment · ="]
    B --> C["or"]
    C --> D["and"]
    D --> E["equality · == !="]
    E --> F["comparison · &lt; &lt;= &gt; &gt;="]
    F --> G["term · + -"]
    G --> H["factor · * /"]
    H --> I["unary · ! -"]
    I --> J["call · () ."]
    J --> K["primary · ตัวเลข · ข้อความ · ชื่อ · วงเล็บ"]

คำบรรยายภาพ: บันไดของการเรียก · ยิ่งอยู่ล่างยิ่งจับแน่น เพราะมันได้เห็น token ก่อน · ลำดับความสำคัญทั้งหมดของภาษาอยู่ในรูปนี้ ไม่ได้อยู่ในตารางที่ไหน

primary ที่อยู่ล่างสุดคือค่าเดี่ยวที่ไม่มีอะไรจับแน่นกว่ามันได้อีก ทุกการเรียกจึงต้องลงไปสุดบันไดก่อน แล้วค่อยพอกกลับขึ้นมา

ราคาที่ติดมากับการเข้ารหัสแบบนี้

หัวข้อย่อยนี้บอกว่าการเก็บลำดับความสำคัญไว้ในลำดับการเรียกทำให้อะไรแพงขึ้น

ลำดับความสำคัญไม่มีที่ให้อ่านรวดเดียว ต้องไล่ตามสายการเรียกทีละขั้นถึงจะเห็นภาพรวม ไวยากรณ์ในหัว file จึงมีไว้ชดเชยข้อนี้โดยตรง

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

จุดนี้ต่างจาก enum ในบทที่ 2 อย่างชัดเจน ที่นั่นการลืมกรณีคือคอมไพล์ไม่ผ่าน ส่วนที่นี่การลืมเชื่อมสายคือ code ที่รันได้แต่ให้ต้นไม้ผิดรูป

ทุก expression ต้องเดินลงบันไดครบทุกขั้นก่อนจะถึงค่าเดี่ยว แม้แต่ตัวเลขโดดๆ ตัวเดียวก็ผ่าน function ทุกตัวในสาย

กฎที่เขียนแบบเรียกตัวเองทางซ้ายไม่ได้เลย

ถ้าเขียนกฎเป็น term → term ( "-" | "+" ) factor ตามที่ตำราคณิตศาสตร์นิยมเขียนกัน function term จะเรียกตัวเองเป็นอย่างแรกโดยยังไม่ได้กิน token สักตัว แล้ววนไม่จบ

ข้อจำกัดนี้เรียกว่า left recursion และเป็นเหตุผลที่ไวยากรณ์ข้างบนเขียนกฎเดียวกันนี้เป็น term → factor ( ( "-" | "+" ) factor )* แทน คือกินตัวซ้ายก่อนแล้วค่อยวน

recursive descent แลกความอ่านง่ายมาด้วยการที่ไวยากรณ์ต้องถูกจัดรูปให้เข้ากับมันก่อน

จับจากซ้าย กับจับจากขวา

หัวข้อนี้แสดงว่ารูปแบบของ code ตัดสินทิศที่ตัวดำเนินการระดับเดียวกันจับคู่กัน คือ loop ให้ซ้ายไปขวา ส่วนการเรียกตัวเองให้ขวาไปซ้าย

Associativity ตอบคำถามคนละข้อกับลำดับความสำคัญ

ใน 1 - 2 - 3 เครื่องหมายลบสองตัวอยู่ระดับเดียวกัน คำถามคือตัวไหนจับคู่ก่อน และคำตอบเปลี่ยนค่าที่ได้จริงๆ เพราะการลบไม่ได้ให้ผลเท่ากันทั้งสองทาง

while ใน term พอกต้นไม้ทับซ้ายไปเรื่อยๆ รอบที่สองรับต้นไม้ของรอบแรกมาเป็นลูกฝั่งซ้าย ผลจึงเป็นซ้ายไปขวาโดยไม่ต้องประกาศอะไรเพิ่ม

ตรงข้ามกันคือ unary ที่เรียกตัวเองแทนที่จะวน

    fn unary(&mut self) -> PResult<Expr> {
        if self.matches(&[TokenKind::Bang, TokenKind::Minus]) {
            let tok = self.previous().clone();
            let op = if tok.kind == TokenKind::Bang { UnaryOp::Not } else { UnaryOp::Neg };
            // เรียกตัวเอง ไม่ใช่ loop — `- - 3` จึงจับขวาไปซ้าย
            let right = self.unary()?;
            return Ok(Expr::Unary { op, line: tok.line, right: Box::new(right) });
        }
        self.call()
    }

assignment ใช้ท่าเดียวกัน มันเรียกตัวเองที่ฝั่งขวาของ = ผลรันของบทนี้จึงมี (= a (= b 3)) ที่ซ้อนเข้าไปทางขวา ไม่ใช่ทางซ้าย

flowchart TD
    subgraph LEFT["while · ซ้ายไปขวา · ได้ (- (- 1 2) 3)"]
        A1["ลบ ตัวนอก"] --> A2["ลบ ตัวใน"]
        A1 --> A3["3"]
        A2 --> A4["1"]
        A2 --> A5["2"]
    end
    subgraph RIGHT["เรียกตัวเอง · ขวาไปซ้าย · ได้ (- 1 (- 2 3))"]
        B1["ลบ ตัวนอก"] --> B2["1"]
        B1 --> B3["ลบ ตัวใน"]
        B3 --> B4["2"]
        B3 --> B5["3"]
    end

คำบรรยายภาพ: ต้นไม้ของ 1 - 2 - 3 สองแบบ · ฝั่งซ้ายคือสิ่งที่ loop ให้ ฝั่งขวาคือสิ่งที่การเรียกตัวเองให้ · ทั้งสองรูปนี้คำนวณออกมาได้คนละค่า

error แรกไม่ควรเป็น error สุดท้าย

หัวข้อนี้อธิบายกลไกที่ทำให้ parser รายงานจุดพังได้หลายจุดในรอบเดียว และราคาที่ติดมากับกลไกนั้น

parser ที่หยุดที่ error แรกบังคับให้คนแก้ทีละจุดแล้วรันใหม่ วนอยู่อย่างนั้นจนกว่าจะหมด

    /// จุดเดียวใน file นี้ที่ *กู้* จาก error
    ///
    /// ถ้า parser ยอมแพ้ที่ error แรก ผู้เรียนจะเห็นทีละหนึ่งข้อ แก้แล้วรันใหม่ วนไป
    /// `synchronize()` จึงทิ้ง token จนถึงจุดที่น่าจะเป็นต้นคำสั่งถัดไป แล้วอ่านต่อ
    /// ผลคือ file ที่พังสองจุดรายงานสองข้อในรอบเดียว
    fn declaration(&mut self) -> Option<Stmt> {
        let result = if self.matches(&[TokenKind::Class]) {
            self.class_declaration()
        } else if self.matches(&[TokenKind::Fun]) {
            self.function("function").map(Stmt::Function)
        } else if self.matches(&[TokenKind::Var]) {
            self.var_declaration()
        } else {
            self.statement()
        };

        match result {
            Ok(stmt) => Some(stmt),
            Err(e) => {
                self.errors.push(e);
                self.synchronize();
                None
            }
        }
    }

declaration เป็นจุดเดียวใน file ที่ดัก error ไว้แทนที่จะส่งต่อขึ้นไป มันจดข้อความไว้ เรียกกลไกที่เรียกว่า Synchronization แล้วคืน None เพื่อบอกว่ารอบนี้ไม่ได้ต้นไม้

    /// ทิ้ง token จนถึงจุดที่น่าจะเป็นต้นคำสั่งถัดไป
    ///
    /// "น่าจะ" คือคำที่ถูกต้อง — มันเดาเอา ไม่ได้รู้จริง จุดตัดคือหลัง `;`
    /// หรือก่อนคำสงวนที่ขึ้นต้นคำสั่งได้ ผลที่ตามมาคือบางครั้งรายงาน error ปลอม
    /// ตามหลังของจริง ซึ่งเป็นราคาที่ยอมจ่ายเพื่อให้รายงานได้หลายข้อในรอบเดียว
    fn synchronize(&mut self) {
        if !self.is_at_end() {
            self.advance();
        }
        while !self.is_at_end() {
            if self.previous().kind == TokenKind::Semicolon {
                return;
            }
            match self.peek().kind {
                TokenKind::Class
                | TokenKind::Fun
                | TokenKind::Var
                | TokenKind::For
                | TokenKind::If
                | TokenKind::While
                | TokenKind::Print
                | TokenKind::Return => return,
                _ => {
                    self.advance();
                }
            }
        }
    }

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

ราคาของการเดา และราคาของการไม่กู้เลย

เดาผิดได้สองทาง ทางหนึ่งคือทิ้ง code ที่ยังดีอยู่ไปด้วย อีกทางคือหยุดเร็วเกินจนพ่น error ปลอมตามหลังของจริง

แต่การไม่กู้เลยแย่กว่านั้น ถ้าเปลี่ยน synchronize เป็นการข้ามไปหนึ่ง token แล้วอ่านต่อทันที ตัวอย่างของบทนี้จะพ่น error ชุดใหม่เพิ่มขึ้นมาทั้งที่จุดพังจริงเท่าเดิม

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

ลองรันจริง

หัวข้อนี้อ่านผลของ parser บนตัวอย่างที่จงใจพังหลายจุด แล้วชี้ว่าอะไรพิสูจน์อะไร

ตัวอย่างของบทนี้แบ่งเป็นสองส่วน ส่วนบนถูกต้องทั้งหมดและมีไว้ให้ดูรูปร่างของต้นไม้ ส่วนล่างพังคนละแบบกันหลายจุด

// บทที่ 3 — ไวยากรณ์กลายเป็น function และ parser ที่พังต้องกู้ตัวเองให้ได้
1 + 2 * 3 - 4 / 2;
1 - 2 - 3;
- - 3;
1 < 2 == true;
a = b = 3;

// ห้าจุดข้างล่างพังคนละแบบ · parser ต้องรายงานให้ครบในรอบเดียว ไม่ใช่หยุดที่จุดแรก
1 +* 2;
var = 9;
h(1 2);
"parser กู้ตัวกลับมาอ่านต่อได้" + "!";
fun f(1) {}
fun g(a b) {}

// พังที่ท้าย file พอดี — ไม่มี token ให้ชี้แล้ว ตัวชี้ตำแหน่งจึงเป็น EOF
print 1 +

โหมด --ast พิมพ์ต้นไม้ที่ประกอบสำเร็จออกมาก่อนทั้งหมด แล้วค่อยตามด้วย error ทั้งหมด

(- (+ 1 (* 2 3)) (/ 4 2))
(- (- 1 2) 3)
(- (- 3))
(== (< 1 2) true)
(= a (= b 3))
(+ "parser กู้ตัวกลับมาอ่านต่อได้" "!")
[บรรทัด 9] ผิดพลาดตอนแยกไวยากรณ์ ที่ '*': ต้องการ expression
[บรรทัด 10] ผิดพลาดตอนแยกไวยากรณ์ ที่ '=': ต้องมีชื่อตัวแปรตามหลัง 'var'
[บรรทัด 11] ผิดพลาดตอนแยกไวยากรณ์ ที่ '2': ต้องมี ')' ปิดรายการ argument
[บรรทัด 13] ผิดพลาดตอนแยกไวยากรณ์ ที่ '1': ต้องมีชื่อ parameter
[บรรทัด 14] ผิดพลาดตอนแยกไวยากรณ์ ที่ 'b': ต้องมี ')' ปิดรายการ parameter
[บรรทัด 18] ผิดพลาดตอนแยกไวยากรณ์ ที่ EOF: ต้องการ expression

ผลนี้พิสูจน์สี่อย่างที่หัวข้อก่อนหน้าอ้างไว้

ลำดับความสำคัญกลายเป็นความลึกจริง 1 + 2 * 3 - 4 / 2; ออกมาเป็น (- (+ 1 (* 2 3)) (/ 4 2)) ทั้งการคูณและการหารจมอยู่ใต้เครื่องหมายบวกลบ
สองทิศของการจับคู่เห็นได้ในบรรทัดติดกัน 1 - 2 - 3; ให้ (- (- 1 2) 3) ซึ่งซ้อนไปทางซ้าย ส่วน - - 3; ให้ (- (- 3)) ซึ่งมาจาก function ที่เรียกตัวเอง
synchronize ทำงานจริง จุดพังหกจุดถูกรายงานครบในรอบเดียว และบรรทัด 12 ที่นั่งอยู่ระหว่างจุดพัง ยังถูกประกอบเป็น (+ "parser กู้ตัวกลับมาอ่านต่อได้" "!") ออกมาได้ตามปกติ
สองเส้นทางของการกู้ตัวถูกใช้คนละที่ จุดพังบนบรรทัด 11 จบด้วย ; parser จึงกลับมาที่บรรทัดถัดไปได้ ส่วนจุดพังบนบรรทัด 13 ไม่มี ; ให้เกาะ มันจึงเดินต่อไปจนเจอคำสงวน fun ของบรรทัดถัดไปแล้วเริ่มใหม่ตรงนั้น

ตำแหน่งที่พัง เมื่อไม่มี token ให้ชี้

หัวข้อย่อยนี้อธิบายว่าทำไม error สุดท้ายถึงชี้ไปที่ EOF แทนที่จะชี้ไปที่เครื่องหมายสักตัว

/// ข้อความสั้นๆ ที่บอกว่าพังตรง token ไหน
fn describe(tok: &Token) -> String {
    if tok.kind == TokenKind::Eof { "EOF".to_string() } else { format!("'{}'", tok.lexeme) }
}

token ทุกตัวมี lexeme ให้หยิบมาใส่ในข้อความ ยกเว้นตัวเดียวคือ Eof ซึ่งไม่ได้กินอักขระอะไรเลย

ถ้าปล่อยให้มันพิมพ์ lexeme ของตัวเอง ผู้อ่านจะได้ข้อความที่มีเครื่องหมายคำพูดว่างเปล่าอยู่ตรงกลาง แล้วต้องเดาเองว่าหมายถึงอะไร

บรรทัดสุดท้ายของผลรันจึงเป็น [บรรทัด 18] ผิดพลาดตอนแยกไวยากรณ์ ที่ EOF: ต้องการ expression ซึ่งบอกทั้งว่าพังเพราะอะไร และบอกว่าไม่มี token เหลือให้ชี้แล้ว

เทียบกับ [บรรทัด 10] ผิดพลาดตอนแยกไวยากรณ์ ที่ '=': ต้องมีชื่อตัวแปรตามหลัง 'var' ที่ยังมี token ให้ชี้ ข้อความจึงยกเครื่องหมายตัวนั้นมาแสดงตรงๆ

ต้นไม้พร้อมแล้ว แต่ยังไม่มีใครอ่านค่าออกมา

หัวข้อนี้บอกว่าบทนี้จบที่ต้นไม้ที่ถูกต้อง ส่วนการหาว่าต้นไม้แต่ละต้นมีค่าเท่าไรเป็นเรื่องของบทถัดไป

สิ่งที่ได้จากบทนี้คือต้นไม้ที่มีรูปร่างถูกต้อง และรายการจุดพังที่ครบในรอบเดียว

แต่ยังไม่มีที่ไหนเลยที่ถามว่าต้นไม้ต้นหนึ่งมีค่าเท่าไร โหมด --ast หยุดก่อนถึงคำถามนั้นพอดี

บทที่ 4 จะเดินบนต้นไม้แล้วประเมินค่าออกมา และที่นั่น match ตัวใหม่บนต้นไม้ตัวเดิม จะทำงานที่ตำราต้นทางต้องสร้าง visitor class ขึ้นมาอีกใบ

🔗 อ้างอิงต้นทางของบทนี้

Crafting Interpreters — Robert Nystrom, บทที่ 6 “Parsing Expressions” (ตรวจแล้ว 2026-08-12) — ที่มาของทั้งสี่เรื่องในบทนี้ คือ recursive descent ที่กฎหนึ่งข้อ เท่ากับ function หนึ่งตัว การแบ่งไวยากรณ์เป็นชั้นตามลำดับความสำคัญ ความต่างระหว่าง การจับจากซ้ายกับจากขวา และ panic mode ที่เป็นชื่อเดิมของกลไก synchronize ตัว code ในตำราเขียนด้วย Java ส่วนคอร์สนี้เขียน Rust ใหม่ทั้งหมด
The Rust Programming Language — บทที่ 6 “Enums and Pattern Matching” (ตรวจแล้ว 2026-08-12) — ที่มาของ Option ที่ declaration ใช้คืนค่า และของ match ที่ synchronize ใช้แยกคำสงวนออกจาก token อื่น

เช็กความเข้าใจ — บทที่ 3

ข้อ 1 / 3

ในไวยากรณ์ของ nok ไม่มีตารางลำดับความสำคัญอยู่เลยสักที่ ถ้าสลับสายการเรียกให้ factor เป็นตัวที่เรียก term แทนที่จะเป็น term เรียก factor แล้วให้ parser อ่านบรรทัด 1 + 2 * 3; จะได้ต้นไม้แบบไหน

parser — ไวยากรณ์​ที่​กลาย​เป็น function

ไวยากรณ์​อยู่​ใน​หัว​ของ file เดียว​กับ parser

ลำดับ​ความ​สำคัญ​คือ​ลำดับ​การ​เรียก

ราคา​ที่​ติด​มา​กับ​การ​เข้า​รหัส​แบบ​นี้

จับ​จาก​ซ้าย กับ​จับ​จาก​ขวา

error แรก​ไม่​ควร​เป็น error สุดท้าย

ลอง​รัน​จริง

ตำแหน่ง​ที่​พัง เมื่อ​ไม่มี token ให้​ชี้

ต้นไม้​พร้อม​แล้ว แต่​ยัง​ไม่มี​ใคร​อ่าน​ค่า​ออก​มา