🌳 Parsing §

= checking if words or statements conform to the rules of a 📖 Formal grammar¹

How? §

→ use 🎰 Automata

Directions §

• ⬇️ Top-Down (= goal-driven)
  • Start at S and progressively replace left-hand sides with right hand sides that match the string
  • Problems:
    • Left recursion (= NT at left edge of left-hand side)
    • Ambiguity
• 🔼 Bottom-Up (= data-driven)
  • Start at word level, progressively replace strings that match right-hand sides with left-hand sides
• Problems when only using TD/BU parsing:
  • Left recursion
  • Ambiguity
  • BU: backtracking → lower ⚡️ Efficiency

Strategies §

• 🧾 Chart parsing
• 🎲 Probabilistic parsing

Evaluation §

• Correctness
• Completeness
• Efficiency

📖 Example result: §

• Bracketing: [(S)[(NP) The children][(VP) ate[(NP) the cake]]]
• Trees:

Footnotes §

1. Syntactic Analysis (Tutorialsprint) ↩