Lesson 03 — Văn phạm phi ngữ cảnh (Grammar & CFG)

Ba công cụ tương tác: dựng cây phân tích từng bước theo grammar phân tầng, so sánh hai cây của một grammar nhập nhằng (14 vs 20), và kiểm tra một dãy token có hợp lệ về cú pháp không.

1. Derivation Stepper — dựng cây phân tích từng bước

Dùng grammar phân tầng (không nhập nhằng, đã mã hoá ưu tiên * > + và trái-kết-hợp):

E → E + T | E - T | T T → T * F | T / F | F F → ( E ) | num

Chuỗi:

Mẫu:

2. Ambiguity Demo — một chuỗi, hai cây, hai giá trị

Grammar nhập nhằng E → E + E | E * E | ( E ) | num chấp nhận hai cây khác nhau cho cùng 2 + 3 * 4. Cây trái lấy * trước (đúng) → 14; cây phải lấy + trước (sai) → 20.

Cây A — áp E → E + E ở gốc

3 * 4 = 12, rồi 2 + 12

= 14 ✓ (đúng quy ước toán)

Cây B — áp E → E * E ở gốc

2 + 3 = 5, rồi 5 * 4

= 20 ✗ (sai — bỏ * ưu tiên)

→ Một grammar cho ra hai cây = nguy hiểm. Grammar phân tầng ở Module 1 loại bỏ cây B ngay từ thiết kế: ở đó 2 + 3 * 4 chỉ có MỘT cây = 14.

3. Kiểm tra chuỗi hợp lệ — accepted / rejected

Nhập dãy token (cách nhau bởi dấu cách): dùng num hoặc số, + - * / ( ). Công cụ chạy parser theo grammar phân tầng và báo chuỗi có thuộc ngôn ngữ không — đúng như câu hỏi mở bài "vì sao 2 + * 3 bị bác bỏ".

Mẫu: