C Academy · บทเรียน

แยกวิเคราะห์นิพจน์

สร้างต้นไม้การแยกวิเคราะห์

แยกวิเคราะห์นิพจน์ เป็นบทเรียน C Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน C Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส C Academy มีบทเรียนทั้งหมด 4 บทเรียน

จากโทเค็นสู่ต้นไม้

การแยกวากยสัมพันธ์จะเปลี่ยนลำดับโทเค็นแบบแบนให้เป็น ต้นไม้วากยสัมพันธ์นามธรรม (AST) ที่มีโครงสร้าง ต้นไม้นี้เข้ารหัสลำดับความสำคัญและการจัดกลุ่มที่โทเค็นดิบสื่อไว้เพียงโดยนัย

สำหรับ 3 + 4 * 2 AST จะซ้อนการคูณไว้ภายใต้การบวก จึงประเมินค่าได้เป็น 11 ไม่ใช่ 14

รูปแบบโหนด AST

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

อักขระตัวดำเนินการใช้แยกความแตกต่างระหว่าง +, -, * และ / ขณะทำงาน

typedef struct Node {
  enum { N_NUM, N_BINOP } kind;
  union {
    int value;                 /* N_NUM */
    struct {                   /* N_BINOP */
      char op;
      struct Node *left, *right;
    } bin;
  };
} Node;

การจัดสรรโหนด

ตัวสร้างขนาดเล็กสองตัวจะจัดสรรโหนดบน heap การสร้างต้นไม้จากล่างขึ้นบนหมายความว่าเราจะสร้างใบไม้ก่อน แล้วจึงห่อใบไม้เหล่านั้นด้วยโหนดตัวดำเนินการ

ในตัวแปลภาษาสำหรับใช้งานจริง คุณจะต้องติดตามการจัดสรรเหล่านี้เพื่อคืนพื้นที่ในภายหลัง

#include <stdlib.h>

static Node *num(int v) {
  Node *n = malloc(sizeof *n);
  n->kind = N_NUM; n->value = v;
  return n;
}

static Node *binop(char op, Node *l, Node *r) {
  Node *n = malloc(sizeof *n);
  n->kind = N_BINOP;
  n->bin.op = op; n->bin.left = l; n->bin.right = r;
  return n;
}

ไวยากรณ์

เราใช้ไวยากรณ์ที่จัดลำดับความสำคัญแบบคลาสสิก โดย expr จัดการกับ + และ - ส่วน term จัดการกับ * และ / และ factor จัดการกับตัวเลขและวงเล็บ

เนื่องจากกฎที่มีลำดับความสำคัญสูงกว่าอยู่ในระดับที่ลึกกว่า การคูณจึงผูกแน่นกว่าการบวกโดยอัตโนมัติ

/* Grammar (EBNF):
   expr   = term   { ('+' | '-') term } ;
   term   = factor { ('*' | '/') factor } ;
   factor = NUMBER | '(' expr ')' ; */

การจับคู่โทเค็น

ตัวช่วย expect จะใช้โทเค็นที่มีชนิดตามที่กำหนด หรือยุติการทำงาน ตัวช่วยนี้เป็นข้อตกลงระหว่างตัวแยกวิเคราะห์กับตัววิเคราะห์คำศัพท์

เราใช้ตัวช่วยดูข้อมูลล่วงหน้า cur และ bump จากบทเรียนตัวสร้างโทเค็นซ้ำ

#include <stdio.h>
#include <stdlib.h>

static void expect(TokKind k) {
  if (cur().kind != k) {
    fprintf(stderr, "parse error: unexpected token\n");
    exit(1);
  }
  bump();
}

การแยกวิเคราะห์ตัวประกอบ

ตัวประกอบคือหน่วยอะตอมของไวยากรณ์ ซึ่งอาจเป็นตัวเลขตามตัวอักษรหรือส่วนย่อยของนิพจน์ที่อยู่ในวงเล็บ วงเล็บจะเรียกกลับเข้าไปยัง parse_expr แบบเรียกซ้ำ

การเรียกซ้ำนี้เองที่ทำให้ตัวแยกวิเคราะห์แบบไล่ลงตามการเรียกซ้ำมีชื่อนี้

static Node *parse_expr(void);

static Node *parse_factor(void) {
  if (cur().kind == TOK_NUM) {
    int v = cur().value; bump();
    return num(v);
  }
  expect(TOK_LPAREN);
  Node *e = parse_expr();
  expect(TOK_RPAREN);
  return e;
}

การแยกวิเคราะห์พจน์

พจน์จะแยกวิเคราะห์ตัวประกอบหนึ่งตัวก่อน จากนั้นวนซ้ำขณะที่พบ * หรือ / โดยรวมแต่ละรายการเข้าเป็นโหนดการดำเนินการแบบไบนารีที่จับกลุ่มจากซ้ายไปขวา

การจับกลุ่มจากซ้ายไปขวาหมายความว่า 8 / 4 / 2 จะถูกแยกวิเคราะห์เป็น (8 / 4) / 2 = 1

static Node *parse_term(void) {
  Node *left = parse_factor();
  while (cur().kind == TOK_STAR || cur().kind == TOK_SLASH) {
    char op = (cur().kind == TOK_STAR) ? '*' : '/';
    bump();
    left = binop(op, left, parse_factor());
  }
  return left;
}

การแยกวิเคราะห์นิพจน์

กฎระดับบนสุดมีรูปแบบคล้าย parse_term แต่จัดการกับ + และ - แต่ละระดับจะเรียกกฎที่มีลำดับความสำคัญสูงกว่าระดับถัดไป จึงทำให้ต้นไม้มีการซ้อนกันอย่างถูกต้อง

โครงสร้างสามฟังก์ชันนี้คือหัวใจของตัวแยกวิเคราะห์

static Node *parse_expr(void) {
  Node *left = parse_term();
  while (cur().kind == TOK_PLUS || cur().kind == TOK_MINUS) {
    char op = (cur().kind == TOK_PLUS) ? '+' : '-';
    bump();
    left = binop(op, left, parse_term());
  }
  return left;
}

การตรวจสอบต้นไม้

โปรแกรมนี้จะแยกวิเคราะห์นิพจน์ แล้วพิมพ์กลับออกมาในรูปแบบที่ใส่วงเล็บครบทุกส่วน เพื่อแสดงให้เห็นว่ามีการแก้ลำดับความสำคัญอย่างไร

ตัวจัดรูปแบบผลลัพธ์จะเรียกซ้ำผ่านโครงสร้างโหนดเดียวกับที่ตัวแยกวิเคราะห์สร้างขึ้น

#include <stdio.h>

typedef struct Node {
  int is_num; int value;
  char op; struct Node *l, *r;
} Node;

static Node *N(int v){ Node*n=calloc(1,sizeof*n); n->is_num=1; n->value=v; return n; }
static Node *B(char o,Node*a,Node*b){ Node*n=calloc(1,sizeof*n); n->op=o; n->l=a; n->r=b; return n; }

static void show(Node *n){
  if (n->is_num){ printf("%d", n->value); return; }
  printf("("); show(n->l); printf(" %c ", n->op); show(n->r); printf(")");
}

int main(void){
  /* 3 + 4 * 2  ->  (3 + (4 * 2)) */
  Node *ast = B('+', N(3), B('*', N(4), N(2)));
  show(ast); printf("\n");
  return 0;
}

การหลีกเลี่ยงการเรียกซ้ำจากซ้าย

ไวยากรณ์แบบตรงไปตรงมา เช่น expr = expr '+' term จะทำให้ parse_expr เรียกตัวเองไม่สิ้นสุด การแยกวิเคราะห์แบบไล่ลงตามการเรียกซ้ำไม่สามารถจัดการการเรียกซ้ำจากซ้ายโดยตรงได้

การเขียนกฎใหม่เป็นลูป while ที่วนผ่าน { '+' term } จะหลีกเลี่ยงการเรียกซ้ำไม่สิ้นสุดได้ทั้งหมด

เหตุใดจึงต้องใช้ AST

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

ถัดไปเราจะเดินผ่านต้นไม้นี้เพื่อคำนวณค่า

ตรวจสอบความเข้าใจ

ลองพิจารณาว่าการแบ่งชั้นของไวยากรณ์บังคับใช้ลำดับความสำคัญอย่างไร

สรุปทบทวน

คุณได้เขียนตัวแยกวิเคราะห์แบบไล่ลงตามการเรียกซ้ำ ซึ่งประกอบด้วยโครงสร้างโหนด AST ตัวสร้าง และฟังก์ชัน expr/term/factor ที่เข้ารหัสลำดับความสำคัญและการจับกลุ่มจากซ้ายไปขวา

ต้นไม้ที่ได้พร้อมสำหรับการประเมินผลแล้ว

คำถามที่พบบ่อย

บทเรียน “แยกวิเคราะห์นิพจน์” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “แยกวิเคราะห์นิพจน์” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส C Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส C Academy มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “แยกวิเคราะห์นิพจน์”

สร้างต้นไม้การแยกวิเคราะห์ คุณปฏิบัติ C Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน C Academy หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน C Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน

บทเรียน “แยกวิเคราะห์นิพจน์” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน C Academy นี้ได้ไหม

ได้ บทเรียน C Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

← กลับไปที่ C Academy