Cây phân tích cú pháp (parse tree) được xây dựng dựa trên ý tưởng

(id + id)

+id+id+

id*id- (id + id)

+(id + id)

Văn phạm phi ngữ cảnh

Văn phạm mơ hồ

Văn phạm LL(1)

Văn phạm LR(1)

Các mục A → xX.y sao cho A → x.Xy thuộc I

Các mục A → x.Xy sao cho A → xX.y thuộc I

Các mục A → xX.y thuộc I

Các mục A → x.Xy thuộc I

Phân tích cú pháp từ trên xuống có thể được xem như một nỗ lực tìm kiếm một dẫn xuất trái nhất cho chuỗi nhập

Phân tích cú pháp từ trên xuống là một quá trình xây dựng cây phân tích cú pháp bắt đầu từ nút gốc và phát sinh dần xuống lá

Một dạng tổng quát của kỹ thuật phân tích từ trên xuống, gọi là phân tích cú pháp đệ quy lùi

Một dạng tổng quát của kỹ thuật phân tích từ trên xuống, gọi là phân tích cú pháp đệ quy tiến

Giả sử x là một chuỗi các ký hiệu văn phạm, FIRST(x) là tập hợp các ký hiệu kết thúc mà nó bắt đầu một chuỗi dẫn xuất từ x

Nếu X là kí hiệu chưa kết thúc thì FIRST(X) là {X}

Giả sử x là một chuỗi các ký hiệu văn phạm, FIRST(x) là tập hợp các ký hiệu không kết thúc mà nó bắt đầu một chuỗi dẫn xuất từ x

Nếu X là kí hiệu kết thúc thì FIRST(X) là {X}

Bộ phân tích cú pháp gạt-thu gọn (Shift – Reduce) cố gắng xây dựng một cây phân tích cú pháp cho chuỗi nhập bắt đầu từ nút lá và đi lên hướng về nút gốc. Tại mỗi bước thu gọn, một chuỗi con cụ thể đối sánh được với vế phải của một luật sinh nào đó thì chuỗi con này sẽ được thay thế bởi ký hiệu vế trái của luật sinh đó. Và nếu chuỗi con được chọn đúng tại mỗi bước, một dẫn xuất phải đảo ngược sẽ được xây dựng

Bộ phân tích cú pháp gạt-thu gọn (Shift – Reduce) là phương pháp xây dựng một cây phân tích cú pháp cho chuỗi nhập bắt đầu từ nút lá và đi lên hướng về nút gốc. Tại mỗi bước thu gọn, một chuỗi con cụ thể đối sánh được với vế trái của một luật sinh nào đó thì chuỗi con này sẽ được thay thế bởi ký hiệu vế phải của luật sinh đó. Và nếu chuỗi con được chọn đúng tại mỗi bước, một dẫn xuất phải đảo ngược sẽ được xây dựng

Bộ phân tích cú pháp gạt-thu gọn (Shift – Reduce) xây dựng một cây phân tích cú pháp cho chuỗi nhập bắt đầu từ nút lá và đi lên hướng về nút gốc. Tại mỗi bước thu gọn, một chuỗi con cụ thể đối sánh được với vế phải của một luật sinh nào đó thì chuỗi con này sẽ được thay thế bởi ký hiệu vế phải của luật sinh đó. Và nếu chuỗi con được chọn đúng tại mỗi bước, một dẫn xuất phải đảo ngược sẽ được xây dựng

Bộ phân tích cú pháp gạt-thu gọn (Shift – Reduce) xây dựng một cây phân tích cú pháp cho chuỗi nhập bắt đầu từ nút lá và đi lên hướng về nút gốc. Tại mỗi bước thu gọn, một chuỗi con cụ thể đối sánh được với vế trái của một luật sinh nào đó thì chuỗi con này sẽ được thay thế bởi ký hiệu vế trái của luật sinh đó. Và nếu chuỗi con được chọn đúng tại mỗi bước, một dẫn xuất phải đảo ngược sẽ được xây dựng

“1” là trị từ vựng của từ tố số nguyên

“1” là mẫu mô mả của từ tố số nguyên

“1” là từ tố số nguyên

“1” là thuộc tính của từ tố số nguyên

5

4

3

2

Trong quá trình phân tích từ vựng các khoảng trắng (blank) sẽ bị bỏ qua

Trong quá trình phân tích từ vựng các khoảng trắng cũng được tính là các từ tố

Trong quá trình phân tích từ vựng các khoảng trắng cũng được tính chung là một từ tố

Trong quá trình phân tích từ vựng các khoảng trắng cũng được tính chung là hai từ tố

0

1

2

3