Lesson 04 β€” Recursive-Descent Parser

BiαΊΏn dΓ£y token phαΊ³ng thΓ nh cΓ’y AST Δ‘ΓΊng Δ‘α»™ Ζ°u tiΓͺn. Ba module tΖ°Ζ‘ng tΓ‘c: chαΊ‘y parser tα»«ng bΖ°α»›c (call stack + AST dα»±ng dαΊ§n), xem cΓ’y AST hoΓ n chỉnh, vΓ  demo lα»—i cΓΊ phΓ‘p.

E β†’ T ( '+' | '-' T )*   (parseExpr)
T β†’ F ( '*' | '/' F )*   (parseTerm)
F β†’ '(' E ')' | num     (parseFactor)

Grammar Δ‘Γ£ khα»­ đệ quy trΓ‘i: mα»—i non-terminal = mα»™t hΓ m. */ ở tαΊ§ng sΓ’u (T) β†’ Ζ°u tiΓͺn cao hΖ‘n +- (tαΊ§ng E).

1. Parser Stepper β€” chαΊ‘y tα»«ng bΖ°α»›c

NhαΊ­p biểu thα»©c (sα»‘ nguyΓͺn, + - * /, ngoαΊ·c). BαΊ₯m BΖ°α»›c tiαΊΏp để theo dΓ΅i tα»«ng lời gọi hΓ m; Tα»± chαΊ‘y để chαΊ‘y chαΊ­m tα»± Δ‘α»™ng.
MαΊ«u:

Token stream

Call stack (hΓ m Δ‘ang chαΊ‘y, đỉnh trΓͺn cΓΉng)

β€” bαΊ₯m NαΊ‘p để bαΊ―t Δ‘αΊ§u β€”

AST Δ‘ang dα»±ng

cΓ’y sαΊ½ hiện dαΊ§n…

NhαΊ­t kΓ½ bΖ°α»›c

…

2. AST Viewer β€” vαΊ½ cΓ’y hoΓ n chỉnh

NhαΊ­p biểu thα»©c bαΊ₯t kα»³ β†’ parse mα»™t lαΊ§n, vαΊ½ AST Δ‘αΊ§y đủ. BαΊ₯m vΓ o node để xem loαΊ‘i node.
MαΊ«u:
BαΊ₯m vΓ o mα»™t node để xem chi tiαΊΏt.

3. Syntax Error Demo β€” token nΓ o gΓ’y lα»—i?

NhαΊ­p biểu thα»©c SAI β†’ parser chỉ ra token gΓ’y lα»—i vΓ  message expect … got … sinh ra ở expect/parseFactor.
MαΊ«u lα»—i:

Token stream (token đỏ = gΓ’y lα»—i)