Lesson 05 β€” Pratt Parsing / Precedence Climbing

Mα»™t hΓ m parseExpr(minbp) thay cho cαΊ£ chα»₯c hΓ m phΓ’n tαΊ§ng. Ba module tΖ°Ζ‘ng tΓ‘c: chαΊ‘y thuαΊ­t toΓ‘n tα»«ng bΖ°α»›c vα»›i cΓ’y dα»±ng dαΊ§n, so kαΊΏt hợp trΓ‘i vs phαΊ£i, vΓ  chỉnh binding power để thαΊ₯y cΓ’y Δ‘α»•i hΓ¬nh.

1. Pratt Stepper β€” chαΊ‘y thuαΊ­t toΓ‘n tα»«ng bΖ°α»›c

NhαΊ­p biểu thα»©c (toΓ‘n tα»­ + - * / ^, ngoαΊ·c ( ), unary -). Chỉnh binding power trong bαΊ£ng nαΊΏu muα»‘n. BαΊ₯m ChαΊ‘y tα»«ng bΖ°α»›c rα»“i BΖ°α»›c β–Έ để xem minbp hiện tαΊ‘i, cΓ’y dα»±ng dαΊ§n, vΓ  giΓ‘ trα»‹ tΓ­nh ra.

MαΊ«u:

BαΊ£ng binding power (chỉnh được)

toÑn tửlbpkết hợprbp (suy ra)

TrΓ‘i-kαΊΏt-hợp β†’ rbp = lbp + 1. PhαΊ£i-kαΊΏt-hợp β†’ rbp = lbp βˆ’ 1. Đổi sα»‘/kαΊΏt hợp rα»“i ChαΊ‘y tα»«ng bΖ°α»›c lαΊ‘i để thαΊ₯y αΊ£nh hưởng.

NhαΊ­t kΓ½ thuαΊ­t toΓ‘n

BαΊ₯m "ChαΊ‘y tα»«ng bΖ°α»›c" để bαΊ―t Δ‘αΊ§u.

2. Associativity Demo β€” trΓ‘i vs phαΊ£i, hai cΓ’y khΓ‘c nhau

CΓΉng mα»™t loαΊ‘i toΓ‘n tα»­ lαΊ·p lαΊ‘i, nhΖ°ng kαΊΏt hợp trΓ‘i vΓ  kαΊΏt hợp phαΊ£i dα»±ng cΓ’y khΓ‘c nhau β†’ giΓ‘ trα»‹ khΓ‘c nhau. ĐÒy lΓ  Δ‘iều mΓ  rbp = lbp Β± 1 Δ‘iều khiển.

TrÑi-kết-hợp: 8 - 3 - 2
rbp(-) = lbp + 1 β†’ toΓ‘n tα»­ cΓΉng mα»©c KHΓ”NG lọt vΓ o đệ quy β†’ gom vΓ²ng ngoΓ i.
CΓ’y:
Phải-kết-hợp: 2 ^ 3 ^ 2
rbp(^) = lbp βˆ’ 1 β†’ toΓ‘n tα»­ cΓΉng mα»©c LỌT vΓ o đệ quy β†’ gom bΓͺn phαΊ£i trΖ°α»›c.
CΓ’y:

BαΊ£n lề: ở 8-3-2, -β‚‚ cΓ³ lbp 30 vs minbp 31 (= rbp của -₁) β†’ 30 > 31 sai β†’ gom trΓ‘i. Ở 2^3^2, ^β‚‚ cΓ³ lbp 50 vs minbp 49 (= rbp của ^₁) β†’ 50 > 49 Δ‘ΓΊng β†’ gom phαΊ£i. Đúng mα»™t con sα»‘ rbp lαΊ­t cαΊ£ cΓ’y.

3. BαΊ£ng Ζ°u tiΓͺn tΖ°Ζ‘ng tΓ‘c β€” Δ‘α»•i binding power, cΓ’y Δ‘α»•i hΓ¬nh

Biểu thα»©c cα»‘ Δ‘α»‹nh 2 + 3 * 4. KΓ©o binding power của + vΓ  *. Khi lbp(*) > lbp(+) β†’ cΓ’y 2 + (3*4) (nhΓ’n trΖ°α»›c). Đảo lαΊ‘i β†’ (2+3) * 4 (cα»™ng trΖ°α»›c). ThαΊ₯y ngay cΓ’y vΓ  giΓ‘ trα»‹ nhαΊ£y.

Ai Ζ°u tiΓͺn cao hΖ‘n: CΓ’y: =