Top-down parsing và bottom-up parsing là kỹ thuật phân tích cú pháp cây để đạt gốc cây. Hai phương pháp:
Top-down Parsing
- Xem cấp cao nhất của parse tree trước, sau đó xuống dần.
- Sử dụng quy tắc ngữ pháp.
- Dùng leftmost derivation (dẫn xuất trái nhất).
- Cố gắng xác định leftmost derivations cho chuỗi đầu vào.
- Phân tích từ đỉnh xuống lá (top-down).
- Quyết định chính: chọn production rule để xây dựng chuỗi.
Bottom-up Parsing
- Ngược lại top-down: xem cấp thấp nhất (lá) trước, lên dần đến gốc.
- Sử dụng quy tắc ngữ pháp.
- Dùng rightmost derivation (dẫn xuất phải nhất).
- Cố gắng xác định rightmost derivations cho chuỗi đầu vào.
- Cố gắng reduce chuỗi đầu vào về start symbol của ngữ pháp.
- Sử dụng production rule reduce chuỗi về start symbol.