Note for Compiler Design Course in NTHU - Week 3


Left-Recursion Grammar & Right-Recursion Grammar

  • 兩者可以互轉
  • Left-Recursion => Left Associate, Right-Recursion => Right Associate.

Left-Recursion Conversion

S -> Sα | β


S  -> βS'
S' -> αS' | ɛ

Parser for a Grammar

  • Top-down Parser / LL(1) Parser
  • Bottom-up Parser / LR(1) Parser

Chapter 3 - Regular Expression

Regular Expression

FSA - Finite State Automata

  • Regular Expression <=> Finite State Machine
  • 5-tuple (Q, Σ, δ, q。, F)
    • Q - a set of states
    • Σ - an input alphabet, symbol.
    • δ - a transition function
    • q。 - the initial state
    • F - a set of final states
  • DFA vs NFA
  • Finite => State 數量是有限的
  • 沒有 Memory, 無法記憶 alphabet 的數量

Thompson Construction



如果覺得這篇文章對你有幫助, 除了留言讓我知道外, 或許也可以考慮請我喝杯咖啡, 不論金額多寡我都會非常感激且能鼓勵我繼續寫出對你有幫助的文章。

If this blog post happens to be helpful to you, besides of leaving a reply, you may consider buy me a cup of coffee to support me. It would help me write more articles helpful to you in the future and I would really appreciate it.

Related Posts